资源描述
1,图论及其应用,应用数学学院,2,第一章图的基本概念,本次课主要内容,极图理论简介,(一)、l部图的概念与特征,(二)、托兰定理,(三)、托兰定理的应用,3,1978年，数学家Bollobas写了一本书极值图论(ExtremalGraph）,是关于极值图论问题的经典著作。,P.Erds是该研究领域的杰出人物。他是数学界的传奇人物，国际图论大师，获过Wolf数学奖。他是20世纪最伟大的数学家之一，也是人类历史上发表数学论文最多的数学家(1000多篇),第二名是欧拉(837篇)。他于1996年9月20日因心脏病去世，享年83岁，他的逝世当时惊动了整个数学界。,极图属于极值图论讨论的范畴，主要研究满足某个条件下的最大图或最小图问题。,上世纪70年代末，极值图论已经形成了相对完整的理论体系，但还有很多引人入胜的公开性问题没有解决，所以，直到现在，它仍然是重要研究方向。但是，该方向是比较困难的数学研究方向之一。,4,本次课，主要介绍极值图论中的一个经典结论：托兰定理。,(一)、l部图的概念与特征,定义1若简单图G的点集V有一个划分：,且所有的Vi非空，Vi内的点均不邻接，称G是一个l部图。,5,定义2如果在一个l部图G中，任意部Vi中的每个顶点，和G中其它各部中的每个顶点均邻接，称G为完全l部图。记作：,例如：,显然：,6,定义3如果在一个n个点的完全l部图G中有：,则称G为n阶完全l几乎等部图，记为Tl,n,|V1|=|V2|=|Vl|的完全l几乎等部图称为完全l等部图。,定理1：连通偶图的2部划分是唯一的。,证明设连通偶图G的2部划分为V1V2=V。,7,取vV1，由于G连通，对任何uV1V2，G中有,联结u和v的路，故d(v,u)有定义。,因为任何一条以v为起点的路交替地经过V1和V2的点，可知一个点uV2当且仅当d(v,u)是奇数。这准则唯一地决定了G的2部划分。,定理2：n阶完全偶图Kn1,n2的边数m=n1n2,且有：,证明：m=n1n2显然。下面证明第二结论：,8,证明：首先有：,定理3n阶l部图G有最多边数的充要条件是GTl,n。,其次，考虑：,则f取最大值的充分必要条件为：1ijl,有:,而G的对应的顶点划分形成的l部图正好为Tl,n,从而证明了该定理。,9,(二)、托兰定理,定义4设G和H是两个n阶图，称G度弱于H，如果存在双射：V(G)V(H),使得：,注意：若G度弱于H，一定有：,但逆不成立！例如：(1,1,4,2)与(3,3,3,3)没有度弱关系！,定理4若n阶简单图G不包含Kl+1，则G度弱于某个完全l部图H，且若G具有与H相同的度序列，则:,10,证明：对l作数学归纳证明。,当l=1时，结论显然成立；,设对lt时，结论成立。考虑l=t时的情况。,令uV(G),且d(u)=(G).,设G1=GN(u),则G1不含Kt,否则，G含Kt+1,矛盾！,由归纳假设，G1度弱于某个完全t-1部图H1.,又令V1=N(u),V2=V-V1,用G2表示顶点集合为V2的空图，则G度弱于G2VG1，当然度弱于G2VH1。,令H=G2VH1,则H是完全t部图。,下面证明定理的第二个结论。,11,若G与H有相同的度序列，而H=G2VH1,所以，G与G1VG2有相同的度序列。,由此可以推出：G=G1VG2,因为G=G1VG2和H=G2VH1有相同度序列，于是得到G1和H1有相同度序列，所以：,定理5（Turn）若G是简单图，并且不包含Kl+1,则：,仅当时，有,12,证明：由定理4知：G度弱于某个完全l部图H。于是：,又由定理3知：,所以得：,下面证明定理5的后一论断。,13,如果,则有,G与H有相同度序列，由定理4：,又由，且由定理3，有：,所以有：,14,几个有趣的相关结果：,设m(n,H)表示n阶单图中不含子图H的最多边数，则：,其中，,15,(三)、托兰定理的应用,问题：工兵排雷问题,一个小组n个人在一个平原地区执行一项排雷任务。,其中任意的两个人，若其距离不超过g米，则可用无线,电保持联系；若发生触雷意外，地雷的杀伤半径为h米。,问：在任意的两个人之间均能保持联系的条件下，平均,伤亡人数最低的可能值为多少？,分析：(1)为保持通信，排雷工兵相互之间距离不能超过g米。因此，他们必须分布在直径是g米的圆形区域内.,16,(2)若某人A触雷，则与A的距离大于h米的人将是安,全的，但究竟哪个人会发生触雷意外，事先是不知,道的，所以此问题实际上是求在任意的两个人之间,的距离不超过g米的条件下，距离大于等于h米的人,数对最多能达到多少对。,(3)如果有n个工兵：x1,x2,xn,每个工兵用一个点表示，两点连线，当且仅当他们距离大于h米.,17,ThankYou!,
展开阅读全文