圖論及其應(yīng)用-課件-全

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

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

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

4、科91、圖的定義(二)、圖的定義與圖論模型 一個(gè)圖是一個(gè)序偶，記為G=(V,E),其中：(1) V是一個(gè)有限的非空集合，稱為頂點(diǎn)集合,其元素稱為頂點(diǎn)或點(diǎn)。用|V|表示頂點(diǎn)數(shù)；(2) E是由V中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對在E中可以重復(fù)出現(xiàn)多次。用|E|表示邊數(shù)。91、圖的定義(二)、圖的定義與圖論模型 一個(gè)圖是一個(gè)序偶10圖可以用圖形表示：V中的元素用平面上一個(gè)黑點(diǎn)表示，E中的元素用一條連接V中相應(yīng)點(diǎn)對的任意形狀的線表示。例1、設(shè)圖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中的元素用平面上一個(gè)黑點(diǎn)表示，E例111圖的相關(guān)概念：有限圖：頂點(diǎn)集和邊集都有限的圖稱為有限圖；平凡圖：只有一個(gè)頂點(diǎn)的圖稱為平凡圖；空圖：邊集為空的圖稱為空圖；n階圖：頂點(diǎn)數(shù)為n的圖稱為n階圖；(n, m) 圖：頂點(diǎn)數(shù)為n,邊數(shù)為m的圖稱為(n, m) 圖；邊的重?cái)?shù)：連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)稱為邊的重?cái)?shù)；重?cái)?shù)大于1的邊稱為重邊；環(huán)：端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)；簡單圖：無環(huán)無重邊的圖稱為簡單圖；其余的圖稱為復(fù)合圖；11圖的相關(guān)概念：有限圖：頂點(diǎn)集和邊集都有限的圖稱為有限圖；

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

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

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

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

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

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

12、模不大的兩個(gè)圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。 例2 證明下面兩圖不同構(gòu)。u1v1證明:u1的兩個(gè)鄰接點(diǎn)與v1的兩個(gè)鄰接點(diǎn)狀況不同。所以，兩圖不同構(gòu)。21 判定圖的同構(gòu)是很困難的，屬于NP完全問題。對于22 例3 證明下面兩圖同構(gòu)。證明:作映射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 )由圖的同構(gòu)定義知，圖(a)與(b)是同構(gòu)的。22 例3 證明下面兩圖同構(gòu)。證明:作映射f : vi 23 例4 指出4個(gè)頂點(diǎn)的非同構(gòu)的所有簡單圖。分析：四個(gè)頂點(diǎn)的簡單圖最少邊數(shù)為0，最

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

14、有一28 2、所謂具有二分類（X, Y）的偶圖（或二部圖）是指一個(gè)圖，它的點(diǎn)集可以分解為兩個(gè)(非空)子集X和Y，使得每條邊的一個(gè)端點(diǎn)在X中，另一個(gè)端點(diǎn)在Y中. 完全偶圖是指具有二分類（X, Y）的簡單偶圖，其中X的每個(gè)頂點(diǎn)與Y的每個(gè)頂點(diǎn)相連，若|X|=m，|Y|=n，則這樣的偶圖記為 K m, n 圖1圖2 圖1與圖2均是偶圖，圖2是K2,328 2、所謂具有二分類（X, Y）的偶圖（或二部圖）是指一29 偶圖是一種常見數(shù)學(xué)模型。 例1 學(xué)校有6位教師將開設(shè)6門課程。六位教師的代號(hào)是xi（i=1,2,3,4,5,6)，六門課程代號(hào)是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ù)學(xué)模型。 例1 學(xué)303、對于一個(gè)簡單圖G =（V, E），令集合則稱圖H =（V，E1E）為G的補(bǔ)圖，記為 例如，下面兩個(gè)圖互為補(bǔ)圖。G1G2303、對于一個(gè)簡單圖G =（V, E），令集合則稱圖H =31定理：若n階圖G是自補(bǔ)圖( ),則有：證明：n階圖G是自補(bǔ)圖，則有：補(bǔ)圖是相對于完全圖定義的。補(bǔ)圖是圖論中經(jīng)常涉及的概念，在

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

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

