离散数学——哈密顿图复习

定义:经过图中每个顶点一次且仅一次的路称为哈密尔顿路。有哈密尔顿回路的图称为哈密尔顿图。

定理1:设无向图G=是哈密尔顿图，V1是V的任意非空子集，
则
p(G-V1)，其中p(G-V1)是从G中删除V1(删除每个V1

定理2:设G是n阶(n>=3)的无向简单图。如果G中任意一对不相邻顶点的度数之和大于或等于n，则G是哈密尔顿图。

推论:设G是n阶无向简单图(n>=3)。如果G中任意一对不相邻顶点的度数之和大于或等于n，则G是哈密尔顿图。

定理3:在一个n阶有向图D=中(n>=2)，如果所有的有向边都被无向边代替，且由此产生的无向图包含生成子图Kn，则该有向图中存在一个哈密顿图。

推论:n阶(n>=3)有向完全图是哈密顿图。