定义1: 经过图中每个顶点一次且仅一次的通路称为哈密顿通路。存在哈密顿回路的图称为哈密顿图。
定理1: 设无向图G=是哈密顿图,V1是V的任意的非空子集,
则
p(G-V1)<=|V1|
其中,p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。
定理2: 设G是n(n>=3)阶无向简单图,如果G中任何一对不相邻的顶点度数之和都大于等于n,则G是哈密顿图。
推论: 设G是n(n>=3)阶无向简单图,如果G中任何一对不相邻的顶点的度数之和都大于等于n,则G是哈密顿图。
定理3: 在n(n>=2)阶有向图D=中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图中存在哈密顿图。
推论: n(n>=3)阶有向完全图为哈密顿图。
正在阅读:
2017年计算机等级考试四级离散数学——哈密顿图复习06-02
写给新兵家长的慰问信范文03-30
2017山东三本大学排名大全11-10
2017高考第一轮复习英语单词速记的方法05-26
2019年广东江门中考数学答案(已公布)03-30
高三化学下册测试试题03-30