圖論及其應用-課件-全

1、1 圖論及其應用任課教師：楊春數(shù)學科學學院1 圖論及其應用任課教師：楊春數(shù)學科學學院2圖論及其應用 作者: 張先迪、李正良 購買地點：教材科2圖論及其應用3參考文獻1 美，幫迪圖論及其應用2 美，Gary Chartrand圖論導引，人民郵電出版社，20073 Bela Bollobas，現(xiàn)代圖論，科學出版社，2019 中國科學院研究生教學叢書4 美，F(xiàn)red Buckley圖論簡明教程，清華大學出版社，2005 李慧霸 王風芹譯3參考文獻1 美，幫迪圖論及其應用45 李尉萱，圖論，湖南科學技術出版社，19796 美，Douglas B.West圖論導引，機械工業(yè)出版社，2007 李建中，駱吉

2、洲譯7 楊洪，圖論常用算法選編，中國鐵道出版社，19888 陳樹柏，網(wǎng)絡圖論及其應用，科學出版社，198245 李尉萱，圖論，湖南科學技術出版社，197959 Chris Godsil，Gordon Royle Algebraic Graph Theory，世界圖書出版公司北京公司，201910 王朝瑞，圖論，高等教育出版社，198359 Chris Godsil，Gordon Royle6第一章 圖的基本概念本次課主要內(nèi)容圖的概念與圖論模型(一)、圖論課程簡介(二)、圖的定義與圖論模型(三)、圖的同構6第一章 圖的基本概念本次課主要內(nèi)容圖的概念與圖論模型(一)71、研究對象 圖論是研究點與線

3、組成的“圖形”問題的一門科學。屬于應用數(shù)學分支.(一)、圖論課程簡介2、發(fā)展歷史 圖論起源于18世紀的1736年，標志事件是“哥尼斯堡七橋問題.數(shù)學家歐拉被稱為“圖論之父”.20世紀30年代出版第一本圖論著作.71、研究對象 圖論是研究點與線組成的“圖形”問題的83、應用狀況 圖論的應用已經(jīng)涵蓋了人類學、計算機科學、化學、環(huán)境保護、非線性物理、心理學、社會學、交通管理、電信以及數(shù)學本身等。 目前，圖論已形成很多分支：如隨機圖論、網(wǎng)絡圖論、代數(shù)圖論、拓撲圖論、極值圖論等。4、教學安排 主要介紹圖的一些基本概念、基本理論和圖論的典型應用。60學時。83、應用狀況 圖論的應用已經(jīng)涵蓋了人類學、計算機

4、科91、圖的定義(二)、圖的定義與圖論模型 一個圖是一個序偶，記為G=(V,E),其中：(1) V是一個有限的非空集合，稱為頂點集合,其元素稱為頂點或點。用|V|表示頂點數(shù)；(2) E是由V中的點組成的無序?qū)嫵傻募?，稱為邊集，其元素稱為邊，且同一點對在E中可以重復出現(xiàn)多次。用|E|表示邊數(shù)。91、圖的定義(二)、圖的定義與圖論模型 一個圖是一個序偶10圖可以用圖形表示：V中的元素用平面上一個黑點表示，E中的元素用一條連接V中相應點對的任意形狀的線表示。例1、設圖G。這里Vv1,v2,v3,v4Ee1,e2,e3,e4,e5,e6，e1(v1,v2)，e2(v1,v3)，e3(v1,v4)，

5、e4(v2,v3)，e5(v3,v2)，e6(v3,v3)。v1v2v3v4e1e2e3e4e5e610圖可以用圖形表示：V中的元素用平面上一個黑點表示，E例111圖的相關概念：有限圖：頂點集和邊集都有限的圖稱為有限圖；平凡圖：只有一個頂點的圖稱為平凡圖；空圖：邊集為空的圖稱為空圖；n階圖：頂點數(shù)為n的圖稱為n階圖；(n, m) 圖：頂點數(shù)為n,邊數(shù)為m的圖稱為(n, m) 圖；邊的重數(shù)：連接兩個相同頂點的邊的條數(shù)稱為邊的重數(shù)；重數(shù)大于1的邊稱為重邊；環(huán)：端點重合為一點的邊稱為環(huán)；簡單圖：無環(huán)無重邊的圖稱為簡單圖；其余的圖稱為復合圖；11圖的相關概念：有限圖：頂點集和邊集都有限的圖稱為有限圖；

6、12頂點u與v相鄰接：頂點u與v間有邊相連接；其中u與v稱為該邊的兩個端點；頂點u與邊e相關聯(lián)：頂點u是邊e的端點；邊e1與邊e2相鄰接：邊e1與邊e2有公共端點；2、圖論模型為了抽象和簡化現(xiàn)實世界，常建立數(shù)學模型。圖是關系的數(shù)學表示，為了深刻理解事物之間的聯(lián)系，圖是常用的數(shù)學模型。(1) 化學中的圖論模型19世紀，化學家凱萊用圖論研究簡單烴即碳氫化合物12頂點u與v相鄰接：頂點u與v間有邊相連接；其中u與v稱為13用點抽象分子式中的碳原子和氫原子，用邊抽象原子間的化學鍵。通過這樣的建模，能很好研究簡單烴的同分異構現(xiàn)象.例如：C4H10的兩種同分異構結構圖模型為：hhhhhhhhhhhhhhh

7、hhhhh13用點抽象分子式中的碳原子和氫原子，用邊抽象原子間通過這樣14(2) 商業(yè)中的圖論模型商業(yè)中，經(jīng)常用圖來對倉庫和零售店進行建模例如：令V=w1,w2,w3,r1,r2,r3,r4,r5代表3個倉庫和5個零售點E=w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5代表每個倉庫和每個零售店間的關聯(lián)。則圖模型圖形為：w1r1r2w2r3r4w3r5(3) 最短航線問題14(2) 商業(yè)中的圖論模型商業(yè)中，經(jīng)常用圖來對倉庫和零售店15用點表示城市，兩點連線當且僅當兩城市有航線。為了求出兩城市間最短航線，需要在線的旁邊注明距離值。例如：令V=a, b, c, d,

