我想检查一下我对生成树（对于无向和连接图）的理解是否正确。
从，我在网上看到的。生成树是图形的子集，它包含相同数量的图形顶点，但它具有最小量的边缘。图形也可以有许多不同的生成树。
我已经看到了生成树及其图形的一些插图，所以我试图想出我自己的例子。
所以这张图片显示了一个房屋形状图。如果我要摆脱该房屋图中的一个边缘，那么这将是一个生成树，因为有一条从一个节点到另一个节点的替代路径。
如果我确保在两个节点之间仍然存在路径，我还可以摆脱两条边。
我在这个假设中是否正确？
不，您在此假设中不正确，因为您必须删除2条边以构建生成树。删除一条边不起作用。
你图片的房子图有5个顶点和6个边。
具有n顶点的树具有n-1边，因此具有5个顶点的树需要具有4个边。
生成树不是一个棘手的对象，它实际上是它的名字。 spanning因为它涵盖了所有顶点，而tree因为它是一棵树。
如果要删除单个边，图中仍会有一个循环，因此它不能是树（根据定义，它是连接的非循环图）。
当你想要构建图形的生成树时，这是很容易找到的一件事，它是要删除的边数（或保持，这是等价的）。公式#vertices = #edges + 1总是在树上。
我建议你看一下树的所有the definitions and characterisations，考虑到不止一个，总是有用的，特别是树木时。