圖論課件-極圖理論簡介.ppt

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

2、主要研究滿足某個條件下的最大圖或最小圖問題。,上世紀(jì)70年代末，極值圖論已經(jīng)形成了相對完整的理論體系，但還有很多引人入勝的公開性問題沒有解決，所以，直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困難的數(shù)學(xué)研究方向之一。,4,本次課，主要介紹極值圖論中的一個經(jīng)典結(jié)論：托蘭定理。,(一)、l 部圖的概念與特征,定義1 若簡單圖G的點集V有一個劃分：,且所有的Vi非空，Vi內(nèi)的點均不鄰接，稱G是一個l 部圖。,5,定義2 如果在一個l 部圖G中，任意部Vi中的每個頂點，和G中其它各部中的每個頂點均鄰接，稱G為完全l 部圖。記作：,例如：,顯然：,6,定義3 如果在一個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 連通，對任何uV1V2 ， G中有,聯(lián)結(jié)u 和v的路，故d (v, u)有定義。,因為任何一條以v為起點的路交替地經(jīng)過V1和V2 的點， 可知一個點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的對應(yīng)的頂點劃分形成的 l 部圖正好為T l, n,從而證明了該定理。,9,(二)、托蘭定理,定義4 設(shè)G和H是兩個n階圖，稱G度弱于H，如果存在雙射：V(G)V(H),使得：,注意：若G度弱于H，一定有：,但逆不成立！例如：(1,1,4,2)與(3,3,3,3)沒有度弱關(guān)系！,定理4 若n階簡單圖G不包含Kl+1，則G度弱于某個完全 l 部圖 H，且若G具有與 H 相同的度序列，則:,10,證明：對 l 作數(shù)學(xué)歸納證明。,當(dāng) l =1時，結(jié)論顯然成立；

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

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