证明子图是生成树

Question

设T和T‘是连通图G的2生成树。证明了T‘中存在一个弧y，使得(T-{x})∪{y}和(T'-{y})∪{x}是G中的生成树。

有什么办法能证明这一点吗？有正式的方法证明子图是生成树吗？

Answer 1

是的，是的。

证明子图是生成树的方法是：

1. 子图涉及图中的所有节点；以及
2. 子图是一棵树。
   • 任何两个节点之间都有一条路径。

​

因为T和T'都是生成树，所以您知道T或T'中的任何两个节点之间都有一条路径，而T和T'都会接触G中的每个节点。

如果您从arc x中删除T，那么您将得到两棵树。我们叫他们T0和T1。由于T'触及每个节点，所以必须在T'中存在一个arc y，以便一个端点位于T0中，另一个端点位于T1中。

arc x和arc y都是连接T0和T1的弧。由于连接两棵树产生了一棵树，T0和T1覆盖了G、(T-{x})∪{y}和(T'-{y})∪{x}中的所有节点。

正如您可能已经注意到的，我没有详细介绍实际的证据，只是做了一个概述。你需要证明：

1. 将arc x从T中删除会产生两棵树，T0和T1，它们不共享节点，也不共享弧；
2. arc y必须存在于T'中，它将T0与T1连接起来；
3. 将arc y从T'中移除会产生两棵树，覆盖与T0和T1相同的节点；
4. 将两棵树与弧形连接起来会产生一棵树。

再加上一些其他的小东西，把它们结合在一起，形成一个连贯的答案，但这4件事是需要展示的核心项目。一旦你证明了这些事情，其他的事情都很容易推断出来。

祝你好运，我认为这是一份家庭作业。