首页 > 试题广场 >

证明：若无向图G中每个顶点的度至少为2，则G必然存在回路。

[问答题]

证明：若无向图G中每个顶点的度至少为2，则G必然存在回路。


添加回答
牛客4414733号头像 牛客4414733号
因为每个结点的度至少为2，则说明没有度为0和度为1的结点，所以该图存在回路。
发表于 2017-11-30 21:25:31 回复(0)
xizhou头像 xizhou
简单的说,就是没有回路,必有叶子节点,与度不为1矛盾
复杂的说：
反证：如果G中不存在回路,则必有一个节点的度为1
可以说明：任意找一个节点,开始遍历,那么最终会访问到一个叶子节点.
任何一个访问到的节点u,存在以下几种情况
1. 是叶子节点（证明结束）
2. 存在节点v,v尚未被访问,且边(u,v)存在,则继续访问v
3. 任何与u有边相连的节点都已经被访问,这种情况会构成回路（与假设矛盾,证明结束）
因为节点个数有限,所以只有有限次可能会落入情况2,随着遍历的进行,必然会落入情况1和3
发表于 2021-12-11 20:00:23 回复(0)
提交观点

问题信息

图
上传者：城市里的养猫者
难度：
2条回答 4808浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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