18、是偶數(shù)，于是 是偶數(shù)。推論2 正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù) 。證明 ： 設(shè)G是k-正則圖，若k為奇數(shù)，則由推論1知正則圖G的點(diǎn)數(shù)必為偶數(shù) 例4 與是簡單圖G的最大度與最小度，求證： 35推論1 在任何圖中，奇點(diǎn)個(gè)數(shù)為偶數(shù)。證明：設(shè)V1,V236證明：由握手定理有：所以有：2、圖的度序列及其性質(zhì)一個(gè)圖G的各個(gè)點(diǎn)的度d1, d2, dn構(gòu)成的非負(fù)整數(shù)組 (d1, d2, dn)稱為G的度序列 。任意一個(gè)圖G對應(yīng)唯一一個(gè)度序列，圖的度序列是刻畫圖的特征的重要“拓?fù)洳蛔兞俊薄?6證明：由握手定理有：所以有：2、圖的度序列及其性質(zhì)一個(gè)圖37 圖G 的“拓?fù)洳蛔兞俊笔侵概c圖G有關(guān)的一個(gè)數(shù)或數(shù)組(向量)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、 = x | d (u, x) 是偶數(shù)，x V (G)Y = y | d (u, y) 是奇數(shù)，y V (G)下面證明：對X中任意兩點(diǎn)v與w , v與w不鄰接！69定理2 一個(gè)圖是偶圖當(dāng)且當(dāng)它不包含奇圈。證明： 必要性70 設(shè)v與w是X中任意兩個(gè)頂點(diǎn)。P是一條最短(u , v)路 ，而Q是一條最短的(u, w)路。QPvuwu1 又設(shè)u1是P和Q的最后一個(gè)交點(diǎn)。由于P, Q是最短路，所以，P,Q中u到u1段長度相同，因此奇偶性相同。又P,Q的長均是偶數(shù)，所以，P,Q中u1v段和u1w段奇偶性相同。 如果v與w鄰接，則可得到奇圈，矛盾！70 設(shè)v與w是X中任意兩個(gè)頂點(diǎn)。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、圖的關(guān)聯(lián)矩陣73第一章 圖的基本概念本次課主要內(nèi)容最短路算法、圖的代數(shù)表741、相關(guān)概念(1) 賦權(quán)圖(一)、最短路算法 在圖G的每條邊上標(biāo)上一個(gè)實(shí)數(shù)w (e)后, 稱G為邊賦權(quán)圖。被標(biāo)上的實(shí)數(shù)稱為邊的權(quán)值。 若H是賦權(quán)圖G的一個(gè)子圖，稱 為子圖H的權(quán)值。 權(quán)值的意義是廣泛的?？梢员硎揪嚯x，可以表示交通運(yùn)費(fèi)，可以表示網(wǎng)絡(luò)流量，

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

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

40、i(i)是使 取最小值，令：(4) 若ai+1=b ,停止，否則，記 ,轉(zhuǎn)(2).77(1) 記 a=a1 , t(a1) =0, A1= 78時(shí)間復(fù)雜性分析： 對第i次循環(huán)：步驟(2)要進(jìn)行i次比較運(yùn)算，步驟(3)要進(jìn)行i次加法與i次比較運(yùn)算。所以，該次循環(huán)運(yùn)算量為3i .所以，在最壞的情況下，運(yùn)算量為n2級，是好算法。算法證明：定理1：算法中的函數(shù)t(ai)給出了a與ai的距離。證明：略78時(shí)間復(fù)雜性分析： 對第i次循環(huán)：步驟(2)要進(jìn)行79例1 如圖所示，求點(diǎn)a到點(diǎn)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 如圖所示，求點(diǎn)a到點(diǎn)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導(dǎo)出的a到b的最短路為：課外作業(yè) 某公司在六個(gè)城市C1,C2,C3,C4,C5,C6中有分公司，從Ci到Cj的直接航程票價(jià)記在下述矩陣的(i, j)位置上，表示沒有直接航程。制作一張任意兩城市間的最便宜的路線表。82T8

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

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

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

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

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

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

