圖論課件-極圖理論簡(jiǎn)介.ppt

1、1,圖論及其應(yīng)用,應(yīng)用數(shù)學(xué)學(xué)院,2,第一章 圖的基本概念,本次課主要內(nèi)容,極圖理論簡(jiǎn)介,(一)、l 部圖的概念與特征,(二)、托蘭定理,(三)、托蘭定理的應(yīng)用,3,1978年，數(shù)學(xué)家Bollobas寫了一本書極值圖論(Extremal Graph）,是關(guān)于極值圖論問(wèn)題的經(jīng)典著作。,P. Erds是該研究領(lǐng)域的杰出人物。他是數(shù)學(xué)界的傳奇人物，國(guó)際圖論大師，獲過(guò)Wolf數(shù)學(xué)獎(jiǎng)。他是20世紀(jì)最偉大的數(shù)學(xué)家之一，也是人類歷史上發(fā)表數(shù)學(xué)論文最多的數(shù)學(xué)家(1000多篇),第二名是歐拉(837篇)。他于1996年9月20日因心臟病去世，享年83歲，他的逝世當(dāng)時(shí)驚動(dòng)了整個(gè)數(shù)學(xué)界。,極圖屬于極值圖論討論的范疇，

2、主要研究滿足某個(gè)條件下的最大圖或最小圖問(wèn)題。,上世紀(jì)70年代末，極值圖論已經(jīng)形成了相對(duì)完整的理論體系，但還有很多引人入勝的公開(kāi)性問(wèn)題沒(méi)有解決，所以，直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困難的數(shù)學(xué)研究方向之一。,4,本次課，主要介紹極值圖論中的一個(gè)經(jīng)典結(jié)論：托蘭定理。,(一)、l 部圖的概念與特征,定義1 若簡(jiǎn)單圖G的點(diǎn)集V有一個(gè)劃分：,且所有的Vi非空，Vi內(nèi)的點(diǎn)均不鄰接，稱G是一個(gè)l 部圖。,5,定義2 如果在一個(gè)l 部圖G中，任意部Vi中的每個(gè)頂點(diǎn)，和G中其它各部中的每個(gè)頂點(diǎn)均鄰接，稱G為完全l 部圖。記作：,例如：,顯然：,6,定義3 如果在一個(gè)n個(gè)點(diǎn)的完全 l 部圖G中有

3、：,則稱G為n階完全 l 幾乎等部圖，記為T l, n,|V1| = |V2| = = |Vl | 的完全 l 幾乎等部圖稱為完 全 l 等部圖。,定理1： 連通偶圖的2部劃分是唯一的。,證明 設(shè)連通偶圖G的2部劃分為V1V2 =V 。,7,取vV1 ，由于G 連通，對(duì)任何uV1V2 ， G中有,聯(lián)結(jié)u 和v的路，故d (v, u)有定義。,因?yàn)槿魏我粭l以v為起點(diǎn)的路交替地經(jīng)過(guò)V1和V2 的點(diǎn)， 可知一個(gè)點(diǎn)uV2 當(dāng)且僅當(dāng)d (v, u)是奇數(shù)。這準(zhǔn)則唯一地 決定了G的2部劃分。,定理2： n階完全偶圖 Kn1,n2的邊數(shù)m=n1n2,且有：,證明：m=n1n2顯然。下面證明第二結(jié)論：,8,證

4、明：首先有：,定理3 n階l部圖G有最多邊數(shù)的充要條件是G Tl,n。,其次，考慮：,則 f 取最大值的充分必要條件為：1ij l,有:,而G的對(duì)應(yīng)的頂點(diǎn)劃分形成的 l 部圖正好為T l, n,從而證明了該定理。,9,(二)、托蘭定理,定義4 設(shè)G和H是兩個(gè)n階圖，稱G度弱于H，如果存在雙射：V(G)V(H),使得：,注意：若G度弱于H，一定有：,但逆不成立！例如：(1,1,4,2)與(3,3,3,3)沒(méi)有度弱關(guān)系！,定理4 若n階簡(jiǎn)單圖G不包含Kl+1，則G度弱于某個(gè)完全 l 部圖 H，且若G具有與 H 相同的度序列，則:,10,證明：對(duì) l 作數(shù)學(xué)歸納證明。,當(dāng) l =1時(shí)，結(jié)論顯然成立；

5、,設(shè)對(duì) l t 時(shí)，結(jié)論成立。考慮 l = t 時(shí)的情況。,令u V(G), 且d (u) = (G).,設(shè)G1= GN(u),則G1不含Kt, 否則，G含Kt+1,矛盾！,由歸納假設(shè)，G1度弱于某個(gè)完全t-1部圖H1.,又令V1=N (u) , V2=V-V1 , 用G2表示頂點(diǎn)集合為V2的空?qǐng)D，則G度弱于G2VG1，當(dāng)然度弱于G2V H1。,令H= G2V H1,則H是完全t部圖。,下面證明定理的第二個(gè)結(jié)論。,11,若G與H有相同的度序列，而H= G2V H1,所以，G與 G1VG2有相同的度序列。,由此可以推出： G= G1V G2,因?yàn)?G= G1V G2和H= G2V H1有相同度序

6、列，于是得到G1和H1有相同度序列，所以：,定理5（Turn）若G是簡(jiǎn)單圖，并且不包含 Kl+1,則：,僅當(dāng) 時(shí)，有,12,證明：由定理4知：G度弱于某個(gè)完全 l 部圖H。于是：,又由定理3知：,所以得：,下面證明定理5的后一論斷。,13,如果,則有,G與H有相同度序列，由定理4：,又由 ，且由定理3，有：,所以有：,14,幾個(gè)有趣的相關(guān)結(jié)果：,設(shè)m (n, H)表示n階單圖中不含子圖H的最多邊數(shù)，則：,其中，,15,(三)、托蘭定理的應(yīng)用,問(wèn)題：工兵排雷問(wèn)題,一個(gè)小組n個(gè)人在一個(gè)平原地區(qū)執(zhí)行一項(xiàng)排雷任務(wù)。,其中任意的兩個(gè)人，若其距離不超過(guò)g米，則可用無(wú)線,電保持聯(lián)系；若發(fā)生觸雷意外，地雷的殺傷半徑為h米。,問(wèn)：在任意的兩個(gè)人之間均能保持聯(lián)系的條件下，平均,傷亡人數(shù)最低的可能值為多少？,分析：(1)為保持通信，排雷工兵相互之間距離不能超過(guò)g米。因此，他們必須分布在直徑是g米的圓形區(qū)域內(nèi).,16,(2) 若某人A觸雷，則與A的距離大于h米的人將是安,全的，但究竟哪個(gè)人會(huì)發(fā)生觸雷意外，事先是不知,道的，所以此問(wèn)題實(shí)際上是求在任意的兩個(gè)人之間,