8、 e代表5個城市E=a b, ad, b c , be, de代表城市間的直達航線則航線圖的圖形為：abcde500320140430370請求出從d到c的最短路15用點表示城市，兩點連線當且僅當兩城市有航線。為了例如：令16(4) 任務分配問題 有一個旅行團要組織一批人去旅游，其中一些人是朋友他們要乘坐公共汽車去，而車上的位子是成對的。因此為了讓大家旅途更愉快，旅行團負責人需要將成對的朋友安排在一起。給出一種安排方案。 該問題可以建立一個圖論模型來解決：旅行團的人抽象為圖的頂點，兩個頂點連線，當且僅當兩個頂點代表的人是朋友。 問題歸結于在模型圖中求所謂的“匹配”，關于圖的匹配將在第五章介紹。

9、16(4) 任務分配問題 有一個旅行團要組織一批人17(5) 考試時間安排問題 一個教授需要對期末考試時間進行安排，使得學生們不會有相互沖突的考試。如何解決？ 該問題可以建立一個圖論模型來解決：待考的課程可抽象為圖的頂點，連接兩個頂點的邊表示至少有一個學生同時選擇了這兩門課程。 問題歸結于在模型圖中求所謂的“頂點著色方案”問題，該問題將在第七章討論。 例如：有a, b, c ,d, e, f 六門課程。按照上面方法建立的模型圖如下：17(5) 考試時間安排問題 一個教授需要對期末考18 一種可行的安排方案為：第一時間：a, d, e;第二時間：b, f ；最后：c.abcefd 另一種可行的安

10、排方案為：第一時間：a, e;第二時間：c, d ；最后：b, f .(6) 旅行售貨員問題 一電腦代理商要從她所在城市出發(fā)，乘飛機去六個城市，然后回到出發(fā)點，如果要求每個城市只經(jīng)歷一次，能否辦到？給出行走方案。18 一種可行的安排方案為：第一時間：a, d, e19 問題歸結為在模型圖中尋求所謂的“哈密爾頓圈”問題。將在第四章介紹。 例如：如果模型圖如下： 該問題可以建立一個圖論模型來解決：城市抽象為圖的頂點，邊代表城市間的直達航線。abcdef 可行方案: (1) h, d, e, c, b, a, h (2) h, d, e, c, a, b, h19 問題歸結為在模型圖中尋求所謂的“哈

11、密爾頓圈”問題20 在圖論中，一個很值得研究的問題是如何比較兩個圖的異同，這就是圖的同構問題。 定義：設有兩個圖G1=(V1,E1)和G2=(V2,E2),若在其頂點集合間存在雙射，使得邊之間存在如下關系：設u1u2v1v2, u1,v1 V1, u2,v2 V2; u1v1 E1,當且僅當u2v2 E2,且u1v1與u2v2的重數(shù)相同。稱G1與G2同構，記為： 由定義可以得到圖同構的幾個必要條件：(三)、圖的同構 (1) 頂點數(shù)相同；(2) 邊數(shù)相同；(3) 關聯(lián)邊數(shù)相同的頂點個數(shù)相同。20 在圖論中，一個很值得研究的問題是如何比較兩個 21 判定圖的同構是很困難的，屬于NP完全問題。對于規(guī)

12、模不大的兩個圖，判定其是否同構，可以采用觀察加推證的方法。 例2 證明下面兩圖不同構。u1v1證明:u1的兩個鄰接點與v1的兩個鄰接點狀況不同。所以，兩圖不同構。21 判定圖的同構是很困難的，屬于NP完全問題。對于22 例3 證明下面兩圖同構。證明:作映射f : vi ui (i=1,2.10)容易證明，對vi v j E (a),有f (v i vj,),ui,uj,E,(b) (1 i 10, 1j 10 )由圖的同構定義知，圖(a)與(b)是同構的。22 例3 證明下面兩圖同構。證明:作映射f : vi 23 例4 指出4個頂點的非同構的所有簡單圖。分析：四個頂點的簡單圖最少邊數(shù)為0，最

13、多邊數(shù)為6，所以可按邊數(shù)進行枚舉。23 例4 指出4個頂點的非同構的所有簡單圖。分析：四個頂點24作業(yè)P29P30 3, 4, 5, 624作業(yè)P29P30 3, 4, 5, 625Thank You !25Thank You !26第一章 圖的基本概念本次課主要內(nèi)容(二)、頂點的度與圖的度序列(一)、完全圖、偶圖與補圖26第一章 圖的基本概念本次課主要內(nèi)容(二)、頂點的度與圖的27(一)、完全圖、偶圖與補圖1、每兩個不同的頂點之間都有一條邊相連的簡單圖稱為完全圖 .在同構意義下，n個頂點的完全圖只有一個，記為 KnK2K3K5容易求出：27(一)、完全圖、偶圖與補圖1、每兩個不同的頂點之間都

14、有一28 2、所謂具有二分類（X, Y）的偶圖（或二部圖）是指一個圖，它的點集可以分解為兩個(非空)子集X和Y，使得每條邊的一個端點在X中，另一個端點在Y中. 完全偶圖是指具有二分類（X, Y）的簡單偶圖，其中X的每個頂點與Y的每個頂點相連，若|X|=m，|Y|=n，則這樣的偶圖記為 K m, n 圖1圖2 圖1與圖2均是偶圖，圖2是K2,328 2、所謂具有二分類（X, Y）的偶圖（或二部圖）是指一29 偶圖是一種常見數(shù)學模型。 例1 學校有6位教師將開設6門課程。六位教師的代號是xi（i=1,2,3,4,5,6)，六門課程代號是yi （i=1,2,3,4,5,6)。已知，教師x1能夠勝任課

15、程y2和y3；教師x2能夠勝任課程y4和y5；教師x3能夠勝任課程y2；教師x4能夠勝任課程y6和y3；教師x5能夠勝任課程y1和y6；教師x6能夠勝任課程y5和y6。請畫出老師和課程之間的狀態(tài)圖。x1x5x4x3x2x6y4y3y1y2y5y629 偶圖是一種常見數(shù)學模型。 例1 學303、對于一個簡單圖G =（V, E），令集合則稱圖H =（V，E1E）為G的補圖，記為 例如，下面兩個圖互為補圖。G1G2303、對于一個簡單圖G =（V, E），令集合則稱圖H =31定理：若n階圖G是自補圖( ),則有：證明：n階圖G是自補圖，則有：補圖是相對于完全圖定義的。補圖是圖論中經(jīng)常涉及的概念，在

