用张铭编写的《数据结构与算法》证明: 对于一个无向图 G=<V, E>,若 G 中各顶点度数都大于等于 2,则 G 中必有回路。
时间: 2023-06-25 22:08:26 浏览: 163
首先,我们需要明确一个概念,回路(Cycle)是指在图中存在至少一条边,能够从某个顶点出发,经过若干个不同的顶点后,再回到这个出发点。
接下来,我们使用反证法证明原命题。
假设 G 中不存在回路,即 G 是无环图。
由于 G 中各顶点度数都大于等于 2,那么对于任意一个顶点 v∈V,它至少有两条出边,连接着不同的顶点。我们从这个顶点 v 出发,依次沿着其中一条出边走到下一个顶点,然后再沿着其中一条出边走到下一个顶点,一直走下去,直到无法继续走下去为止,这时我们会停在一个度数为 1 的顶点 u 上。
由于 G 是无环图,我们不能再从顶点 u 出发继续往下走,因为如果我们能够继续往下走,那么我们就会形成一个回路,与假设矛盾。因此,顶点 u 只有一条入边与之相连,否则它的度数就大于等于 2。
现在我们考虑从顶点 u 出发,继续按照上述方法往下走,走到下一个度数为 1 的顶点 v 上。同样地,顶点 v 也只有一条入边与之相连。
继续往下走,我们会发现如果 G 是无环图,那么我们最终一定会走到某个度数为 1 的顶点 w 上,且顶点 w 的入边与顶点 v 的出边相同。如下图所示:
```
v ----> w
^ |
| |
+-------+
```
现在我们将这条边从图中删除,再将顶点 w 也从图中删除,得到新的图 G'。由于顶点 w 的入边和顶点 v 的出边相同,所以删除这条边对 G 的连通性没有影响。此时,顶点 v 的度数减少了 1,但仍然大于等于 1。同样地,对于顶点 u 和它的出边也是如此。因此,我们可以重复上述过程,每次都删除某个度数为 1 的顶点及其相连的边,直到剩余的图 G'' 中只剩下一个度数不为 0 的连通分量。
最终得到的图 G'' 中,所有顶点的度数都为 0,这是因为每次删除顶点和边时,总度数减少 2,而初始时总度数为偶数(因为每条边都被算了两次),因此经过若干次删除后,剩余的总度数为偶数,而每个顶点的度数又都是偶数,所以剩余的图中顶点的度数都为偶数,与总度数为偶数矛盾。
因此,假设不成立,原命题得证。即,对于一个无向图 G=<V, E>,若 G 中各顶点度数都大于等于 2,则 G 中必有回路。
阅读全文