如何证明无圈图有n-1边？

Question

我对这个数学不太感兴趣，但我理解的是.

图g具有v个顶点和边。G= (V，E)；

这个图的生成图是这个图的一个无圈拷贝，其中所有的顶点都存在，所有的边都是图的子集，条件是每个连接是不同的。

很明显，MST应该有n-1节点。如何证明这一点？

来源：

http://youtu.be/zFbq8vOZ_0k?t=25m1s

http://www.gtkesh.com/minimum-spanning-tree/

Answer 1

归纳证明：

如果所有节点都是连通的，则每个无圈图都可以表示为树。

所以让我们想想树木。你有一个根节点。让我们看看最简单的例子，在这种情况下，树只有一个分支，所以它是一个简单的链表。

如果有两个节点，它们之间就有一个边。将一个节点添加到链接列表的末尾，有三个节点和两个边，以此类推。

现在，如果我们获取链接列表并将另一个节点添加到中间的一个节点中，那么我们就有了一棵真正的树。再一次，我们在一个边加上一个节点。再加一个，就一样了。

不管您添加了多少个节点，或者在哪里添加它们，只要它仍然是一个无循环的、完全连接的树，N节点总是有N个边。

Answer 2

考虑任何最小生成树。选择一些顶点作为根。然后每个顶点都有一个父节点，除了根。

Answer 3

基本上和梅森和迈克说的一样，但用不同的话说.

如果你没有边，你能拥有的最多(连通的)顶点就是一个。把这个顶点称为根。

若要向树添加新顶点，还必须添加新的边缘(以便连接新的顶点)。该边缘可以(而且必须)连接到任何预先存在的顶点.新顶点是预先存在的顶点的子节点，我们不限制父节点可以拥有的子节点数。

如果你只从根开始(一个顶点和零个边)，你就会得到两个顶点和一个边。重复n次得到n+1顶点和n个边。

这本身并不是一个完整的证明，但不可能以任何其他方式添加边或顶点(除非您可以同时添加两个子节点，前提是您这样做的方式相当于先添加一个，然后再添加另一个)。如果不添加顶点，就不能添加边，因为这样做会完成一个循环。如果不添加边，就不能添加顶点，因为这个顶点不会连接到树上。

顺便说一句--对无向图形来说，“根”、“父”和“子”这样的词并不意味着什么，至少不是正式意义上的。任何无向树中的任何顶点都可以被认为是根，而您碰巧调用根的顶点决定了所有边的哪个顶点是父顶点，哪个是子顶点。我对一棵树的印象往往包括识别一个特定的顶点作为根，但这可以说是一种误导性的心理形象。