欧拉图和哈密顿图小总结

欧拉图

概念

定义

欧拉回路:图中经过每条边一次且仅一次的环;
欧拉路径:图中经过每条边一次且仅一次的路径;
欧拉图:有至少一个欧拉回路的图;
半欧拉图:没有欧拉环,但有至少一条欧拉路径的图。

无向图判定条件

  • 图是联通的(度数为0的点不用考虑,因为是孤立的点,没影响)~先决条件
  • 所有点的度数都是偶数~存在欧拉回路,欧拉图
  • 有且仅有两个点的度数是奇数~存在欧拉路径,半欧拉图
    两个奇数度数的点一个是路径起点一个是路径终点

证明:因为任意一个点,欧拉环(或欧拉路径)从它这里进去多少次就要出来多少次,故(进去的次数+出来的次数)为偶数,又因为(进去的次数+出来的次数)=该点的度数(根据定义),所以该点的度数为偶数。

有向图判定条件

  • 把所有的边强行改为无向边之后(这个图叫原图的基图),联通~先决条件
  • 所有点出度等于入度~存在欧拉回路,欧拉图
  • 有且仅有两个点出度不等于入度,一个出度比入度大1,另一个入度比出度大1~欧拉路径,半欧拉图
    出度比入度大1的点是路径起点,入度比出度大1的点是路径终点

证明:与无向图证明类似,一个点进去多少次就要出来多少次。

模板

 

1 Comment

  1. […] 如果不会这个知识,请参考:有关欧拉图问题的一些总结。 […]

    Reply

Leave a Reply

Scroll to top