16、圖論研究中有重要的作用如果圖G與其補圖同構，則稱G為自補圖。31定理：若n階圖G是自補圖( 32所以：由于n是正整數(shù)，所以： 自補圖是很有意義的圖類。它在對角型拉姆齊數(shù)方面的研究、關于圖的香農(nóng)容量的研究、強完美圖方面的研究等都有重要作用。32所以：由于n是正整數(shù)，所以： 自補圖是很有意義33(二)、頂點的度與圖的度序列G的頂點v的度d (v)是指G中與v關聯(lián)的邊的數(shù)目，每個環(huán)計算兩次。 1、頂點的度及其性質(zhì)分別用(G)和(G)表示圖G的最小與最大度。 例2 在10個頂點以下的單圖中，哪些階數(shù)的圖可能為自補圖？畫出8階的4個自補圖(共10個)。33(二)、頂點的度與圖的度序列G的頂點v的度d (

17、v)是指34奇數(shù)度的頂點稱為奇點，偶數(shù)度的頂點稱偶點。 設G = (V, E)為簡單圖，如果對所有 ，有d (v) = k，稱圖G為k-正則圖 定理： 圖G= (V, E)中所有頂點的度的和等于邊數(shù)m的2倍，即：證明：由頂點度的定義知：圖中每條邊給圖的總度數(shù)貢獻2度，所以，總度數(shù)等于邊數(shù)2倍。注：該定理稱為圖論第一定理，是由歐拉提出的。歐拉一身發(fā)表論文886篇，著作90部。該定理還有一個名字：“握手定理”。34奇數(shù)度的頂點稱為奇點，偶數(shù)度的頂點稱偶點。 設G = (35推論1 在任何圖中，奇點個數(shù)為偶數(shù)。證明：設V1,V2分別是G中奇點集和偶點集.則由握手定理有：是偶數(shù)，由于 是偶數(shù)， 所以

18、是偶數(shù)，于是 是偶數(shù)。推論2 正則圖的階數(shù)和度數(shù)不同時為奇數(shù) 。證明 ： 設G是k-正則圖，若k為奇數(shù)，則由推論1知正則圖G的點數(shù)必為偶數(shù) 例4 與是簡單圖G的最大度與最小度，求證： 35推論1 在任何圖中，奇點個數(shù)為偶數(shù)。證明：設V1,V236證明：由握手定理有：所以有：2、圖的度序列及其性質(zhì)一個圖G的各個點的度d1, d2, dn構成的非負整數(shù)組 (d1, d2, dn)稱為G的度序列 。任意一個圖G對應唯一一個度序列，圖的度序列是刻畫圖的特征的重要“拓撲不變量”。36證明：由握手定理有：所以有：2、圖的度序列及其性質(zhì)一個圖37 圖G 的“拓撲不變量”是指與圖G有關的一個數(shù)或數(shù)組(向量)。

19、它對于與圖G同構的所有圖來說，不會發(fā)生改變。 一個圖G可以對應很多拓撲不變量。如果某組不變量可完全決定一個圖，稱它為不變量的完全集。定理：非負整數(shù)組(d1,d2,., d n)是圖的度序列的充分必要條件是： 為偶數(shù)。證明：必要性由握手定理立即得到。如果 為偶數(shù)，則數(shù)組中為奇數(shù)的數(shù)字個數(shù)必為偶數(shù)。按照如下方式作圖G:若di為偶數(shù)，則在與之對應的點作di/2個環(huán)；對于剩下的偶數(shù)個奇數(shù)，37 圖G 的“拓撲不變量”是指與圖G有關的一個數(shù)38兩兩配對后分別在每配對點間先連一條邊，然后在每個頂點畫dj-1/2個環(huán)。該圖的度序列就是已知數(shù)組。一個非負數(shù)組如果是某簡單圖的度序列，我們稱它為可圖序列，簡稱圖序

20、列。關于圖序列，主要研究3個問題：(1) 存在問題：什么樣的整數(shù)組是圖序列？(2) 計數(shù)問題：一個圖序列對應多少不同構的圖？(3) 構造問題：如何畫出圖序列對應的所有不同構圖？研究現(xiàn)狀: (1)徹底解決了，(2)解決得不好，(3)沒有解決。38兩兩配對后分別在每配對點間先連一條邊，然后一個非負數(shù)組如39定理：非負整數(shù)組是圖序列的充分必要條件是：是圖序列。39定理：非負整數(shù)組是圖序列的充分必要條件是：是圖序列。40例5 是否為圖序列？如果是，作出對應的一個簡單圖。 解：由于 是圖序列，所以原序列是圖序列。40例5 41定理: (厄多斯1960)非負整數(shù)組是圖序列的充分必要條件是：該定理證明很難！

21、上世紀60年代以來，人們又研究所謂的唯一圖序列問題。例5就是一個唯一圖序列！41定理: (厄多斯1960)非負整數(shù)組是圖序列的充分必要條42定理: 一個滿足d2=dn-1的圖序列是唯一圖序列的充分必要條件是下列條件之一滿足：42定理: 一個滿足d2=dn-1的圖序列是唯一圖序列的充分433、圖的頻序列及其性質(zhì)定理： 一個簡單圖G的n個點的度不能互不相同 證明： 因為圖G為簡單圖，所以：(G)n-1。 情形1：若G沒有孤立點，則 由鴿籠原理：必有兩頂點度數(shù)相同；情形2：若G只有一個孤立點，設G1表示G去掉孤立點后的部分，則：由鴿籠原理：在G1里必有兩頂點度數(shù)相同；情形3：若G只有兩個以上的孤立點

22、，則定理顯然成立。433、圖的頻序列及其性質(zhì)定理： 一個簡單圖G的n個點的度44定義： 設n階圖G的各點的度取s個不同的非負整數(shù)d1,d2, ds。又設度為di的點有bi個 (i = 1,2,s)，則 故非整數(shù)組(b1,b2, bs)是n的一個劃分，稱為G的頻序列。定理： 一個n階圖G和它的補圖有相同的頻序列。44定義： 設n階圖G的各點的度取s個不同的非負整數(shù)故非整45作業(yè)P29P30 8, 9, 10, 1145作業(yè)P29P30 8, 9, 10, 1146Thank You !46Thank You !47第一章 圖的基本概念本次課主要內(nèi)容子圖、圖運算、路與連通性(一)、子圖的相關概念(

23、三)、路與連通性(二)、圖運算47第一章 圖的基本概念本次課主要內(nèi)容子圖、圖運算、路與連通481、子圖簡單地說，圖G的任意一部分(包括本身)都稱為是圖G的的一個子圖。定義1 如果(一)、子圖的相關概念且H中邊的重數(shù)不超過G中對應邊的條數(shù)，則稱H為G的子圖，記為當 時，稱H是G的真子圖，記為 481、子圖簡單地說，圖G的任意一部分(包括本身)都稱為是圖492、點與邊的導出子圖(1) 圖G的頂點導出子圖定義2 如果 ，則以 為頂點集，以兩個端點均在 中的邊集組成的圖，稱為圖G的點導出子圖。記為：例1 如圖所示，求 。其中12345圖G492、點與邊的導出子圖(1) 圖G的頂點導出子圖定義2 如50

24、解：由點導出子圖的定義得：135(2) 圖G的邊導出子圖定義3 如果 ，則以 為邊集，以 中邊的所有端點為頂點集組成的圖，稱為圖G的邊導出子圖。記為：例2 如圖所示，求 。其中50解：由點導出子圖的定義得：135(2) 圖G的邊導出子圖51解：由邊導出子圖的定義得：12345圖G1234551解：由邊導出子圖的定義得：12345圖G12345523、圖的生成子圖定義3 如果圖G的一個子圖包含G的所有頂點，稱該子圖為G的一個生成子圖例2 如圖所示，求G的所有生成子圖123圖G解：按邊數(shù)分別求出523、圖的生成子圖定義3 如果圖G的一個子圖包含G的所有頂53定理：簡單圖G=(n,m)的所有生成子圖

25、個數(shù)為2m(二)、圖運算 在圖論中，將兩個或更多的圖按照某種方式合并，或者對一個圖作某種形式的操作，可以得到很有意義的新圖。將圖合并或?qū)σ粋€圖進行操作，稱為圖運算。圖運算形式很多。1、圖的刪點、刪邊運算(1)、圖的刪點運算設 ，在G中刪去 中的頂點和G中與之關聯(lián)的所有邊的操作，稱為刪點運算。記為特別地，如果只刪去一個點v，則記為G-v.53定理：簡單圖G=(n,m)的所有生成子圖個數(shù)為2m(二)54(2)、圖的刪邊運算設 ，在G中刪去 中的所有邊的操作，稱為刪邊運算。記為特別地，如果只刪去一條邊e，則記為G-e.注：刪點、刪邊后得到的圖是原圖的子圖。2、圖的并運算 設G1,G2是G的兩個子圖，

26、G1與G2并是指由 為頂點集，以 為邊集組成的子圖。記為： 特別是，如果G1,G2不相交(沒有公共頂點)，稱它們的并為直接并，可以記為：54(2)、圖的刪邊運算設 552、圖的交運算 設G1,G2是G的兩個子圖，G1與G2交是指由 為頂點集，以 為邊集組成的子圖。記為： 設G1,G2是兩個圖，G1與G2的差是指從G1中刪去G2中的邊得到的新圖。記為G1-G2.3、圖的差運算4、圖的對稱差運算(或環(huán)和運算) 設G1,G2是兩個圖，G1與G2的對稱差定義為：552、圖的交運算 設G1,G2是G的兩個子圖，G1與56例3 已知G1與G2，求1234abcdefG1h2354cdegijG2解：由相應

27、運算定義得下面結果：1234abcdef5hgij234cde56例3 已知G1與G2，求1234abcdefG1h23557123abfh2354gij1234abf5hgij57123abfh2354gij1234abf5hgij585、圖的聯(lián)運算 設G1,G2是兩個不相交的圖，作G1+G2，并且將G1中每個頂點和G2中的每個頂點連接，這樣得到的新圖稱為G1與G2的聯(lián)圖。記為 ：例4 已知G1與G2，求21G1345G2解：由聯(lián)圖的定義得：21345585、圖的聯(lián)運算 設G1,G2是兩個不相交的圖，作G596、圖的積圖 設 是兩個圖。對點集 的任意兩個點u=(u1,u2)與v=(v1,v2

28、),當(u1=v1和u2adjv2)或(u2=v2和u1adjv1)時，把u與v相連。如此得到的新圖稱為G1與G2的積圖。記為 例5 已知G1與G2，畫G112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)596、圖的積圖 設 606、圖的合成圖 設 是兩個圖。對點集 的任意兩個點u=(u1,u2)與v=(v1,v2),當(u1adjv1)或(u1=v1和u2adjv2)時，把u與v相連。如此得到的新圖稱為G1與G2的合成圖。記為 例6 已知G1與G2，畫G112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)606、圖的合成圖 設 61 圖的積運

