python - 生成树的定义

Question

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

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

我已经看过一些生成树及其图表的插图，所以我试图提出我自己的例子。

房子图

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

如果我确保两个节点之间仍然存在一条路径，我也可能会摆脱两条边。

我在这个假设中正确吗？

Answer 1

不，您在这个假设中是不正确的，因为您必须删除 2 条边才能构建生成树。删除一个边缘将不起作用。
你图片的房子图有 5 个顶点和 6 条边。
有n顶点的树有n-1边，所以有 5 个顶点的树需要有 4 条边。

生成树并不是一个棘手的对象，它确实名副其实。spanning因为它覆盖了所有顶点，而且tree因为它是一棵树。

如果您要删除一条边，您的图中仍然会有一个循环，因此它不能是一棵树（根据定义，它是一个连接的无环图）。

当您想要构建图的生成树时，这是很容易发现的一件事，它是要删除（或保留，这是等效的）的边数。这个公式#vertices = #edges + 1总是在一棵树中成立。
我建议您查看一棵树的所有定义和特征，记住多个定义和特征总是有用的，尤其是在涉及树木时。