8.3哈密尔顿图

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,8.3,哈密尔顿图,哈密尔顿通路,(,回路,),、哈密尔顿图,经过图中每个顶点一次且仅一次的通路,(,回路,),称为,哈密尔顿通路,(,回路,).,存在哈密尔顿回路的图称为,哈密尔顿图,.,图中,(1),(3),不是哈密尔顿图,(2),为哈密尔顿图,.,是不是哈密尔顿图,?,哈密尔顿图的判定,定理,(,必要条件,1),设无向图,G=,是,哈密尔顿图,V,1,是,V,的任意的非空子集,p(G-V,1,),V,1,.,其中,p(G-V,1,),为从,G,中,删除,V,1,(,删除,V,1,中各顶点及关联的边,),后所得,图的连通分支数,.,证明,:,设,C,为,G,中的一条哈密尔顿回路,.,(1),若,V,1,中的顶点在,C,上彼此相邻,则,p(C-V,1,)=1,V,1,(2),设,V,1,中的顶点在,C,上存在,r(2r,V,1,),个互不相邻,则,p(C-V,1,)=r,V,1,一般说来,V,1,中的顶点在,C,上既有相邻的,又有不相邻的,因而总有,p(C-V,1,),V,1,.,又因为,C,是,G,的生成子图,故,p(G-V,1,)p(C-V,1,),V,1,.,(1),图不是哈密尔顿图,.(3),图也不是哈密尔顿图,.,例,在图中，虽然对任意的结点集合,V,1,，,都满足,p(G-V,1,),|V,1,|,，但它仍然不是哈密尔顿图。,定理,(,充分条件,1,),设,G,是简单无向图。如果对任意两个不相邻的结点,u,，,v,V,，均有：,deg(u)+deg(v),|V|-1,，,则,G,中,存在哈密尔顿通路,；,如果对任意两个不相邻的结点,u,，,v,V,，均有：,deg(u)+deg(v),|V,|,，,则,G,中,存在哈密尔顿回路,，即,G,是哈密尔顿图。,例,在图,中，任意两个结点的度数之和为4，结点数为6，即有4,6,，但它仍然是,哈密尔顿图。,定理,6.G,有,n,个顶点，,m,条边，如果 ，则,G,是,Hamilton,图。,证明,.,任取不相邻的两个顶点,u,，,vG,，,G,中去掉,u,，,v,后导出子图,G,G,有,n,2,个顶点，至多 条边,.,U,v,到,G,的边数有,D(u)+D(v)n,.,由充分条件,1,得，,G,是,Hamilton,图。,推论,n,阶简单无向图,G,中，,n2,任意顶点的度数大于等于,n/2,，则,G,有,Hamilton,回路。,充分条件,2,完全图,Kn,，,n2,，是,Hamilton,图。,归纳可证。,定理,在,n(n2),阶有向图,D=,中,如果所有,有向边均用无向边代替,所得无向图中,含生成子图,K,n,则,有向图,D,中,存在哈密尔顿通路,.,推论,n(n3),阶有向完全图为哈密尔顿图,.,