29、算是網(wǎng)絡構造的常用方法。并行計算機中的網(wǎng)絡拓撲常采用所謂的“超立方體”結構。采用該結構可使網(wǎng)絡具有較好的可靠性、較小的通信延遲和很好的可擴展性以及便于并行編程等優(yōu)點。 “超立方體”可以采用積圖來遞歸構造。定義如下： (1) 1方體 (2) n方體定義為：Q1Q3Q2 “超立方體”常采用下面簡單的遞歸構造方法：61 圖的積運算是網(wǎng)絡構造的常用方法。并行計算機中的網(wǎng)62 n方體Q n的頂點可用一個長度為n的二進制碼來表示。Q n的頂點數(shù)目正好等于2n個。 由n-1方體Q n-1構造Q n的方法是：將Q n-1拷貝一個。將原Q n-1每個頂點的碼前再添加一個零，將拷貝得來的n-1方體每個頂點的碼前面

30、再添加一個1。然后在兩個n-1方體之間連線：當且僅當兩個頂點碼只有一位對應位數(shù)字不同時，該兩點連線。如此得到的圖即為n方體。 關于n方體Q n的性質(zhì)研究，可以查閱到很多文獻。經(jīng)典文章是：Saad Y, Schultz M H. Topological properties of hypercubes J. IEEETrans. Comput . 1988, 37(7) : 867-8727、圖的聯(lián)合 把G1的一個頂點和G2的一個頂點粘合在一起后得到的新圖稱為G1與G2的聯(lián)合。記為：62 n方體Q n的頂點可用一個長度為n的二進制碼來表63(三)、路與連通性 對圖的路與連通性進行研究，在計算機網(wǎng)

