哈密顿回路存在性判断的一些充分条件

(已会)1.Dirac定理:无向图共n个顶点,每个顶点的度数均>=ceil(n/2),则该图一定含有哈密顿回路

(3的充分条件)

2.设G是含有n个顶点的无向简单图,如果G的每一对顶点度数之和>=n-1,则G一定存在哈密顿路

(已会)3.设G是含有n个顶点的无向简单图,如果G的每一对顶点度数之和>=n,则G一定存在哈密顿回路(Dirac定理的必要条件)

(已会)4.竞赛图一定有哈密顿路

5.竞赛图含有哈密顿回路当且仅当该竞赛图强连通

1.3的解决方法一样的,因为1和3本质相同,1比3条件强一些而已