跨越的定义

Question

我想检查我对生成树（对于无向图和连通图）的理解是否正确。你知道吗

从，我在网上读到的。生成树是图的一个子集，它包含与图相同数量的顶点，但是它有最小数量的边。一个图也可以有许多不同的生成树。你知道吗

我看过一些生成树的插图和它们的图表，所以我试着提出我自己的例子。你知道吗

house graph

所以这张图显示了一个房子形状的图形。如果我要去掉房屋图中的一条边，这将是一个生成树，因为有一个从一个节点到另一个节点的替代路径。你知道吗

如果我确定在两个节点之间仍然存在一条路径，我还可以潜在地去掉两条边。你知道吗

我的假设正确吗？你知道吗

Answer 1

不，这个假设是不正确的，因为要构建生成树，必须删除2条边。去掉一条边是行不通的。
您的图片的房屋图有5个顶点和6条边。
有n个顶点的树有n-1条边，所以有5个顶点的树需要有4条边。你知道吗

生成树并不是一个复杂的对象，它真正的意义在于它的名字。spanning因为它覆盖了所有顶点，tree因为它是一棵树。你知道吗

如果要删除一条边，那么图中仍然会有一个循环，因此它不能是树（根据定义，它是一个连通的非循环图）。你知道吗

这是一件很容易找到的事情，当你想建立一个图的生成树，它是要删除（或保留，这是等价的）边的数量。公式#vertices = #edges + 1总是适用于树。
我建议你看一看一棵树的所有部分，记住不止一个总是有用的，尤其是当涉及到树的时候。你知道吗