离散数学-哈密顿图复习

离散数学-哈密顿图复习

定义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)阶有向完全图为哈密顿图。http://www.cnrencai.com/

【离散数学-哈密顿图复习】相关文章：

离散数学-欧拉图复习10-09

离散数学-二部图复习10-09

离散数学-图论基础复习10-09

离散数学趣味题目10-09

探寻刑法司考规律，预测来年复习重点(图)10-13

离散数学分层次实验教学设计应用论文03-26

条形图与扇形图教学设计02-24

另有所图成语01-16

唯利是图成语01-20