31、絡研究中有十分重要的意義。因為網(wǎng)絡的抽象就是一個圖。研究網(wǎng)絡信息傳遞，信息尋徑是主要問題之一，這恰對應于圖中路的研究；在網(wǎng)絡研究中，可靠性也是主要問題之一，它與圖的連通性問題相對應。1、路與連通性的相關概念(1)、圖中的途徑 G的一條途徑（或通道或通路）是指一個有限非空序列w= v0 e1 v1 e2 v2ek vk，它的項交替地為頂點和邊，使得 ，ei的端點是vi-1和vi. 途徑中邊數(shù)稱為途徑的長度；v0,vk分別稱為途徑的起點與終點，其余頂點稱為途徑的內(nèi)部點。(2)、圖中的跡 邊不重復的途徑稱為圖的一條跡。63(三)、路與連通性 對圖的路與連通性進行研究，在計64 圖中頂點u與v的距離：

32、u與v間最短路的長度稱為u與v間距離。記為d (u, v). 如果u與v間不存在路，定義d (u, v)=.(3)、圖中的路(4)、圖中兩頂點的距離注：起點與終點重合的途徑、跡、路分別稱為圖的閉途徑、閉跡 與圈。閉跡也稱為回路。長度為k的圈稱為k圈，k為奇數(shù)時稱為奇 圈，k為偶數(shù)時稱為偶圈。 頂點不重復的途徑稱為圖的一條路。(5)、圖中兩頂點的連通性 圖G中點u與v說是連通的，如果u與v間存在通路。否則稱u與v不連通。點的連通關系是等價關系。 如果圖G中任意兩點是連通的，稱G是連通圖，否則，稱G是非連通圖。非連通圖中每一個極大連通部分，稱為G的連通分支。G的連通分支的個數(shù)，稱為G的分支數(shù)，記為

33、64 圖中頂點u與v的距離：u與v間最短路的長度稱為u與v間65(6)、圖的直徑 連通圖G的直徑定義為： 如果G不連通，圖G的直徑定義為 例7 證明：在n階連通圖中 (1) 至少有n-1條邊； (2) 如果邊數(shù)大于n-1，則至少有一條閉跡； (3) 如果恰有n-1條邊，則至少有一個奇度點。65(6)、圖的直徑 連通圖G的直徑定義為： 如果G不連通，66證明： (1) 由于G連通，所以，存在如下形式的途徑： 顯然該途徑至少含有n-1條邊。(v1,v2, , v n是G的n個不同頂點) (2) 考慮G中途徑： 若W是路，則長為n-1;但由于G的邊數(shù)大于n-1,因此，存在vi與vj,它們相異，但鄰接

34、。于是： 為G中一閉途徑，于是也就存在閉跡。66證明： (1) 由于G連通，所以，存在如下形式的途徑： 67 (3) 若不然，G中頂點度數(shù)至少為2，于是由握手定理： 這與G中恰有n-1條邊矛盾！ 例8 證明：若2，則G中必然含有圈。 證明：只就連通圖證明即可！設W=v1v2.vk-1vk是G中的一條最長路。由于2，所以vk必然有相異于vk-1的鄰接頂點。又W是G中最長路,所以，這樣的鄰接點必然是v1,v2,.,vk-2中之一。設該點為vm，則vmvm+1.v kvm為G中圈。67 (3) 若不然，G中頂點度數(shù)至少為2，于是由握手定理682、連通性性質(zhì) 定理1：若圖G不連通，則其補圖連通 證明：

35、對 ,如果u, v屬于G的同一分支，設w是與u, v處于不同分支中的點，則在G的補圖中，u與w, v與w分別鄰接，于是，u與v在G的補圖中是連通的。 如果u與v在G的兩個不同分支中，則在G的補圖中必然鄰接，因此，也連通。 所以，若G不連通，G的補圖是連通的。3、偶圖的判定定理682、連通性性質(zhì) 定理1：若圖G不連通，則其補圖連通 證69定理2 一個圖是偶圖當且當它不包含奇圈。證明： 必要性：設G是具有二分類（X, Y）的偶圖，并且C = v0 v1 vk v0是G的一個圈 不失一般性，可假定 。一般說來， 。又因為 ，所以 由此即得C是偶圈。 充分性：在G中任意選取點u, 定義V的分類如下：X

36、 = x | d (u, x) 是偶數(shù)，x V (G)Y = y | d (u, y) 是奇數(shù)，y V (G)下面證明：對X中任意兩點v與w , v與w不鄰接！69定理2 一個圖是偶圖當且當它不包含奇圈。證明： 必要性70 設v與w是X中任意兩個頂點。P是一條最短(u , v)路 ，而Q是一條最短的(u, w)路。QPvuwu1 又設u1是P和Q的最后一個交點。由于P, Q是最短路，所以，P,Q中u到u1段長度相同，因此奇偶性相同。又P,Q的長均是偶數(shù)，所以，P,Q中u1v段和u1w段奇偶性相同。 如果v與w鄰接，則可得到奇圈，矛盾！70 設v與w是X中任意兩個頂點。P是一條最短(u , v)

37、71作業(yè)P29P30 13, 14, 20, 2271作業(yè)P29P30 13, 14, 20, 2272Thank You !72Thank You !73第一章 圖的基本概念本次課主要內(nèi)容最短路算法、圖的代數(shù)表示(一)、最短路算法(二)、圖的代數(shù)表示1、圖的鄰接矩陣2、圖的關聯(lián)矩陣73第一章 圖的基本概念本次課主要內(nèi)容最短路算法、圖的代數(shù)表741、相關概念(1) 賦權圖(一)、最短路算法 在圖G的每條邊上標上一個實數(shù)w (e)后, 稱G為邊賦權圖。被標上的實數(shù)稱為邊的權值。 若H是賦權圖G的一個子圖，稱 為子圖H的權值。 權值的意義是廣泛的?？梢员硎揪嚯x，可以表示交通運費，可以表示網(wǎng)絡流量，

