首页 > 试题广场 >

试证明:对于一个无向图G=(V,E),若G中各顶点的度均大于

[问答题]
试证明:对于一个无向图G=(V,E),若G中各顶点的度均大于或等于2,则G中必有回路存在。
添加回答
skylee03头像 skylee03
反证：如果G中不存在回路,则必有一个节点的度为1
可以说明：任意找一个节点,开始遍历,那么最终会访问到一个叶子节点.
任何一个访问到的节点u,存在以下几种情况
1. 是叶子节点（证明结束）
2. 存在节点v,v尚未被访问,且边(u,v)存在,则继续访问v
3. 任何与u有边相连的节点都已经被访问,这种情况会构成回路（与假设矛盾,证明结束）
因为节点个数有限,所以只有有限次可能会落入情况2,随着遍历的进行,必然会落入情况1和3
发表于 2018-12-11 16:53:16 回复(0)
乌鲁鲁头像 乌鲁鲁
解（1）、回路是环的一种特殊情况，先证明有环这一种普遍规律，再进一步可证明有回路
    （2）、假设该图无环，那么存在一条最长路径P，设起点为Vs，终点Ve
    （3）、那么Ve或者Vs的邻居点都在P上
               （可以反证法证明：如果存在Ve的邻居点Vn，不在P上，那么最长路径为P+(Ve,Vn)，与最长路径为P矛盾）
    （4）、由于这是一条无环图的最长路径，所以Ve与Vs的度为1
      但题目中，所有点的度大于等于2
     （1）、假设P上的Ve的度为2，那么除了与P上邻居点的一条外，还有另一条边Ee
     （2）、假设Vx在P上，且Ee = （Ve，Vx）
                  那么，（Vx，Ve）并 Ee 即是一个环，因为Vx通过（Vx，Ve）和 Ee 可以回到 Vx
     （3）、进而，如果Vx = Vs，那么这个环就是回路了
发表于 2018-12-18 15:36:50 回复(1)
提交观点

问题信息

图
上传者：小小
难度：
2条回答 6983浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号