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

  1. 1、本文档共17页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
图论课件--极图理论简介.ppt图论课件--极图理论简介.ppt图论课件--极图理论简介.ppt

* * 图论及其应用 应用数学学院 第一章 图的基本概念 本次课主要内容 极图理论简介 (一)、l 部图的概念与特征 (二)、托兰定理 (三)、托兰定理的应用 1978年,数学家Bollobas写了一本书《极值图论》(Extremal Graph),是关于极值图论问题的经典著作。 P. Erd?s是该研究领域的杰出人物。他是数学界的传奇人物,国际图论大师,获过Wolf数学奖。他是20世纪最伟大的数学家之一,也是人类历史上发表数学论文最多的数学家(1000多篇),第二名是欧拉(837篇)。他于1996年9月20日因心脏病去世,享年83岁,他的逝世当时惊动了整个数学界。 极图属于极值图论讨论的范畴,主要研究满足某个条件下的最大图或最小图问题。 上世纪70年代末,极值图论已经形成了相对完整的理论体系,但还有很多引人入胜的公开性问题没有解决,所以,直到现在,它仍然是重要研究方向。但是,该方向是比较困难的数学研究方向之一。 本次课,主要介绍极值图论中的一个经典结论:托兰定理。 (一)、l 部图的概念与特征 定义1 若简单图G的点集V有一个划分: 且所有的Vi非空,Vi内的点均不邻接,称G是一个l 部图。 4部图 定义2 如果在一个l 部图G中,任意部Vi中的每个顶点,和G中其它各部中的每个顶点均邻接,称G为完全l 部图。记作: 例如: K1, 2, 2 显然: 定义3 如果在一个n个点的完全 l 部图G中有: 则称G为n阶完全 l 几乎等部图,记为T l, n |V1| = |V2| = … = |Vl | 的完全 l 几乎等部图称为完 全 l 等部图。 定理1: 连通偶图的2部划分是唯一的。 证明 设连通偶图G的2部划分为V1∪V2 =V 。 取v∈V1 ,由于G 连通,对任何u∈V1∪V2 , G中有 联结u 和v的路,故d (v, u)有定义。 因为任何一条以v为起点的路交替地经过V1和V2 的点, 可知一个点u∈V2 当且仅当d (v, u)是奇数。这准则唯一地 决定了G的2部划分。 定理2: n阶完全偶图 Kn1,n2的边数m=n1n2,且有: 证明:m=n1n2显然。下面证明第二结论: 证明:首先有: 定理3 n阶l部图G有最多边数的充要条件是G ≌ Tl,n。 其次,考虑: 则 f 取最大值的充分必要条件为:1≦ij ≦l,有: 而G的对应的顶点划分形成的 l 部图正好为T l, n 从而证明了该定理。 (二)、托兰定理 定义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 相同的度序列,则: 证明:对 l 作数学归纳证明。 当 l =1时,结论显然成立; 设对 l t 时,结论成立。考虑 l = t 时的情况。 令u ∈V(G), 且d (u) = Δ(G). 设G1= G[N(u)],则G1不含Kt, 否则,G含Kt+1,矛盾! 由归纳假设,G1度弱于某个完全t-1部图H1. 又令V1=N (u) , V2=V-V1 , 用G2表示顶点集合为V2的空图,则G度弱于G2VG1,当然度弱于G2V H1。 令H= G2V H1,则H是完全t部图。 下面证明定理的第二个结论。 若G与H有相同的度序列,而H= G2V H1,所以,G与 G1VG2有相同的度序列。 由此可以推出: G= G1V G2 因为 G= G1V G2和H= G2V H1有相同度序列,于是得到G1和H1有相同度序列,所以: 定理5(Turán)若G是简单图,并且不包含 Kl+1,则: 仅当 时,有 证明:由定理4知:G度弱于某个完全 l 部图H。于是: 又由定理3知: 所以得: 下面证明定理5的后一论断。

文档评论(0)

junjun37473 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档