38、在朋友關系圖甚至可以表示友誼深度。但都可以抽象為距離。741、相關概念(1) 賦權圖(一)、最短路算法 在75(2) 賦權圖中的最短路 設G為邊賦權圖。u與v是G中兩點，在連接u與v的所有路中，路中各邊權值之和最小的路，稱為u與v間的最短路。 解決某類問題的一組有窮規(guī)則，稱為算法。(3) 算法1) 好算法 算法總運算量是問題規(guī)模的多項式函數(shù)時，稱該算法為好算法。(問題規(guī)模：描述或表示問題需要的信息量) 算法中的運算包括算術運算、比較運算等。運算量用運算次數(shù)表示。2) 算法分析75(2) 賦權圖中的最短路 設G為邊賦權圖。u與v76 對算法進行分析，主要對時間復雜性進行分析。分析運算量和問題規(guī)模

39、之間的關系。2、最短路算法 1959年，旦捷希(Dantjig）發(fā)現(xiàn)了在賦權圖中求由點a到點b的最短路好算法，稱為頂點標號法。 t (an) : 點an的標號值，表示點 a1=a 到an的最短路長度 Ai =a1,a2, ., ai:已經(jīng)標號的頂點集合。 Ti : a1到ai的最短路上的邊集合算法敘述如下：76 對算法進行分析，主要對時間復雜性進行分析。分析運77(1) 記 a=a1 , t(a1) =0, A1= a1, T1= ;(2) 若已經(jīng)得到 Ai = a1,a2, ai , 且對于 1ni,已知t(an),對每一個an Ai , 求一點：使得：(3) 設有mi ，1mii ,而bm

40、i(i)是使 取最小值，令：(4) 若ai+1=b ,停止，否則，記 ,轉(2).77(1) 記 a=a1 , t(a1) =0, A1= 78時間復雜性分析： 對第i次循環(huán)：步驟(2)要進行i次比較運算，步驟(3)要進行i次加法與i次比較運算。所以，該次循環(huán)運算量為3i .所以，在最壞的情況下，運算量為n2級，是好算法。算法證明：定理1：算法中的函數(shù)t(ai)給出了a與ai的距離。證明：略78時間復雜性分析： 對第i次循環(huán)：步驟(2)要進行79例1 如圖所示，求點a到點b的距離。812614227924693av1v2v3v4v5v6b解 1. A1= a，t (a) = 0，T1 = 2.

41、 b1 (1)= v3 ;3. m1 = 1, a2 = v3 , t(v3) = t(a) + l(av3) = 1 (最小)， T2 =av3;79例1 如圖所示，求點a到點b的距離。812614227802. A2 =a, v3, b1 (2) =v1, b2 (2) =v2 ;3. m2 = 1, a3 = v1 , t(v1) = t(a) + l(av1) = 2 (最小)， T3 =av3, av1; 2. A3 =a, v3, v1, b1 (3) =v2, b2 (3) =v2 , b3 (3) =v4 ; 3. m3 = 3, a4 = v4 , t(v4) = t(v1)

42、 + l(v1v4) = 3 (最小)， T4 =av3, av1, v1v42. A4 = a, v3, v1, v4，b1 (4) = v2，b2 (4) = v2，b3 (4) = v2, b4 (4) = v5 ;3. m4 = 4, a5 = v5 , t(v5) = t(v4) + l(v4v5) = 6 (最小)， T5 =av3, av1, v1v4, v4v5 ;802. A2 =a, v3, b1 (2) =v1,812. A5 = a, v3, v1, v4, v5，b1 (5) = v2，b2 (5) = v2， b3 (5) = v2 , b4 (5) = v2, b

43、5 (5) = v2 ;3. m5 = 4, t(v2) = t(v4) + l(v4v2) = 7 (最小)， T6 =av3, av1, v1v4, v4v5, v4v2;2. A6 = a, v3, v1, v4, v5, v2, b2 (6) = v6, b4 (6) = b， b5 (6) = v6，b6 (6) = v6 ;3. m6 = 6, a7 = v6 , t(v6) = t(v2) + l(v2v6) = 9 (最小)， T7 =av3, av1, v1v4, v4v5, v4v2, v2v6 ;2. A7 = a, v3, v1, v4, v5, v2, v6, b4

44、(7) = b，b5 (7) =b， b7 (7) =b ;3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)， 812. A5 = a, v3, v1, v4, v5，82T8 =av3, av1, v1v4, v4v5, v4v2, v2v6, v6b;于是知a與b的距離 d (a, b) = t (b) = 11 由T8導出的a到b的最短路為：課外作業(yè) 某公司在六個城市C1,C2,C3,C4,C5,C6中有分公司，從Ci到Cj的直接航程票價記在下述矩陣的(i, j)位置上，表示沒有直接航程。制作一張任意兩城市間的最便宜的路線表。82T8

45、 =av3, av1, v1v4, v4v5, v83例2 某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，分別為5升和3升。求最少的操作次數(shù)能均分酒。解：設x1,x2,x3分別表示8,5,3升酒壺中的酒量。則容易算出(x1,x2,x3) 的組合形式共24種。每種組合用一個點表示，兩點連線，當且僅當可通過倒酒的方式相互變換。若各邊賦權為1，則問題轉化為在該圖中求(8,0,0)到(4,4,0)的一條最短路。結果如下：83例2 某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，分別84例3 在一河岸有狼，羊和卷心菜。擺渡人要將它們渡過河去，由于船太小，每次只能載一樣東西。由于狼羊，羊卷心菜不能單獨相處。

