离散数学——哈密顿图复习
定义:经过图中每个顶点一次且仅一次的路称为哈密尔顿路。有哈密尔顿回路的图称为哈密尔顿图。
定理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)有向完全图是哈密顿图。
0条评论