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