关键词不能为空

当前您在: 主页 > 英语 >

狄拉克定理-奥勒定理

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-02-01 21:29
tags:

-

2021年2月1日发(作者:调酒器)



哈密顿图判定



< /p>



假设


G


?


(


V


,


E


)


是一个哈密顿图,则对


V

的任意非空子集


V


1


均有


W


(


G


?


V


1


)


?

< br>|


V


1


|



这里


G


?


V


1


表示从图


G


中删去


V


1


中的所有顶点以及所关联 的边;


W


(


G


?


V


1


)


表示 子



G


?


V< /p>


1


的连通分支数。


证明:


因为图


G


是哈密顿图









所以必 存在哈密顿回路


C


。我们来考察一下两种情况

< br>








i




V


1


中的顶点在


C


中均彼此相邻,则


W


(


C


?


V


1

)


?


1


?


|


V


1


|











ii



V


1


中的顶点在


C


中不相邻,不妨设有

< p>
r


?


2


并且


r


?


|


V

< br>1


|


个顶点不相邻

















W


(


C


?


V


1


)


?


r


?


|


V


1


|

< br>














一般情况下,


V

1


中的顶点在


C


中既有相邻的也有 不相邻的。















所以


< /p>


W


(


C


?


V


1


)


?

< p>
|


V


1


|
















C


?


V


1


是图


G


?


V


1


的生成子图< /p>















所以


|


E< /p>


(


C


?


V


1


)


|


?

< p>
|


E


(


G


?


V


1


)

|















所以,


W


(


G


?


V


1


)


?


W


(


C


?


V


1


)


?


|


V

< br>1


|






证毕


< /p>


这是一个判定哈密顿图的必要条件,但它不充分。如果某一个图不满足

W


(


G


?


V


1


)


?


|< /p>


V


1


|



则可以断定它不是哈密顿图。



< p>
②狄拉克定理:


如果图


G


是一个具有


n


(


n

?


3


)


个顶点的简单图,并且图< /p>


G


中每个顶点


的度数至少为


n


,那么图


G


是哈密顿图。



2


Dirac



s theorem



If G is a simple graph with n vertices with n


?


3 such that the degree of


every vertex in G is at least n/2,then G has a Hamilton circuit.


狄拉克定理是英国数学家


G



A


.狄拉克(


Dirac


)在


1952


年给出的一个判定哈密顿图


的充分条件。


一般来讲都 是从简单图讨论。


因为对哈密顿图来讲每个顶点只能通过一次,



以如果图中出现自环和平行边,


那么对构造哈密顿图是没有什 么影响的,


因此,


只考虑简单


图即可。



证明:


假设


G


不是哈密顿图









在图


G


中连 接不相邻的两个顶点,所得到的图仍然满足定理的条件









(我们知道,当图


G


通过上述方法添加边,最终可以构造出一个完全图,而完


全图必定是哈密顿图)









因此通 过上述方法添加边,总可以使图


G


成为满足条件的极大非哈密顿 图。













这里不 妨设


G


就是极大非哈密顿图













(所谓极大非哈密顿图是指该图本 身不是哈密顿图,


但是在该图中,


任意一对不

< br>相邻的顶点之间加上一条边,它就成为哈密顿图。极大非哈密顿图肯定不是完全图)














G


中取两个不相邻的顶点


u



v














G


?


uv


必是哈密顿图,并且该哈密顿回路一定包含边


{


u


,


v


}













于是图


G


中一定存在一条从顶点


u


到顶点


v


的哈密顿通路(不是哈密顿回路)














u


?


v


1


v


2


v


3


...


v


n


?


v















S


?


{


v


i


|


{


v


1


v


i


?


1


}

< br>?


E


}





凡是与


v


1


邻接的顶点的前一个序号的顶点组成的集合



i


?


1


,

< br>2


,...,


n


?


1



-


-


-


-


-


-


-


-



本文更新与2021-02-01 21:29,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/595211.html

狄拉克定理-奥勒定理的相关文章

  • 余华爱情经典语录,余华爱情句子

    余华的经典语录——余华《第七天》40、我不怕死,一点都不怕,只怕再也不能看见你——余华《第七天》4可是我再也没遇到一个像福贵这样令我难忘的人了,对自己的经历如此清楚,

    语文
  • 心情低落的图片压抑,心情低落的图片发朋友圈

    心情压抑的图片(心太累没人理解的说说带图片)1、有时候很想找个人倾诉一下,却又不知从何说起,最终是什么也不说,只想快点睡过去,告诉自己,明天就好了。有时候,突然会觉得

    语文
  • 经典古训100句图片大全,古训名言警句

    古代经典励志名言100句译:好的药物味苦但对治病有利;忠言劝诫的话听起来不顺耳却对人的行为有利。3良言一句三冬暖,恶语伤人六月寒。喷泉的高度不会超过它的源头;一个人的事

    语文
  • 关于青春奋斗的名人名言鲁迅,关于青年奋斗的名言鲁迅

    鲁迅名言名句大全励志1、世上本没有路,走的人多了自然便成了路。下面是我整理的鲁迅先生的名言名句大全,希望对你有所帮助!当生存时,还是将遭践踏,将遭删刈,直至于死亡而

    语文
  • 三国群英单机版手游礼包码,三国群英手机单机版攻略

    三国群英传7五神兽洞有什么用那是多一个武将技能。青龙飞升召唤出东方的守护兽,神兽之一的青龙。玄武怒流召唤出北方的守护兽,神兽之一的玄武。白虎傲啸召唤出西方的守护兽,

    语文
  • 不收费的情感挽回专家电话,情感挽回免费咨询

    免费的情感挽回机构(揭秘情感挽回机构骗局)1、牛牛(化名)向上海市公安局金山分局报案,称自己为了挽回与女友的感情,被一家名为“实花教育咨询”的情感咨询机构诈骗4万余元。

    语文