图论课件--极图理论简介

《图论课件--极图理论简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用应用数学学院1第一章图的基本概念本次课主要内容极图理论简介(一)、l部图的概念与特征(二)、托兰定理(三)、托兰定理的应用21978年，数学家Bollobas写了一本书《极值图论》(ExtremalGraph）,是关于极值图论问题的经典著作。P.Erdồs是该研究领域的杰出人物。他是数学界的传奇人物，国际图论大师，获过Wolf数学奖。他是20世纪最伟大的数学家之一，也是人类历史上发表数学论文最多的数学家(1000多篇),第二名是欧拉(837篇)。他于1996年9月20日因心脏病去世，享年

2、83岁，他的逝世当时惊动了整个数学界。极图属于极值图论讨论的范畴，主要研究满足某个条件下的最大图或最小图问题。上世纪70年代末，极值图论已经形成了相对完整的理论体系，但还有很多引人入胜的公开性问题没有解决，所以，直到现在，它仍然是重要研究方向。但是，该方向是比较困难的数学研究方向之一。3本次课，主要介绍极值图论中的一个经典结论：托兰定理。(一)、l部图的概念与特征定义1若简单图G的点集V有一个划分：且所有的Vi非空，Vi内的点均不邻接，称G是一个l部图。4部图4定义2如果在一个l部图G中，任意部Vi

3、中的每个顶点，和G中其它各部中的每个顶点均邻接，称G为完全l部图。记作：例如：K1,2,2显然：5定义3如果在一个n个点的完全l部图G中有：则称G为n阶完全l几乎等部图，记为Tl,n

4、V1

5、=

6、V2

7、=…=

8、Vl

9、的完全l几乎等部图称为完全l等部图。定理1：连通偶图的2部划分是唯一的。证明设连通偶图G的2部划分为V1∪V2=V。6取v∈V1，由于G连通，对任何u∈V1∪V2，G中有联结u和v的路，故d(v,u)有定义。因为任何一条以v为起点的路交替地经过V1和V2的点，可知一个点u∈V2当且仅当d(

10、v,u)是奇数。这准则唯一地决定了G的2部划分。定理2：n阶完全偶图Kn1,n2的边数m=n1n2,且有：证明：m=n1n2显然。下面证明第二结论：7证明：首先有：定理3n阶l部图G有最多边数的充要条件是G≌Tl,n。其次，考虑：则f取最大值的充分必要条件为：1≦i

11、,2)与(3,3,3,3)没有度弱关系！定理4若n阶简单图G不包含Kl+1，则G度弱于某个完全l部图H，且若G具有与H相同的度序列，则:9证明：对l作数学归纳证明。当l=1时，结论显然成立；设对l

12、2VH1,则H是完全t部图。下面证明定理的第二个结论。10若G与H有相同的度序列，而H=G2VH1,所以，G与G1VG2有相同的度序列。由此可以推出：G=G1VG2因为G=G1VG2和H=G2VH1有相同度序列，于是得到G1和H1有相同度序列，所以：定理5（Turán）若G是简单图，并且不包含Kl+1,则：仅当时，有11证明：由定理4知：G度弱于某个完全l部图H。于是：又由定理3知：所以得：下面证明定理5的后一论断。12如果则有G与H有相同度序列，由定理4：又由，且由定理3，有：所以有：13几个有趣

13、的相关结果：设m(n,H)表示n阶单图中不含子图H的最多边数，则：其中，14(三)、托兰定理的应用问题：工兵排雷问题一个小组n个人在一个平原地区执行一项排雷任务。其中任意的两个人，若其距离不超过g米，则可用无线电保持联系；若发生触雷意外，地雷的杀伤半径为h米。问：在任意的两个人之间均能保持联系的条件下，平均伤亡人数最低的可能值为多少？分析：(1)为保持通信，排雷工兵相互之间距离不能超过g米。因此，他们必须分布在直径是g米的圆形区域内.15(2)若某人A触雷，则与A的距离大于h米的人将是安全的，但究竟

14、哪个人会发生触雷意外，事先是不知道的，所以此问题实际上是求在任意的两个人之间的距离不超过g米的条件下，距离大于等于h米的人数对最多能达到多少对。(3)如果有n个工兵：{x1,x2,…,xn},每个工兵用一个点表示，两点连线，当且仅当他们距离大于h米.16ThankYou!17