46、問擺渡人至少要多少次才能將其渡過河？分析：人，狼，羊，菜所有組合形式為：但是以下組合不能允許出現(xiàn)：狼羊菜，羊菜，狼羊，人，人狼，人菜，共6種。岸上只能允許出現(xiàn)10種組合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。每種情況用點表示；84例3 在一河岸有狼，羊和卷心菜。擺渡人要將它們渡過河去，85兩點連線，當且僅當兩種情況可用載人(或加一物)的渡船相互轉變。于是，問題轉化為求由頂點“人狼羊菜”到頂點“空”的一條最短路。每條邊賦權為1結果為：人狼羊菜狼菜人狼菜狼人狼羊羊人羊空；(2) 人狼羊菜狼菜人狼菜菜人羊菜羊人羊空。85兩點連線，當且僅當兩種情況可用載人(或加一物)的渡船相互

47、86(二)、圖的代數(shù)表示 用鄰接矩陣或關聯(lián)矩陣表示圖，稱為圖的代數(shù)表示。用矩陣表示圖，主要有兩個優(yōu)點： (1) 能夠把圖輸入到計算機中；(2) 可以用代數(shù)方法研究圖論。1、圖的鄰接矩陣定義1 設G為n階圖，V=v1, v2, , vn,鄰接矩陣A(G)=(aij),其中：86(二)、圖的代數(shù)表示 用鄰接矩陣或關聯(lián)矩陣表示圖87例如：寫出下圖G的鄰接矩陣：解：鄰接矩陣為：1234圖G87例如：寫出下圖G的鄰接矩陣：解：鄰接矩陣為：1234圖G88圖G的鄰接矩陣的性質(zhì)(1)非負性與對稱性 由鄰接矩陣定義知aij是非負整數(shù)，即鄰接矩陣是非負整數(shù)矩陣； 在圖中點vi與vj鄰接，有vj與vi鄰接，即ai

48、j =aji.所以，鄰接矩陣是對稱矩陣。(2) 同一圖的不同形式的鄰接矩陣是相似矩陣。 這是因為，同圖的兩種不同形式矩陣可以通過交換行和相應的列變成一致。(3) 如果G為簡單圖，則A(G)為布爾矩陣;行和(列和)等于對應頂點的度數(shù)；矩陣元素總和為圖的總度數(shù)，也就是G的邊數(shù)的2倍。88圖G的鄰接矩陣的性質(zhì)(1)非負性與對稱性 由鄰接矩89(4) G連通的充分必要條件是：A(G)不能與如下矩陣相似證明：1) 必要性若不然：設A11對應的頂點是v1,v2, vk , A22對應的頂點為vk+1,vk+2, vn顯然，vi (1ik)與vj (k+1in)不鄰接，即G是非連通圖。矛盾！2) 充分性若不

49、然：設G1與G2是G的兩個不連通的部分，并且設V(G1)=v1,v2,vk, V(G2)=vk+1,vk+2,vn, 如果在寫89(4) G連通的充分必要條件是：A(G)不能與如下矩陣相90G的鄰接矩陣時，先排V(G1)中點，再排V(G2)中點，則G的鄰接矩陣形式必為：(5) 定理：設 ，則a ij (k)表示頂點vi到頂點vj的途徑長度為k的途徑條數(shù)。證明：對k作數(shù)學歸納法證明。當k=1時，由鄰接矩陣的定義，結論成立；設結論對k-1時成立。當為k時：一方面：先計算Ak ;90G的鄰接矩陣時，先排V(G1)中點，再排V(G2)中點，91另一方面：考慮vi到vj的長度為k的途徑設vm是vi到vj

50、的途徑中點，且該點和vj鄰接。則vi到vj的經(jīng)過vm且長度為k的途徑數(shù)目應該為：所以，vi到vj的長度為k的途徑數(shù)目為：即為例4 求下圖中v1到v3的途徑長度為2和3的條數(shù)。91另一方面：考慮vi到vj的長度為k的途徑設vm是vi到v92解：由于：v4v1v2v3所以，v1到v3的途徑長度為2和3的條數(shù)分別為：3和4。推論: (1)A2的元素aii (2)是vi的度數(shù)，A3的元素aii (3)是含vi的三角形個數(shù)的2倍；92解：由于：v4v1v2v3所以，v1到v3的途徑長度為293(2) 若G是連通的，對于i j , vi和vj間距離是使An的aij (n)0的最小整數(shù)。2、圖的關聯(lián)矩陣(1

51、) 若G是(n, m) 圖。定義G的關聯(lián)矩陣：其中：例如：e1v4v3v2v1e7e5e4e3e2e693(2) 若G是連通的，對于i j , vi和vj間距離94(2) 關聯(lián)矩陣的性質(zhì)1) 關聯(lián)矩陣的元素為0，1或2；2) 關聯(lián)矩陣的每列和為2；每行的和為對應頂點度數(shù)；94(2) 關聯(lián)矩陣的性質(zhì)1) 關聯(lián)矩陣的元素為0，1或2；95作業(yè)P29P30 1695作業(yè)P29P30 1696Thank You !96Thank You !97第一章 圖的基本概念本次課主要內(nèi)容鄰接譜與圖的鄰接代數(shù)(一)、鄰接譜(二)、圖的鄰接代數(shù)(三)、圖空間簡介97第一章 圖的基本概念本次課主要內(nèi)容鄰接譜與圖的鄰接