51、) 若G是(n, m) 圖。定義G的關(guān)聯(lián)矩陣：其中：例如：e1v4v3v2v1e7e5e4e3e2e693(2) 若G是連通的，對于i j , vi和vj間距離94(2) 關(guān)聯(lián)矩陣的性質(zhì)1) 關(guān)聯(lián)矩陣的元素為0，1或2；2) 關(guān)聯(lián)矩陣的每列和為2；每行的和為對應(yīng)頂點(diǎn)度數(shù)；94(2) 關(guān)聯(lián)矩陣的性質(zhì)1) 關(guān)聯(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、圖的特征多項(xiàng)式定義1：圖的鄰接矩陣A(G)的特征多項(xiàng)式：稱為圖G的特征多項(xiàng)式。例1、設(shè)單圖G的特征多項(xiàng)式為：求證: (1) a1=0 ; (2) a2= m (G) ;(3) a3是G中含有不同的K3子圖的個(gè)數(shù)2倍。98(一)、鄰接譜1、圖的特征多項(xiàng)式定義1：圖的鄰接矩陣A(99證明：由矩陣?yán)碚摚簩γ總€(gè)1in,(-1)iai是A(G)的所有i階主子式之和。(1) 由于A(G)的主對角元全為零，所以所有1階主子式全為零，即：a1=0 ;這樣的一個(gè)2階主子式對應(yīng)G中的一條邊，反之亦然，所以，有：(2) 對于單圖G, A(G)中非零的2階主子式必為如下形式：99證明：由矩

53、陣?yán)碚摚簩γ總€(gè)1in,(-1)iai是A(100這樣的一個(gè)3階主子式對應(yīng)G中的一個(gè)K3，反之亦然.設(shè)G中有S個(gè)K3, 則：(3) 對于單圖G, A(G)中非零的3階主子式必為如下形式：100這樣的一個(gè)3階主子式對應(yīng)G中的一個(gè)K3，反之亦然.設(shè)G1012、圖的鄰接譜定義2：圖的鄰接矩陣A(G)的特征多項(xiàng)式的特征值及其重?cái)?shù)，稱為G的鄰接譜。例2、求出K n的譜。解：K n的鄰接矩陣為：1012、圖的鄰接譜定義2：圖的鄰接矩陣A(G)的特征多項(xiàng)式102于是：102于是：103所以：例3，若兩個(gè)非同構(gòu)的圖具有相同的譜，則稱它們是同譜圖。求證：下面兩圖是同譜圖。GH103所以：例3，若兩個(gè)非同構(gòu)的圖具有

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

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

56、圖G的鄰接代數(shù)。注： 向量空間的定義可簡單地記為“非空”、“兩閉”、“八條” 2、圖的鄰接代數(shù)的維數(shù)特征108(二)、圖的鄰接代數(shù)1、圖的鄰接代數(shù)的定義定義3：設(shè)A109定理1：G為n階連通無環(huán)圖，則：證明：由哈密爾頓凱萊定理(見北大數(shù)學(xué)力學(xué)系高等代數(shù))：所以：下面證明：E, A, A2, , A d (G)線性無關(guān)！若不然，則存在不全為零的數(shù)a0 ,a1 , , a d (G) ,使：109定理1：G為n階連通無環(huán)圖，則：證明：由哈密爾頓凱萊110設(shè)a m-10 , 但當(dāng)k m 時(shí)，有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設(shè)a m-10 , 但當(dāng)k m 時(shí)，有a k =111產(chǎn)生矛盾！定理結(jié)果分析：不等式右端的界是緊的！因?yàn)椋簄點(diǎn)路的直徑為n-1, 所以，此時(shí)該路的鄰接代數(shù)的維數(shù)正好為n。此外：當(dāng)G為K n時(shí)，有：111產(chǎn)生矛盾！定理結(jié)果分析：不等式右端的界是緊的！因?yàn)椋簄112定理2：集合：對于圖的對稱差運(yùn)算和數(shù)乘運(yùn)算：(三)、圖空間簡介來說作成數(shù)域 F = 0, 1 上的m維向量空間。注：圖空

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

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

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