离散数学 第四篇 图论06 哈密顿图

离散数学

定义

哈密尔顿通路（回路）

经过每个结点一次仅且一次的通路（回路）
哈密尔顿通路是经过图中所有结点的初级通路
哈密尔顿回路是经过图中所有结点的初级回路

半哈密尔顿图

有哈密尔顿通路的图

哈密尔顿图

有哈密尔顿回路的图

平凡图即哈密顿图

哈密顿图的判定

狄拉克定理

如果$G$是有$n$个顶点的简单图，其中$n \geqslant 3$，并且$G$中每个顶点的度都至少为$\frac{n}{2}$,则$G$有哈密顿回路（即为哈密顿图）

欧尔定理

如果$G$是有$n$个顶点的简单图，其中$n \geqslant 3$，并且$G$中每一对不相邻的顶点$u,v$ 来说的都有$deg(u)+deg(v) \geqslant n$,则$G$有哈密顿回路（即为哈密顿图）

哈密顿图的应用