52、代數(shù)(98(一)、鄰接譜1、圖的特征多項式定義1：圖的鄰接矩陣A(G)的特征多項式：稱為圖G的特征多項式。例1、設單圖G的特征多項式為：求證: (1) a1=0 ; (2) a2= m (G) ;(3) a3是G中含有不同的K3子圖的個數(shù)2倍。98(一)、鄰接譜1、圖的特征多項式定義1：圖的鄰接矩陣A(99證明：由矩陣理論：對每個1in,(-1)iai是A(G)的所有i階主子式之和。(1) 由于A(G)的主對角元全為零，所以所有1階主子式全為零，即：a1=0 ;這樣的一個2階主子式對應G中的一條邊，反之亦然，所以，有：(2) 對于單圖G, A(G)中非零的2階主子式必為如下形式：99證明：由矩

53、陣理論：對每個1in,(-1)iai是A(100這樣的一個3階主子式對應G中的一個K3，反之亦然.設G中有S個K3, 則：(3) 對于單圖G, A(G)中非零的3階主子式必為如下形式：100這樣的一個3階主子式對應G中的一個K3，反之亦然.設G1012、圖的鄰接譜定義2：圖的鄰接矩陣A(G)的特征多項式的特征值及其重數(shù)，稱為G的鄰接譜。例2、求出K n的譜。解：K n的鄰接矩陣為：1012、圖的鄰接譜定義2：圖的鄰接矩陣A(G)的特征多項式102于是：102于是：103所以：例3，若兩個非同構的圖具有相同的譜，則稱它們是同譜圖。求證：下面兩圖是同譜圖。GH103所以：例3，若兩個非同構的圖具有

54、相同的譜，則稱它們是同104證明：G與H顯然不同構。通過直接計算：所以G與H是同譜圖。例4，設單圖A(G)的譜為：則：證明：由矩陣理論：104證明：G與H顯然不同構。通過直接計算：所以G與H是同譜105a ii (2)表示點vi的度數(shù)，由握手定理：即：例5，設是單圖G = (n, m)的任意特征值，則：證明：不失一般性，設=1，2，,n是G的全體特征值。G是單圖，有：105a ii (2)表示點vi的度數(shù)，由握手定理：即：例5106又由例4，有：對向量(1,1,1)與(2,3,4,n)用柯西不等式得：所以，有：由(1)與(2)得：106又由例4，有：對向量(1,1,1)與(2,3,107注：對

55、于圖譜的研究，開始于二十世紀60年代。形成了代數(shù)圖論的主要研究方向之一。圖譜研究在流體力學，量子化學，量子物理與非線性物理以及網(wǎng)絡技術中都有重要的應用。國內(nèi)，中國科技大學數(shù)學系是最早展開該課題研究的單位(1978年就有很好的研究成果)。他們對圖論的研究主要有兩個方面：一是圖譜問題，二是組合網(wǎng)絡研究，也有達到國際水平的研究成果(1994年開始).關于組合網(wǎng)絡問題，將在第三章作一些介紹。107注：對于圖譜的研究，開始于二十世紀60年代。形成了代數(shù)108(二)、圖的鄰接代數(shù)1、圖的鄰接代數(shù)的定義定義3：設A是無環(huán)圖G的鄰接矩陣，稱：對于矩陣的加法和數(shù)與矩陣的乘法來說作成數(shù)域C上的向量空間，稱該空間為

56、圖G的鄰接代數(shù)。注： 向量空間的定義可簡單地記為“非空”、“兩閉”、“八條” 2、圖的鄰接代數(shù)的維數(shù)特征108(二)、圖的鄰接代數(shù)1、圖的鄰接代數(shù)的定義定義3：設A109定理1：G為n階連通無環(huán)圖，則：證明：由哈密爾頓凱萊定理(見北大數(shù)學力學系高等代數(shù))：所以：下面證明：E, A, A2, , A d (G)線性無關！若不然，則存在不全為零的數(shù)a0 ,a1 , , a d (G) ,使：109定理1：G為n階連通無環(huán)圖，則：證明：由哈密爾頓凱萊110設a m-10 , 但當k m 時，有a k =0. 于是有：假定：v1 v2 v d(G)+1 是G中一條最短的 (v1, v d(G)+1)路

57、，易知：d (G) n.于是，d(v1, v m ) = m-1 , (m=1, 2, , d (G)+1)注意到：A k的元素a1m (k)在 k 0所以， 的一行m列元為am-1a1m (m-1)0，這樣有：110設a m-10 , 但當k m 時，有a k =111產(chǎn)生矛盾！定理結果分析：不等式右端的界是緊的！因為：n點路的直徑為n-1, 所以，此時該路的鄰接代數(shù)的維數(shù)正好為n。此外：當G為K n時，有：111產(chǎn)生矛盾！定理結果分析：不等式右端的界是緊的！因為：n112定理2：集合：對于圖的對稱差運算和數(shù)乘運算：(三)、圖空間簡介來說作成數(shù)域 F = 0, 1 上的m維向量空間。注：圖空

58、間概念是網(wǎng)絡圖論中的一個基本概念。研究通信網(wǎng)絡，如果要用圖論方法，建議參看陳樹柏的網(wǎng)絡圖論及其應用，科學出版社，1982年。學習網(wǎng)絡圖論的主要基礎是電工學與矩陣理論知識。112定理2：集合：對于圖的對稱差運算和數(shù)乘運算：(三)、圖113證明: (1) 證明M是F上的向量空間，只需要驗證“兩閉”與“八條”即可。(2) M的維數(shù)為m令又令：可以證明：g1,g2,gm為M的一組基！事實上：對若E(Gi)=ei1,ei2,eik,則：113證明: (1) 證明M是F上的向量空間，只需要驗證“兩114另一方面：若則：c1=c2= = cm =0所以：114另一方面：若則：c1=c2= = cm =0所以

59、：115作業(yè)設G是一個r度正則圖，證明：r是G的的一個特征值；(2) 特征值r的重數(shù)等于G的連通分支數(shù)；(3) G的任意特征值滿足：115作業(yè)設G是一個r度正則圖，證明：r是G的的一個特征值；116Thank You !116Thank You !117第一章 圖的基本概念本次課主要內(nèi)容極圖理論簡介(一)、l 部圖的概念與特征(二)、托蘭定理(三)、托蘭定理的應用(四)、交圖與團圖簡介117第一章 圖的基本概念本次課主要內(nèi)容極圖理論簡介(一)、118 1978年，數(shù)學家Bollobas寫了一本書極值圖論(Extremal Graph）,是關于極值圖論問題的經(jīng)典著作。 P. Erds是該研究領域

60、的杰出人物。他是數(shù)學界的傳奇人物，國際圖論大師，獲過Wolf數(shù)學獎。他是20世紀最偉大的數(shù)學家之一，也是人類歷史上發(fā)表數(shù)學論文最多的數(shù)學家(1000多篇),第二名是歐拉(837篇)。他于2019年9月20日因心臟病去世，享年83歲，他的逝世當時驚動了整個數(shù)學界。 極圖屬于極值圖論討論的范疇，主要研究滿足某個條件下的最大圖或最小圖問題。 上世紀70年代末，極值圖論已經(jīng)形成了相對完整的理論體系，但還有很多引人入勝的公開性問題沒有解決，所以，直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困難的數(shù)學研究方向之一。118 1978年，數(shù)學家Bollobas寫了一本書119 本次課，主要介紹極值圖論中