有向图中每个顶点的度数都大于2,一定存在回路吗?

分类: 作业答案 • 2021-12-29 14:42:14

问题描述：

答

因为每个顶点的度数都大于2,所以必然有两个通道或以上的通道连接每个点,现在我们反过来思考,如果不存在回路的话,必然存在有一个断点,该点只有一个通道连接,所以根据题意不存在这样的点,也就是说必然存在回路.