電子科大研究生圖論——第1,2章基本概念,樹

1、 電子科技大學(xué)應(yīng)用數(shù)學(xué)學(xué)院電子科技大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 張先迪張先迪 1.1 圖論簡(jiǎn)介 現(xiàn)實(shí)生活中許多問題都可歸結(jié)為由點(diǎn)和線組現(xiàn)實(shí)生活中許多問題都可歸結(jié)為由點(diǎn)和線組成的圖形的問題，例如，鐵路交通圖，公路成的圖形的問題，例如，鐵路交通圖，公路交通圖，市區(qū)交通圖，自來水管網(wǎng)系統(tǒng)，甚交通圖，市區(qū)交通圖，自來水管網(wǎng)系統(tǒng)，甚至電路圖在研究某些問題時(shí)也可簡(jiǎn)化為由點(diǎn)至電路圖在研究某些問題時(shí)也可簡(jiǎn)化為由點(diǎn)和線組成的圖形，如：和線組成的圖形，如：ABCDABCDEuler的2. Hamilton 周游世界問題 1859年年 Hamilton 提出這樣一個(gè)問題：提出這樣一個(gè)問題：一個(gè)正十二面體有一個(gè)正十二面體有20個(gè)

2、頂點(diǎn)，它們代表個(gè)頂點(diǎn)，它們代表世界上世界上20個(gè)重要城市。正十二面體的每個(gè)重要城市。正十二面體的每個(gè)面均為五邊形，若兩個(gè)頂點(diǎn)之間有邊個(gè)面均為五邊形，若兩個(gè)頂點(diǎn)之間有邊相連，則表示相應(yīng)的城市之間有航線相相連，則表示相應(yīng)的城市之間有航線相通。通。 Hamilton 提出提出 “能否從某城市出發(fā)能否從某城市出發(fā)經(jīng)過每個(gè)城市一次且僅一次然后返回出經(jīng)過每個(gè)城市一次且僅一次然后返回出發(fā)點(diǎn)？發(fā)點(diǎn)？” 1840年數(shù)學(xué)家茂比烏斯（年數(shù)學(xué)家茂比烏斯（Mbius）提出一提出一個(gè)猜想：個(gè)猜想：任何平面地圖，總可以把它的一個(gè)國(guó)任何平面地圖，總可以把它的一個(gè)國(guó)家用四種顏色的一種著染，使相鄰國(guó)家著不同家用四種顏色的一種著染

3、，使相鄰國(guó)家著不同色。色。這就是著名的這就是著名的四色猜想四色猜想。如：。如：3. 四色問題四色問題 4. 中國(guó)郵路問題 19621962年中國(guó)數(shù)學(xué)家管梅谷提出：一年中國(guó)數(shù)學(xué)家管梅谷提出：一個(gè)郵遞員從郵局出發(fā)遞送郵件，要求個(gè)郵遞員從郵局出發(fā)遞送郵件，要求對(duì)他所負(fù)責(zé)的轄區(qū)的每條街至少走一對(duì)他所負(fù)責(zé)的轄區(qū)的每條街至少走一次，問如何選取路程最短次，問如何選取路程最短 的路線？這的路線？這個(gè)問題稱為中國(guó)郵路問題。個(gè)問題稱為中國(guó)郵路問題。 該問題可用專門的算法來求解。該問題可用專門的算法來求解。 圖論的應(yīng)用范圍很廣，它不但能應(yīng)用于自然圖論的應(yīng)用范圍很廣，它不但能應(yīng)用于自然科學(xué)，也能應(yīng)用于社會(huì)科學(xué)。它非但

4、廣泛應(yīng)用科學(xué)，也能應(yīng)用于社會(huì)科學(xué)。它非但廣泛應(yīng)用于電信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、運(yùn)輸能力開關(guān)理論、于電信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、運(yùn)輸能力開關(guān)理論、編碼理論、控制論、反饋理論、隨機(jī)過程、可編碼理論、控制論、反饋理論、隨機(jī)過程、可靠性理論、化學(xué)化合物的辨認(rèn)、計(jì)算機(jī)的程序靠性理論、化學(xué)化合物的辨認(rèn)、計(jì)算機(jī)的程序設(shè)計(jì)、故障診斷、人工智能、印刷電路板的設(shè)設(shè)計(jì)、故障診斷、人工智能、印刷電路板的設(shè)計(jì)、圖案識(shí)別、地圖著色、情報(bào)檢索，也應(yīng)用計(jì)、圖案識(shí)別、地圖著色、情報(bào)檢索，也應(yīng)用于語(yǔ)言學(xué)、社會(huì)結(jié)構(gòu)、經(jīng)濟(jì)學(xué)、運(yùn)籌學(xué)、遺傳于語(yǔ)言學(xué)、社會(huì)結(jié)構(gòu)、經(jīng)濟(jì)學(xué)、運(yùn)籌學(xué)、遺傳學(xué)等。學(xué)等。圖論作為一個(gè)數(shù)學(xué)分支，有一套完整圖論作為一個(gè)數(shù)學(xué)分支，有一套

5、完整的體系和廣泛的內(nèi)容，在這里我們的體系和廣泛的內(nèi)容，在這里我們只準(zhǔn)備介紹圖論的初步知識(shí)，其目只準(zhǔn)備介紹圖論的初步知識(shí)，其目的是今后在其它有關(guān)學(xué)科的學(xué)習(xí)和的是今后在其它有關(guān)學(xué)科的學(xué)習(xí)和研究時(shí)，可以用圖論的基本知識(shí)作研究時(shí)，可以用圖論的基本知識(shí)作為工具。為工具。1.1 1.1 圖和簡(jiǎn)單圖圖和簡(jiǎn)單圖 一圖的定義一圖的定義 定義定義1 一個(gè)圖一個(gè)圖 G 定義為一個(gè)有序?qū)Χx為一個(gè)有序?qū)?V, E)，記為，記為G = (V, E)，其中其中 （1）V是一個(gè)非空集合，稱為頂點(diǎn)集或點(diǎn)集，其元素稱是一個(gè)非空集合，稱為頂點(diǎn)集或點(diǎn)集，其元素稱為頂點(diǎn)或點(diǎn)；為頂點(diǎn)或點(diǎn)； （2）E是由是由V中的點(diǎn)組成的無序點(diǎn)對(duì)構(gòu)成的

6、集合，稱為中的點(diǎn)組成的無序點(diǎn)對(duì)構(gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對(duì)在邊集，其元素稱為邊，且同一點(diǎn)對(duì)在 E 中可出現(xiàn)多次。中可出現(xiàn)多次。第一章第一章 圖的基本概念圖的基本概念編輯ppt11符號(hào)說明符號(hào)說明: 圖圖G 的頂點(diǎn)集也記為的頂點(diǎn)集也記為V(G), 邊集也記為邊集也記為E(G)。圖。圖G 的頂點(diǎn)數(shù)（或階數(shù)）和邊數(shù)可分別用符號(hào)的頂點(diǎn)數(shù)（或階數(shù)）和邊數(shù)可分別用符號(hào) n(G) (或或 |V(G)| ) 和和 m(G)表示。表示。例例1 1 設(shè)設(shè) V =v1, v2, v3, v4，E =v1v2 , v1v2, v2v3 ，則，則 G = (V, E) 是一個(gè)是一個(gè)4階圖。階圖。 若用

7、小圓點(diǎn)代若用小圓點(diǎn)代表點(diǎn)，連線代表邊表點(diǎn)，連線代表邊，則可將一個(gè)圖用，則可將一個(gè)圖用“圖形圖形”來表示來表示, 如如例例1 中的圖可表中的圖可表為為v1v2v3v4編輯ppt12注注: 也可記邊也可記邊 uv 為為e ，即，即 e = uv。v1v2v3v4e1e2e3e4e5 例例2 2 設(shè)設(shè)V = v1,v2,v3,v4，E = e1,e2,e3,e4,e5，其中其中 e1= v1v2， e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4 則則 G = (V, E) 是一個(gè)圖。是一個(gè)圖。編輯ppt13相關(guān)概念相關(guān)概念: (1) 若邊若邊e = uv , 此

8、時(shí)稱此時(shí)稱 u 和和v 是是 e 的的端點(diǎn)端點(diǎn); 并稱并稱 u 和和 v 相相鄰鄰，u (或或v)與與 e 相關(guān)聯(lián)相關(guān)聯(lián)。若兩條邊有一個(gè)共同的端點(diǎn)，則。若兩條邊有一個(gè)共同的端點(diǎn)，則稱這兩條稱這兩條邊相鄰邊相鄰。（2）特殊點(diǎn)、邊）特殊點(diǎn)、邊 孤立點(diǎn)：孤立點(diǎn)：不與任何邊相關(guān)聯(lián)的點(diǎn)；不與任何邊相關(guān)聯(lián)的點(diǎn)； 環(huán)：環(huán)：兩端點(diǎn)重合的邊；兩端點(diǎn)重合的邊； 重邊：重邊：連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)，叫做邊的連接兩個(gè)相同頂點(diǎn)的邊的條數(shù)，叫做邊的重?cái)?shù)重?cái)?shù)。重?cái)?shù)大于重?cái)?shù)大于1的邊稱為重邊。的邊稱為重邊。編輯ppt14(4) 既沒有環(huán)也沒有重邊的圖稱為既沒有環(huán)也沒有重邊的圖稱為簡(jiǎn)單圖簡(jiǎn)單圖。其他所有的圖。其他所有的圖都

9、稱為都稱為復(fù)合圖。復(fù)合圖。簡(jiǎn)單圖簡(jiǎn)單圖非非簡(jiǎn)單簡(jiǎn)單圖圖例例3 3 平凡圖平凡圖 (3) 點(diǎn)集與邊集均為有限集合的圖稱為點(diǎn)集與邊集均為有限集合的圖稱為有限圖有限圖，本書只討，本書只討論有限圖。只有一個(gè)頂點(diǎn)而無邊的圖稱為論有限圖。只有一個(gè)頂點(diǎn)而無邊的圖稱為平凡圖平凡圖。邊集為。邊集為空的圖稱為空的圖稱為空?qǐng)D空?qǐng)D。二圖的同構(gòu)二圖的同構(gòu)定義定義2 設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖G1 = (V1, E1)和和G2 = (V2, E2)，若在其頂，若在其頂點(diǎn)集合之間存在雙射，即存在一一對(duì)應(yīng)的關(guān)系，使得邊之點(diǎn)集合之間存在雙射，即存在一一對(duì)應(yīng)的關(guān)系，使得邊之間有如下的關(guān)系：設(shè)間有如下的關(guān)系：設(shè)1 11u vE2 22u

10、 vE1 1u v2 2u v當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)， ；且；且的重?cái)?shù)與的重?cái)?shù)與的重?cái)?shù)相同，則稱兩圖同構(gòu)，記為的重?cái)?shù)相同，則稱兩圖同構(gòu)，記為G1 G2。12uu12vv111,u vV222,u vV，對(duì)應(yīng)為：，對(duì)應(yīng)為：編輯ppt16例如例如 說明：說明：(1) 兩個(gè)同構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的兩個(gè)同構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的差異差異, 差異只是頂點(diǎn)和邊的名稱不同。差異只是頂點(diǎn)和邊的名稱不同。（2）圖同構(gòu)的幾個(gè)必要條件：圖同構(gòu)的幾個(gè)必要條件： 頂點(diǎn)數(shù)相同；頂點(diǎn)數(shù)相同； 邊數(shù)邊數(shù)相同；相同； 度數(shù)度數(shù)相等的頂點(diǎn)個(gè)數(shù)相同。相等的頂點(diǎn)個(gè)數(shù)相同。定義定義 設(shè)設(shè) v為為 G 的頂點(diǎn)，的頂點(diǎn)，G

11、 中與中與 v 為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn)算兩次）稱為點(diǎn) v 的度數(shù)，簡(jiǎn)稱為點(diǎn)的度數(shù)，簡(jiǎn)稱為點(diǎn)v的的度度，記為，記為 dG (v)，簡(jiǎn)記為簡(jiǎn)記為 d(v)。編輯ppt17圖中圖中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2v1v2v3v4v5例例 注：注：該圖中各點(diǎn)的度數(shù)該圖中各點(diǎn)的度數(shù) 之和等于之和等于14，恰好，恰好 是邊數(shù)是邊數(shù)7的的兩兩倍倍(3) 易證，圖的同構(gòu)關(guān)系是一個(gè)等價(jià)關(guān)系。該關(guān)系將所有易證，圖的同構(gòu)關(guān)系是一個(gè)等價(jià)關(guān)系。該關(guān)系將所有的圖的集合，劃分為一些等價(jià)類，即相互同構(gòu)的圖作成的圖

12、的集合，劃分為一些等價(jià)類，即相互同構(gòu)的圖作成同一個(gè)等價(jià)類。同一個(gè)等價(jià)類。編輯ppt18（3）在圖的圖形表示中我們可以不給圖的點(diǎn)和在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號(hào)，稱這樣的圖為邊標(biāo)上符號(hào)，稱這樣的圖為非標(biāo)定（號(hào)）圖非標(biāo)定（號(hào)）圖，否，否則稱為則稱為標(biāo)定（號(hào)）圖標(biāo)定（號(hào)）圖。非標(biāo)定圖實(shí)際上是代表一。非標(biāo)定圖實(shí)際上是代表一類相互同構(gòu)的圖。類相互同構(gòu)的圖。 不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。（4）判定圖的同構(gòu)是很困難的，屬于判定圖的同構(gòu)是很困難的，屬于NP完全完全問題。對(duì)于規(guī)模不大的兩個(gè)圖，判定其是否同問題。對(duì)于規(guī)模不大的兩個(gè)圖，判定其是

13、否同構(gòu)，可以采用觀察加推證的方法。構(gòu)，可以采用觀察加推證的方法。編輯ppt19 例例 證明下面兩圖同構(gòu)。證明下面兩圖同構(gòu)。證明證明 作映射作映射 f : vi ui (i=1,2.10)，易知該映射為雙射。，易知該映射為雙射。 (a) v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 (b) 容易驗(yàn)證容易驗(yàn)證 ，對(duì)，對(duì) vi v j E (a), 有有 f (v i vj,) ui,uj, E(b) ，(1 i 10, 1 j 10 )由圖的同構(gòu)定義知，圖由圖的同構(gòu)定義知，圖(a)與與(b)是同構(gòu)的。是同構(gòu)的。編輯ppt

14、20 例例 判斷下面兩圖是否同構(gòu)。判斷下面兩圖是否同構(gòu)。u1v1解解 兩圖不同構(gòu)。兩圖不同構(gòu)。這是因若同構(gòu)，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個(gè)點(diǎn)這是因若同構(gòu)，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個(gè)點(diǎn)u1 與與v1 一定相對(duì)應(yīng)，而一定相對(duì)應(yīng)，而u1的兩個(gè)鄰接點(diǎn)與的兩個(gè)鄰接點(diǎn)與v1的兩個(gè)鄰接點(diǎn)狀況不的兩個(gè)鄰接點(diǎn)狀況不同（同（ u1鄰接有鄰接有4度點(diǎn)，而度點(diǎn)，而v1 沒有）。沒有）。 所以，兩圖不同構(gòu)。所以，兩圖不同構(gòu)。編輯ppt21三完全圖三完全圖 ，偶圖，偶圖 ，補(bǔ)圖，補(bǔ)圖 完全圖：完全圖：任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱為完全圖，任意兩點(diǎn)均相鄰的簡(jiǎn)單圖稱為完全圖，在同構(gòu)意義下，在同構(gòu)意義下，n 階完全圖只有一個(gè)，記為

15、階完全圖只有一個(gè)，記為Kn。例例如如K2, K3, K4分別為如下圖所示分別為如下圖所示。K2K3K4編輯ppt22具有二分類（具有二分類（X, Y）的偶圖（或二部圖）：）的偶圖（或二部圖）：是是指該圖的點(diǎn)集可以分解為兩個(gè)（非空）子集指該圖的點(diǎn)集可以分解為兩個(gè)（非空）子集 X 和和 Y ，使得每條邊的一個(gè)端點(diǎn)在，使得每條邊的一個(gè)端點(diǎn)在 X 中，另一個(gè)中，另一個(gè)端點(diǎn)在端點(diǎn)在Y 中。中。完全偶圖：完全偶圖：是指具有二分類（是指具有二分類（X, Y）的簡(jiǎn)單偶圖）的簡(jiǎn)單偶圖，其中，其中 X的每個(gè)頂點(diǎn)與的每個(gè)頂點(diǎn)與 Y 的每個(gè)頂點(diǎn)相連，若的每個(gè)頂點(diǎn)相連，若 |X|=m，|Y|=n，則這樣的偶圖記為，則這

16、樣的偶圖記為 Km,n編輯ppt23例例 K 3,3 K1,3 G1 G2 四個(gè)圖均為偶圖四個(gè)圖均為偶圖; K1,3 , K3,3為完全偶圖為完全偶圖 編輯ppt24例例偶圖不是偶圖1, ,Euv uv u vV簡(jiǎn)單簡(jiǎn)單圖圖G 的補(bǔ)圖的補(bǔ)圖: 設(shè)設(shè) G =（V, E），則圖），則圖 H =（V，E1E）稱為稱為G 的補(bǔ)圖，記為的補(bǔ)圖，記為 , 其中集合其中集合HG編輯ppt25例如例如, 下圖中的下圖中的(a)，(b)兩圖是互補(bǔ)的。兩圖是互補(bǔ)的。（a）（b）定理定理1 若若n 階圖階圖G是自補(bǔ)的（即是自補(bǔ)的（即 ），則），則 n = 0, 1（mod 4）GG編輯ppt26證明證明 因?yàn)橐驗(yàn)镚

17、是自補(bǔ)的，則是自補(bǔ)的，則G和其補(bǔ)圖有同樣多的邊數(shù)，且和其補(bǔ)圖有同樣多的邊數(shù)，且邊數(shù)邊數(shù)m(G) +m)(G2) 1( nn= m(Kn) =從而從而4) 1()(nnGm又因又因G 的邊數(shù)的邊數(shù) m(G)是整數(shù)，故是整數(shù)，故 n(n-1)/4 為整數(shù)，即只能有為整數(shù)，即只能有n0（mod 4）, 或或 (n-1) 0 （mod 4）。）。 四四頂點(diǎn)的度（續(xù)）頂點(diǎn)的度（續(xù)）, , 度序列度序列前已定義：前已定義： 設(shè)設(shè) v為為 G 的頂點(diǎn)，的頂點(diǎn)，G 中與中與 v 為端點(diǎn)的邊為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn)的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn) v 的度數(shù)，簡(jiǎn)稱為點(diǎn)的度數(shù)，簡(jiǎn)稱為點(diǎn)v的的度度，記為，記為

18、 dG (v)，簡(jiǎn)記為簡(jiǎn)記為 d(v)。圖中圖中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2v1v2v3v4v5例如例如注：注：該圖中各點(diǎn)的度數(shù)該圖中各點(diǎn)的度數(shù) 之和等于之和等于14，恰好，恰好 是邊數(shù)是邊數(shù)7的的兩兩倍倍對(duì)任意的有對(duì)任意的有m條邊的圖條邊的圖 G = (V, E)。有有證明證明 因圖因圖 G 的任一條邊均有兩個(gè)端點(diǎn)的任一條邊均有兩個(gè)端點(diǎn) (可以相同可以相同)，在，在計(jì)算度時(shí)恰被計(jì)算兩次計(jì)算度時(shí)恰被計(jì)算兩次 (每個(gè)端點(diǎn)各被計(jì)算了一次每個(gè)端點(diǎn)各被計(jì)算了一次)，所，所以各點(diǎn)的度數(shù)之和恰好為邊數(shù)的兩倍，即以各點(diǎn)的度數(shù)之

19、和恰好為邊數(shù)的兩倍，即 (1.1) 式成立。式成立。 Vvmvd2)(（1.1） 定理定理2 2 （握手定理）：（握手定理）：注：注：該定理也稱為圖論第一定理，是由歐拉提出的。歐拉一身發(fā)該定理也稱為圖論第一定理，是由歐拉提出的。歐拉一身發(fā)表論文表論文886篇，著作篇，著作90部。部。編輯ppt29奇奇(偶偶)點(diǎn)點(diǎn): 奇奇(偶偶)數(shù)度的頂點(diǎn)數(shù)度的頂點(diǎn)相關(guān)術(shù)語(yǔ)和記號(hào)相關(guān)術(shù)語(yǔ)和記號(hào) G圖圖G的頂點(diǎn)的最小度的頂點(diǎn)的最小度 G圖圖G的頂點(diǎn)的最大度的頂點(diǎn)的最大度k-正則圖正則圖: 每個(gè)點(diǎn)的度均為每個(gè)點(diǎn)的度均為 k 的的簡(jiǎn)單圖簡(jiǎn)單圖例如例如,完全圖和完全偶圖完全圖和完全偶圖Kn,n均是正則圖。均是正則圖。

20、推論推論1 1 任意圖中，奇點(diǎn)的個(gè)數(shù)為任意圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。偶數(shù)。從而推知從而推知 也為偶。而和式中每個(gè)也為偶。而和式中每個(gè)d(v)均為奇，故和均為奇，故和式中的被加項(xiàng)的項(xiàng)數(shù)應(yīng)為偶，這表明式中的被加項(xiàng)的項(xiàng)數(shù)應(yīng)為偶，這表明G 中度為奇數(shù)的點(diǎn)有偶中度為奇數(shù)的點(diǎn)有偶數(shù)個(gè)。數(shù)個(gè)。 1)(Vvvd證明證明 任給圖任給圖G = (V, E)，設(shè)設(shè)G 有有m 條邊，令條邊，令V1= v | v V ,d(v) 為奇數(shù)為奇數(shù) , V2= v | v V ,d(v) 為偶數(shù)為偶數(shù) 顯然，顯然，V1 V2 2= = V, ,V1 1V2 2= = 。由握手定理由握手定理 Vvvd)( 1)(Vvvd 2)(

21、Vvvd2m = = + （1）2)(Vvvd（1）式中）式中2m為偶，為偶， 也為偶（因其中每個(gè)也為偶（因其中每個(gè)d(v)為偶），為偶），例例7 7 證明在任意一次集會(huì)中和奇數(shù)個(gè)證明在任意一次集會(huì)中和奇數(shù)個(gè)人握手的人的個(gè)數(shù)為偶數(shù)個(gè)。人握手的人的個(gè)數(shù)為偶數(shù)個(gè)。 證明證明: 將集會(huì)中的人作為點(diǎn)，若兩個(gè)人握將集會(huì)中的人作為點(diǎn)，若兩個(gè)人握手則對(duì)應(yīng)的點(diǎn)聯(lián)線，則得簡(jiǎn)單圖手則對(duì)應(yīng)的點(diǎn)聯(lián)線，則得簡(jiǎn)單圖G。這樣這樣G中點(diǎn)中點(diǎn)v的度對(duì)應(yīng)于集會(huì)中與的度對(duì)應(yīng)于集會(huì)中與v握手的人的個(gè)數(shù)。握手的人的個(gè)數(shù)。于是，問題轉(zhuǎn)化為證明于是，問題轉(zhuǎn)化為證明“圖圖G 中度數(shù)為奇的中度數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)點(diǎn)的個(gè)數(shù)為偶數(shù)”，這正是，這

22、正是推論推論1的結(jié)論。的結(jié)論。編輯ppt32推論推論2 正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù)。正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù)。證明證明 設(shè)設(shè)G是是k-正則圖，若正則圖，若k為奇數(shù)，則由推論為奇數(shù)，則由推論1知正則圖知正則圖G的點(diǎn)數(shù)必為偶數(shù)。的點(diǎn)數(shù)必為偶數(shù)。 度序列度序列: 一個(gè)圖一個(gè)圖G的各個(gè)點(diǎn)的度的各個(gè)點(diǎn)的度d1, d2, dn構(gòu)成的非負(fù)整數(shù)構(gòu)成的非負(fù)整數(shù) 組組 (d1, d2, dn)稱為稱為G的度序列的度序列 。它是刻畫圖的特。它是刻畫圖的特 征的重要征的重要“拓?fù)洳蛔兞客負(fù)洳蛔兞俊薄Ｕ麛?shù)正整數(shù)k的劃分的劃分: 是指將是指將k表示為若干正整數(shù)的和表示為若干正整數(shù)的和,或指一或指一 個(gè)無序正整

23、數(shù)組，組中正整數(shù)的和是個(gè)無序正整數(shù)組，組中正整數(shù)的和是k。 圖劃分圖劃分: 正整數(shù)正整數(shù)k的一個(gè)劃分的一個(gè)劃分(d1, d2, dn)能成為某簡(jiǎn)能成為某簡(jiǎn) 單圖的度序列的單圖的度序列的k的劃分的劃分. 顯然，若正整數(shù)顯然，若正整數(shù) k 有圖劃分，則有圖劃分，則k 必須是偶數(shù)必須是偶數(shù)編輯ppt33例例 偶數(shù)偶數(shù)4有五種劃分：有五種劃分： 4，3+1，2+2，1+1+2，1+1+1+1但屬于圖劃分的卻只有兩種但屬于圖劃分的卻只有兩種:2+1+11+1+1+1對(duì)一個(gè)非負(fù)整數(shù)組對(duì)一個(gè)非負(fù)整數(shù)組(d1, d2, dn)，mdnii21 , 若存在一個(gè)若存在一個(gè)簡(jiǎn)單圖簡(jiǎn)單圖G，以它為度序列，則稱這個(gè)數(shù)組

24、是，以它為度序列，則稱這個(gè)數(shù)組是可圖的可圖的。 編輯ppt34mdnii21), 1, 1, 1(213211nddddddd定理定理5 設(shè)有非負(fù)整數(shù)組設(shè)有非負(fù)整數(shù)組 = (d1, d2, dn)，且，且是一個(gè)偶數(shù)，是一個(gè)偶數(shù)，n-1d1d2dn， 是可圖的充要條件為是可圖的充要條件為是可圖的。是可圖的。例例 試判斷下列非負(fù)整數(shù)組試判斷下列非負(fù)整數(shù)組 是否可圖是否可圖?5 5 3 3 2 2 2 4 2 2 1 1 2 解解 利用定理利用定理5可得下列非負(fù)整數(shù)組可得下列非負(fù)整數(shù)組14 2 2 2 1 1 11 1 1 0 1 編輯ppt3511 1 1 0 1 因因是可圖的是可圖的 所以所以

25、也是可圖的也是可圖的: 5 5 3 3 2 2 2 v3 v4 v5v1 v6v2 v7 關(guān)于圖序列，主要研究的關(guān)于圖序列，主要研究的3個(gè)問題個(gè)問題：（：（1）存在問題（什存在問題（什么樣的整數(shù)組是圖序列？）已么樣的整數(shù)組是圖序列？）已解決；解決；(2) 計(jì)數(shù)問題（一個(gè)圖計(jì)數(shù)問題（一個(gè)圖序列對(duì)應(yīng)多少不同構(gòu)的圖？）序列對(duì)應(yīng)多少不同構(gòu)的圖？）解決得不好；解決得不好；(3) 構(gòu)造問題構(gòu)造問題（如何畫出圖序列對(duì)應(yīng)的所有不同構(gòu)圖？）（如何畫出圖序列對(duì)應(yīng)的所有不同構(gòu)圖？）沒有解決。沒有解決。編輯ppt361.2 子圖與圖的運(yùn)算子圖與圖的運(yùn)算一一. 子圖子圖 定義定義1 1 設(shè)設(shè)G 和和H為兩個(gè)圖，若為兩個(gè)

26、圖，若V(H) V(G) , E(H) E(G) ,且且H中邊的重?cái)?shù)不超過中邊的重?cái)?shù)不超過G中對(duì)應(yīng)邊的重?cái)?shù)，則稱中對(duì)應(yīng)邊的重?cái)?shù)，則稱H 是是G 的的子圖子圖. 記為記為H G 。有時(shí)又稱。有時(shí)又稱G是是H的母圖。的母圖。 當(dāng)當(dāng)H G ，但，但H G時(shí)，則記為時(shí)，則記為H G ，且稱，且稱H為為G的的真子圖真子圖。G的的生成子圖生成子圖是指滿足是指滿足V(H) = V(G)的子圖的子圖H。例如例如編輯ppt37 上圖中，上圖中，H1與與H2均為均為G 的子圖，其中的子圖，其中H2 是是G 的生成子圖，的生成子圖，而而H1 則不是。則不是。v1v2v3v4v5v1v3v4v2G H1 v1v3v4

27、v2v5 H2導(dǎo)出子圖導(dǎo)出子圖 設(shè)設(shè)V是是V的一個(gè)非空子集。以的一個(gè)非空子集。以V為頂點(diǎn)集，以兩為頂點(diǎn)集，以兩端點(diǎn)均在端點(diǎn)均在V中的邊的全體為邊集所組成的子圖，稱為中的邊的全體為邊集所組成的子圖，稱為G的的由由V導(dǎo)出的子圖，記為導(dǎo)出的子圖，記為GV；簡(jiǎn)稱為；簡(jiǎn)稱為G的導(dǎo)出子圖，的導(dǎo)出子圖， 導(dǎo)出子圖導(dǎo)出子圖GVV記為記為 G -V ；它是；它是G中刪除中刪除V中的頂點(diǎn)中的頂點(diǎn)以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。若以及與這些頂點(diǎn)相關(guān)聯(lián)的邊所得到的子圖。若 V=v, 則則把把G-v簡(jiǎn)記為簡(jiǎn)記為Gv。編輯ppt38邊導(dǎo)出子圖邊導(dǎo)出子圖 假設(shè)假設(shè)E是是E的非空子集。以的非空子集。以E為邊集，以為邊集

28、，以E中中邊的端點(diǎn)全體為頂點(diǎn)集所組成的子圖稱為邊的端點(diǎn)全體為頂點(diǎn)集所組成的子圖稱為G的由的由E導(dǎo)出的導(dǎo)出的子圖，記為子圖，記為GE ；簡(jiǎn)稱為；簡(jiǎn)稱為G的邊導(dǎo)出子圖，邊集為的邊導(dǎo)出子圖，邊集為 E E 的的G 的導(dǎo)出子圖簡(jiǎn)記為的導(dǎo)出子圖簡(jiǎn)記為 G-E 。若。若E =e ，則用，則用Ge來代來代替替 G-e。定理定理8 簡(jiǎn)單圖簡(jiǎn)單圖G 中所有不同的生成子圖（包括中所有不同的生成子圖（包括G和空?qǐng)D）和空?qǐng)D）的個(gè)數(shù)是的個(gè)數(shù)是2m個(gè)個(gè), 其中其中m為為G 的邊數(shù)。的邊數(shù)。證明證明 易知易知其個(gè)數(shù)其個(gè)數(shù) = 含含0條邊的條邊的+含含1條邊的條邊的+含含m條邊的條邊的mmmmm210編輯ppt39二二. 圖

29、的運(yùn)算圖的運(yùn)算設(shè)設(shè)G1，G2是是G 的子圖的子圖, 有下列術(shù)語(yǔ)與概念有下列術(shù)語(yǔ)與概念 G1和和G2不相交不相交: 指它們無公共頂點(diǎn)指它們無公共頂點(diǎn).G1和和G2邊不重邊不重 : 指它們無公共邊指它們無公共邊.并圖并圖G1G2 ：是指其頂點(diǎn)集為是指其頂點(diǎn)集為V(G1)V(G2)，邊集，邊集為為E(G1)E(G2) 的的G 的一個(gè)子圖的一個(gè)子圖 ；如果；如果G1和和G2是不是不相交的，有時(shí)就記其并圖為相交的，有時(shí)就記其并圖為G1+G2。 交圖交圖G1G2 ：類似地定義類似地定義對(duì)稱差對(duì)稱差G1G2 ：G1G2 = (G1G2) - (G1G2) = (G1-G2)(G2-G1)編輯ppt40例例2

30、 d 4a c e1 f 3 G1b2 d 4 g e 5 i 3 j G2 h c 2 d 4 g a c e 5 b i h1 f 3 G1G2j 2 d 4 c e 3G1G2編輯ppt41例例2 d 4a c e1 f 3 G1b2 d 4 g e 5 i 3 j G2 h c2 4a b1 f 3 G1-G254 g h i3 j G2-G1254 g h i j 2a b1 f 3G2G1編輯ppt42定義定義2 在不相交的在不相交的G1和和G2的并圖的并圖G1+G2中，把中，把G1的每個(gè)頂?shù)拿總€(gè)頂點(diǎn)和點(diǎn)和G2的每個(gè)頂點(diǎn)連接起來所得到的圖稱為的每個(gè)頂點(diǎn)連接起來所得到的圖稱為G1和和

31、G2的聯(lián)的聯(lián)圖，記為圖，記為G1G2。例例v1 v2v4 v3 G2v1 v2v4 v3 G1G2u1u1G1有：有： K1K4=K5，K2K3=K5 K6= K1K5 = K2K4 = K3K3。編輯ppt43定義定義3 設(shè)設(shè)G1= (V1, E1)，G2 = (V2, E2)，對(duì)點(diǎn)集，對(duì)點(diǎn)集V = V1V2中中的任意兩個(gè)點(diǎn)的任意兩個(gè)點(diǎn)u = (u1,u2)和和v = (v1,v2)，當(dāng)，當(dāng)(u1 = v1和和 u2 adj v2) 或或 (u2 = v2 和和 u1 adj v1) 時(shí)就把時(shí)就把 u 和和 v 連接起來所得到的圖連接起來所得到的圖G稱為稱為G1和和G2積圖，記為積圖，記為G

32、 = G1G2。其中。其中 ui adj vi 表表 ui 和和vi鄰接，如下圖所示。鄰接，如下圖所示。u1v1G1u2 v2 w2 G2(u1, u2) (u1, v2) (u1, w2)(v1, u2) (v1, v2) (v1, w2) G1G2例例編輯ppt44n-方體方體Qn ：遞推地定義為，遞推地定義為，Q1= K2，Qn= K2Qn-1 。 01 1100 10 Q2= K2K2101 111 001 011 000 010100 110 Q3= K2K2K2例例注：注： Qn有有2n個(gè)點(diǎn)，它的點(diǎn)可以用個(gè)點(diǎn)，它的點(diǎn)可以用a1 a2an來標(biāo)定，其中來標(biāo)定，其中ai是是0或者或者1。

33、如果。如果Qn的兩個(gè)點(diǎn)的二進(jìn)制表示式中只有一處不同，則的兩個(gè)點(diǎn)的二進(jìn)制表示式中只有一處不同，則它們鄰接。它們鄰接。 1.1.3 3 路和連通性路和連通性 定義定義 給定圖給定圖G = (V, E)，w = v0e1v1e2ekvk 是是G 中點(diǎn)邊中點(diǎn)邊交替組成的序列，其中交替組成的序列，其中 viV，eiE，若若w滿足滿足 ei 的端點(diǎn)為的端點(diǎn)為 vi-1 與與 vi，i = 0,1, k，則稱則稱w為一條從起點(diǎn)為一條從起點(diǎn) v0 到終點(diǎn)到終點(diǎn) vk 的的長(zhǎng)為長(zhǎng)為 k 的的途徑途徑（或通道或（或通道或通路通路), , 簡(jiǎn)稱（簡(jiǎn)稱（v0, vk）途徑。）途徑。 邊不重復(fù)的邊不重復(fù)的途徑途徑稱為稱

34、為跡跡 ；任意兩點(diǎn)都不同的；任意兩點(diǎn)都不同的途徑途徑稱為稱為路路。顯然路必為。顯然路必為跡跡。 閉途徑閉途徑:起點(diǎn)和終點(diǎn)相同的長(zhǎng)為正的途徑。起點(diǎn)和終點(diǎn)相同的長(zhǎng)為正的途徑。 閉跡也稱為閉跡也稱為回路回路。1. 途徑、跡、路、圈、距離和直徑途徑、跡、路、圈、距離和直徑編輯ppt46圈圈: 起點(diǎn)和內(nèi)部頂點(diǎn)（非起點(diǎn)和終點(diǎn)的點(diǎn)）兩兩不相同起點(diǎn)和內(nèi)部頂點(diǎn)（非起點(diǎn)和終點(diǎn)的點(diǎn)）兩兩不相同 的閉跡。的閉跡。k（奇，偶）圈：（奇，偶）圈：長(zhǎng)為長(zhǎng)為k （奇，偶）的圈。（奇，偶）的圈。 3圈常稱為三角形。圈常稱為三角形。 易知，圖中若兩個(gè)不同點(diǎn)易知，圖中若兩個(gè)不同點(diǎn)u與與 v 間存在途徑（通路），間存在途徑（通路），

35、則則 u 與與 v 間必存在路；若過點(diǎn)間必存在路；若過點(diǎn)u存在回路，則過點(diǎn)存在回路，則過點(diǎn)u 必必存在圈存在圈 。點(diǎn)點(diǎn)u與與v的距離：的距離：指圖中最短指圖中最短 (u, v) 途徑的長(zhǎng)度，記為途徑的長(zhǎng)度，記為 d(u, v)。圖圖G的直徑的直徑定義為定義為 d(G) = max d(u, v) | u, vV例例1 1 在下圖在下圖G 中，取中，取w1 = v1v2v3 ，w2 = v1v2v3v4v2 ，w3 = v1v2v3v2v3v4 ( 注：注：簡(jiǎn)單圖可只用點(diǎn)序列表通路）簡(jiǎn)單圖可只用點(diǎn)序列表通路）v1v4v5v3v2G則則 w1, w2, w3 依次為長(zhǎng)依次為長(zhǎng) 為為2,4,5的途徑

36、的途徑 ； 由定義由定義1可看出可看出,G中中 v1 v2v5v1為長(zhǎng)為為長(zhǎng)為3的圈，的圈，v1v2 v3 v4v2 v5v1 為長(zhǎng)為為長(zhǎng)為 6 的回路。的回路。w1與與w2為跡為跡 ，w1為路。為路。d(G) =22. 圖的連通性圖的連通性點(diǎn)點(diǎn)u與與v連通連通 ：指圖存在（指圖存在（u, v）路。規(guī)定）路。規(guī)定u和和u是連通的。是連通的。 連通圖連通圖: G中任意兩個(gè)頂點(diǎn)均連通的圖。中任意兩個(gè)頂點(diǎn)均連通的圖。非連通圖：非連通圖：不是連通圖的圖。不是連通圖的圖。連連通通圖圖非非連連通通圖圖 G D連通分支（分支，支）：連通分支（分支，支）：若若H是圖是圖G 的連通子圖且的連通子圖且H不不能再擴(kuò)

37、充為能再擴(kuò)充為G的任一連通子圖，則稱的任一連通子圖，則稱H為為G的連通分支。的連通分支。用用(G) 記圖記圖G 的的連通分支數(shù)連通分支數(shù)。有：有：(D) =3， (G) =1 易知：易知：G 連通連通(G)=1 G D例例編輯ppt503. 有關(guān)定理有關(guān)定理定理定理7 若圖若圖G是不連通的，則是不連通的，則 是連通圖。是連通圖。G證明證明 因因G是不連通是不連通, 故故G中至少兩個(gè)分支中至少兩個(gè)分支. 設(shè)設(shè)u，v是是G的任意兩個(gè)頂點(diǎn)。若的任意兩個(gè)頂點(diǎn)。若u和和v在在G中不鄰接，則中不鄰接，則在在 中它們鄰接。中它們鄰接。G 若若u和和v在在G中鄰接，則它們屬于中鄰接，則它們屬于G的同一分支。在

38、另一的同一分支。在另一個(gè)分支中取一點(diǎn)個(gè)分支中取一點(diǎn)w，則在，則在 中中u和和v均與均與w鄰接，從而鄰接，從而uwv是一條通道是一條通道, 故在故在 中它們鄰接。中它們鄰接。GG編輯ppt51定理定理8 一個(gè)圖是偶圖當(dāng)且當(dāng)它不包含奇圈。一個(gè)圖是偶圖當(dāng)且當(dāng)它不包含奇圈。證明證明 設(shè)設(shè)G是具有二分類（是具有二分類（X, Y）的偶圖，并且）的偶圖，并且C = v0 v1 vk v0是是G的一個(gè)圈。不失一般性，可假定的一個(gè)圈。不失一般性，可假定v0 X 。這樣，這樣， v2i X ，且，且v2i +1Y 。又因?yàn)?。又因?yàn)関0 X ，所以，所以vk Y 。由此即得。由此即得C是偶圈。是偶圈。 顯然僅對(duì)連通

39、圖證明其逆命題就夠了。設(shè)顯然僅對(duì)連通圖證明其逆命題就夠了。設(shè)G是不包含奇是不包含奇圈的連通圖。任選一個(gè)頂點(diǎn)圈的連通圖。任選一個(gè)頂點(diǎn)u且定義且定義V的一個(gè)分類（的一個(gè)分類（X, Y）如下：如下：X = x | d (u, x) 是偶數(shù)，是偶數(shù)，xV(G)Y = y | d (u, y) 是奇數(shù)，是奇數(shù)，yV(G)編輯ppt52現(xiàn)在證明（現(xiàn)在證明（X, Y）是）是G的一個(gè)二分類。的一個(gè)二分類。 假設(shè)假設(shè)v和和w是是X的兩個(gè)頂點(diǎn)，的兩個(gè)頂點(diǎn)，P是最短的（是最短的（u, v）路，）路，Q是最短的（是最短的（u, w）路，以）路，以u(píng)1記記P和和Q的最后一個(gè)公共的最后一個(gè)公共頂點(diǎn)。因頂點(diǎn)。因P和和Q是最

40、短路，是最短路，P和和Q二者的（二者的（u1, u）節(jié)也）節(jié)也是最短的路，故長(zhǎng)相同?，F(xiàn)因是最短的路，故長(zhǎng)相同?，F(xiàn)因P和和Q的長(zhǎng)都是偶數(shù)，的長(zhǎng)都是偶數(shù)，所以所以P的（的（u1, v）節(jié)）節(jié)P1和和Q的（的（u1, w）節(jié)）節(jié)Q1必有相同必有相同的奇偶性。由此推出路（的奇偶性。由此推出路（v, w）長(zhǎng)為偶數(shù)。若）長(zhǎng)為偶數(shù)。若v和和w相相連，則連，則 就是一個(gè)奇圈，與假設(shè)矛盾，故就是一個(gè)奇圈，與假設(shè)矛盾，故X中中任意兩個(gè)頂點(diǎn)均不相鄰。任意兩個(gè)頂點(diǎn)均不相鄰。 111P Q wv類似地，類似地，Y中任意兩個(gè)頂點(diǎn)也不相鄰。所以（中任意兩個(gè)頂點(diǎn)也不相鄰。所以（X, Y）是是G的一個(gè)二分類。的一個(gè)二分類。 編

41、輯ppt531.4 最短路及其算法最短路及其算法一一. 賦權(quán)圖賦權(quán)圖 定義定義 若圖若圖G的每一條邊的每一條邊e 都附有一個(gè)實(shí)數(shù)都附有一個(gè)實(shí)數(shù)w(e)，則則G連同連同它邊上的權(quán)稱為它邊上的權(quán)稱為賦權(quán)圖賦權(quán)圖。實(shí)數(shù)。實(shí)數(shù)w(e) 稱為稱為e的權(quán)。子圖的權(quán)。子圖H的各的各邊權(quán)之和稱為子圖邊權(quán)之和稱為子圖H 的權(quán)，記為的權(quán)，記為W(H)。例例 右圖右圖G 為為賦賦權(quán)圖權(quán)圖v1v3v2v4 G 1 3 5 6 5其中其中w(v1v2) = 1，w(v1v3) = 5，W(G) = 20 設(shè)設(shè)是權(quán)圖是權(quán)圖G 中的一條路，稱中的一條路，稱 的各邊權(quán)之和為路的各邊權(quán)之和為路的長(zhǎng)。的長(zhǎng)。賦權(quán)圖中點(diǎn)賦權(quán)圖中點(diǎn)

42、u 到到 v 的距離仍定義為點(diǎn)的距離仍定義為點(diǎn) u 到到 v 的最短路的長(zhǎng)，的最短路的長(zhǎng)，仍記為仍記為 d(u,v)。例例2 右圖中，右圖中， d(v2, v4) = 5相應(yīng)的最短路為相應(yīng)的最短路為 ：v2v1 v3v4v1v3v2v4 G 1 3 1 6 3 易知，各邊的權(quán)均為易知，各邊的權(quán)均為1的權(quán)圖中的路長(zhǎng)與非權(quán)圖中的路長(zhǎng)的權(quán)圖中的路長(zhǎng)與非權(quán)圖中的路長(zhǎng)是一致的。是一致的。編輯ppt55二二. . 最短路問題最短路問題 問題：?jiǎn)栴}：給定簡(jiǎn)單權(quán)圖給定簡(jiǎn)單權(quán)圖G = (V, E)，并設(shè)并設(shè)G 有有n個(gè)頂點(diǎn)，求個(gè)頂點(diǎn)，求G中點(diǎn)中點(diǎn)u0到其它各點(diǎn)的距離。到其它各點(diǎn)的距離。Dijkstra算法算法

43、(Edmonds, 1965)(2) 若若i = n-1，則停；否則令則停；否則令 = V Si , iSiSiS 對(duì)每個(gè)對(duì)每個(gè)v ，令令 l(v) = min l(v)，l(ui) + w(uiv)(1) 置置 l(u0) = 0；對(duì)所有；對(duì)所有vV u0，令，令 l(v) = ； S0 = u0，i = 0。并用并用 ui+1記達(dá)到最小值的某點(diǎn)。置記達(dá)到最小值的某點(diǎn)。置S i+1= Siu i+1，i = i+1（表示賦值語(yǔ)句，以后的算法中相同），轉(zhuǎn)（表示賦值語(yǔ)句，以后的算法中相同），轉(zhuǎn)（2）。）。終止后，終止后，u0 到到 v 的距離由的距離由 l(v) 的終值給出。的終值給出。)(mi

44、nvliSv (3) 計(jì)算計(jì)算說明：說明： （1） 算法中算法中w(uiv) 表示邊表示邊 uiv 的權(quán)；的權(quán)； （2） 若只想確定若只想確定u0到某頂點(diǎn)到某頂點(diǎn)v0的距離，的距離， 則當(dāng)某則當(dāng)某 uj 等于等于 v0 時(shí)即停；時(shí)即停；（3 3） 算法稍加改進(jìn)可同時(shí)得出算法稍加改進(jìn)可同時(shí)得出u u0 0到其它點(diǎn)的最短路。到其它點(diǎn)的最短路。例例3 求圖求圖 G 中中 u0 到其它點(diǎn)的距離。到其它點(diǎn)的距離。u0 742155813G :解解 u0 742155813 （a）初始標(biāo)號(hào)初始標(biāo)號(hào)u0 742155813 2 4 7（b）用與用與u0關(guān)聯(lián)的邊的關(guān)聯(lián)的邊的權(quán)權(quán)2,4,7分別更新與分別更新與u

45、0相鄰相鄰的三個(gè)點(diǎn)的標(biāo)號(hào)的三個(gè)點(diǎn)的標(biāo)號(hào);（c）取小圓點(diǎn)中標(biāo)號(hào)取小圓點(diǎn)中標(biāo)號(hào)最小者得最小者得 u1； u0 742155813 2 4 7u1 （d）對(duì)與對(duì)與u1相鄰的小圓點(diǎn)，相鄰的小圓點(diǎn)，用用 l (u1) + w (u1v) = 2+1 = 3更新標(biāo)號(hào)更新標(biāo)號(hào)4； 2+5=7 更新兩個(gè)更新兩個(gè)；u0 742155813 2 7 37 7u1 （e）取小圓點(diǎn)中標(biāo)號(hào)取小圓點(diǎn)中標(biāo)號(hào) 最小者得最小者得 u2。u0 742155813 2 7 37 7u1 u2 u4 u0 742155813 2 7 34 6（h）u1 u2 0u3u5 u0 742155813 2 7 37 7u1 u2 4 （f

46、）u0 742155813 2 7 3 6u1 u2 （g）u0 742155813 2 7 34 6u1 u2 u3編輯ppt61三三. . 算法分析算法分析好算法好算法 一個(gè)圖論算法如果在任何一個(gè)具有一個(gè)圖論算法如果在任何一個(gè)具有m條邊的條邊的n階階圖圖G上施行這個(gè)算法所需要的計(jì)算步數(shù)都可由上施行這個(gè)算法所需要的計(jì)算步數(shù)都可由n和和m的一的一個(gè)多項(xiàng)式（例如個(gè)多項(xiàng)式（例如3n2m）為其上界）為其上界, 則稱該算法是好的則稱該算法是好的. Dijkstra算法總共需作算法總共需作 n(n-1)/2 次加法和次加法和 n(n-1)/2 次比次比較較, 確定一個(gè)點(diǎn)是否屬于或不屬于確定一個(gè)點(diǎn)是否屬于

47、或不屬于S, 按按1969年年Dreyfus 報(bào)報(bào)告的技巧告的技巧, 需作需作(n-1)2 次比較次比較, 若把一次比較和一次加法作若把一次比較和一次加法作為一個(gè)基本計(jì)算單位為一個(gè)基本計(jì)算單位, 則該算法的總計(jì)算量大約是則該算法的總計(jì)算量大約是5n2/2.因此該算法是一個(gè)好算法因此該算法是一個(gè)好算法.編輯ppt62例例 某兩人有一只某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，分別升的酒壺裝滿了酒，還有兩只空壺，分別為為5升和升和3升?，F(xiàn)要將酒平分，求最少的操作次數(shù)。升?，F(xiàn)要將酒平分，求最少的操作次數(shù)。解解 設(shè)設(shè)x1,x2,x3分別表示分別表示8,5,3升酒壺中的酒量。則升酒壺中的酒量。則12

48、31238,8,5,3.xxxxxx容易算出容易算出(x1,x2,x3) 的組合形式共的組合形式共24種。種。 每種組合用一個(gè)點(diǎn)表示，若點(diǎn)每種組合用一個(gè)點(diǎn)表示，若點(diǎn)u能通過倒酒的方式變能通過倒酒的方式變換為換為v,則則 u向向v 連有向邊，并將各邊賦權(quán)連有向邊，并將各邊賦權(quán)1，得一個(gè)有向權(quán)，得一個(gè)有向權(quán)圖。圖。于是問題轉(zhuǎn)化為在該圖中求于是問題轉(zhuǎn)化為在該圖中求 (8,0,0)到到(4,4,0)的一條最短路的一條最短路(求最短路的算法在有向圖中仍適用求最短路的算法在有向圖中仍適用)。結(jié)果如下：。結(jié)果如下：(8,0,0)(3,5,0)(3,2,3)(6,2,0)(6,0,2)(1,5,2)(1,4,

49、3)(4,4,0).編輯ppt631.5 圖的代數(shù)表示及特征圖的代數(shù)表示及特征一一. 鄰接矩陣鄰接矩陣 定義：定義：設(shè)設(shè) n 階標(biāo)定圖階標(biāo)定圖G = (V,E)，V = v1,v2, vn，則則 G 的鄰接矩陣是一個(gè)的鄰接矩陣是一個(gè)nn 矩陣矩陣A(G) = aij (簡(jiǎn)記為簡(jiǎn)記為A)，其中若，其中若 vi鄰接鄰接vj，則，則aij =1;否則否則aij =0。 注注: 若若aij 取為連接取為連接vi與與vj 的邊的數(shù)目的邊的數(shù)目, 則稱則稱A為推廣的鄰接矩陣為推廣的鄰接矩陣編輯ppt64鄰接矩陣鄰接矩陣 A =0 1 0 01 0 1 00 1 0 10 0 1 10 1 0 01 0 2

50、 00 2 0 10 0 1 1推廣的推廣的鄰接矩陣鄰接矩陣 A =編輯ppt65說明說明: (1) 鄰接矩陣是一個(gè)對(duì)稱方陣。鄰接矩陣是一個(gè)對(duì)稱方陣。 (2) 簡(jiǎn)單標(biāo)定圖的鄰接矩陣的各行簡(jiǎn)單標(biāo)定圖的鄰接矩陣的各行 (列列) 元素之和是該行元素之和是該行 (列列) 對(duì)應(yīng)的點(diǎn)的度。對(duì)應(yīng)的點(diǎn)的度。 （3）若若A1和和A2是對(duì)應(yīng)于同一個(gè)是對(duì)應(yīng)于同一個(gè)G的兩種不同的標(biāo)定的鄰的兩種不同的標(biāo)定的鄰接矩陣，則接矩陣，則 A1和和A2 是相似的。即存在一個(gè)可逆矩陣是相似的。即存在一個(gè)可逆矩陣P有有112AP A P（4）G是連通的當(dāng)且僅當(dāng)沒有是連通的當(dāng)且僅當(dāng)沒有G的點(diǎn)的一種標(biāo)定法使的點(diǎn)的一種標(biāo)定法使 它的鄰接矩

51、陣有約化的形式它的鄰接矩陣有約化的形式112200AAA編輯ppt660 1 0 01 0 2 00 2 0 10 0 1 1推廣的推廣的鄰接矩陣鄰接矩陣 A =我們有：我們有：1 0 2 00 5 0 22 0 5 10 2 1 2 A 2=圖中圖中 v1到到 v1 的長(zhǎng)為的長(zhǎng)為2的的通道的數(shù)目為的的通道的數(shù)目為1 v1到到 v2 的長(zhǎng)為的長(zhǎng)為2的的通道的數(shù)目為的的通道的數(shù)目為0v1到到 v3 的長(zhǎng)為的長(zhǎng)為2的的通道的數(shù)目為的的通道的數(shù)目為2v1到到 v4的長(zhǎng)為的長(zhǎng)為2的的通道的數(shù)目為的的通道的數(shù)目為0 v2到到 v2 的長(zhǎng)為的長(zhǎng)為2的的通道的數(shù)目為的的通道的數(shù)目為5 編輯ppt67定理定理

52、10 令令G是一個(gè)有推廣鄰接矩陣是一個(gè)有推廣鄰接矩陣A的的 p階標(biāo)定圖，則階標(biāo)定圖，則 An的的i 行行j 列元素列元素 等于由等于由vi到到vj的長(zhǎng)度為的長(zhǎng)度為n的通道的數(shù)目。的通道的數(shù)目。 nija證明證明 n = 0時(shí)，時(shí)，A0 = In (n階單位矩陣階單位矩陣)，從任一點(diǎn)到自身，從任一點(diǎn)到自身有一條長(zhǎng)度為零的通道，任何不同的兩點(diǎn)間沒有長(zhǎng)度為有一條長(zhǎng)度為零的通道，任何不同的兩點(diǎn)間沒有長(zhǎng)度為零的通道，從而命題對(duì)零的通道，從而命題對(duì)n = 0時(shí)成立。時(shí)成立。 由于由于aik是聯(lián)結(jié)是聯(lián)結(jié)vi和和vk的長(zhǎng)度為的長(zhǎng)度為1的通道的數(shù)目，的通道的數(shù)目，akj(n)是是聯(lián)結(jié)聯(lián)結(jié)vk和和vj的長(zhǎng)度為的長(zhǎng)

53、度為n的通道的數(shù)目，所以的通道的數(shù)目，所以 aikakj(n) 表示由表示由vi經(jīng)過經(jīng)過vk到到vj的長(zhǎng)度為的長(zhǎng)度為n+1的通道數(shù)目。的通道數(shù)目。今設(shè)命題對(duì)今設(shè)命題對(duì)n 成立，由成立，由An+1=AAn，故，故pknkjiknijaaa1)()1(（*）編輯ppt68 于是對(duì)所有的于是對(duì)所有的k求和即（求和即（*）式右邊表示了由）式右邊表示了由 vi 到到 vj 的的長(zhǎng)度為長(zhǎng)度為n+1的通道數(shù)目。也即的通道數(shù)目。也即 aij(n+1) 為由為由 vi 到到 vj 的長(zhǎng)度的長(zhǎng)度為為n+1的通道數(shù)目。的通道數(shù)目。 這表明命題對(duì)這表明命題對(duì)n+1成立。成立。推論推論 設(shè)設(shè)A為簡(jiǎn)單圖為簡(jiǎn)單圖G的鄰接矩

54、陣，則的鄰接矩陣，則（1）A2 的元素的元素 aii(2) 是是 vi 的度數(shù)。的度數(shù)。A3 的元素的元素 aii(3) 是含是含 vi 的三角形的數(shù)目的兩倍。的三角形的數(shù)目的兩倍。 （2） 若若G是連通的，對(duì)于是連通的，對(duì)于ij，vi 與與vj 之間的距離是使之間的距離是使An 的的 aij(n) 0 的最小整數(shù)的最小整數(shù)n。編輯ppt69二二. 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣定義定義1 無環(huán)圖無環(huán)圖G的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣B(G) = bij (簡(jiǎn)記為簡(jiǎn)記為B)是一個(gè)是一個(gè) nm 矩陣，當(dāng)點(diǎn)矩陣，當(dāng)點(diǎn)vi 與邊與邊ej 關(guān)聯(lián)時(shí)關(guān)聯(lián)時(shí) bij =1，否則否則 bij =0。v1 e1 e5v2 v5 e6

55、e7 e2 e4v3 e3 v4例例B = e1 e2 e3 e4 e5 e6 e7v1v2v3v4v500110001001100010011000000111110001編輯ppt70說明：說明：定義中定義中“無無環(huán)環(huán)”的條件可去掉，此時(shí)的條件可去掉，此時(shí)bij =點(diǎn)點(diǎn)vi 與邊與邊ej 關(guān)聯(lián)的次數(shù)（關(guān)聯(lián)的次數(shù)（0, 1, 2(環(huán)環(huán)).性質(zhì)：性質(zhì)：關(guān)聯(lián)矩陣的每列和為關(guān)聯(lián)矩陣的每列和為2；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù)；其行和為對(duì)應(yīng)頂點(diǎn)的度數(shù).例如：例如：e1v4v3v2v1e7e5e4e3e2e61 1 0 0 1 0 11 1 1 0 0 0 0( )0 0 1 1 0 0 10 0 0 1 1

56、 2 0M G編輯ppt71三、鄰接代數(shù)三、鄰接代數(shù) 給定圖給定圖G , 容易驗(yàn)證容易驗(yàn)證G 的鄰接矩陣的全體復(fù)系數(shù)多項(xiàng)的鄰接矩陣的全體復(fù)系數(shù)多項(xiàng)式在通常的矩陣運(yùn)算下構(gòu)成一個(gè)有限維的線性空間，它式在通常的矩陣運(yùn)算下構(gòu)成一個(gè)有限維的線性空間，它也是一個(gè)代數(shù)，稱為圖也是一個(gè)代數(shù)，稱為圖G的鄰接代數(shù)，記為的鄰接代數(shù)，記為(G)。 用圖用圖G的點(diǎn)數(shù)和直徑可以給出鄰接代數(shù)的點(diǎn)數(shù)和直徑可以給出鄰接代數(shù)(G)的維數(shù)的的維數(shù)的界。界。定理定理11 n階連通圖階連通圖G的鄰接代數(shù)的維數(shù)有的鄰接代數(shù)的維數(shù)有 d(G)dim(G)n編輯ppt72 回憶線性代數(shù)的一些概念。設(shè)回憶線性代數(shù)的一些概念。設(shè)A = (aij

57、) 是一個(gè)是一個(gè)n 階方階方陣，其中陣，其中 aijC（復(fù)數(shù)集合）。（復(fù)數(shù)集合）。A的行（列）組成的的行（列）組成的n維維向量稱為向量稱為A的行（列）向量。的行（列）向量。稱為方陣稱為方陣A的特征值，如的特征值，如果存在數(shù)域果存在數(shù)域C 中一個(gè)非零列向量中一個(gè)非零列向量X，使得，使得 AX=X （1）則則X 稱為稱為A的屬于的屬于的一個(gè)特征向量。的一個(gè)特征向量。 實(shí)際上實(shí)際上是方程是方程 |In-A | = 0 （2）的）的根，其中根，其中In為為n階單位矩陣。階單位矩陣。 若方程（若方程（2）有）有s 個(gè)相異的根個(gè)相異的根1,2, ,s, ,其重?cái)?shù)依其重?cái)?shù)依次記為次記為m1, , m2, ,

58、 , ms（有（有 m1+ +m2+ + +ms = n），稱），稱編輯ppt73Spec A = ssmmm2121為為 A 的譜。的譜。 例例1 設(shè)設(shè)A 為為4圈圈C4 的鄰接矩陣，求的鄰接矩陣，求A的譜。的譜。 解解 C4的鄰接矩陣的鄰接矩陣0101101001011010A于是于是 |I4 -A | = =2(-2)(+2)101110011101編輯ppt74 定理定理13 設(shè)設(shè)G為為n 階連通圖，則鄰接矩陣階連通圖，則鄰接矩陣A(G)的不同特征值的不同特征值數(shù)目數(shù)目s 滿足不等式滿足不等式 d(G)+1 s n證明證明 右邊的不等式顯然成立。右邊的不等式顯然成立。所以所以A 的特征

59、值為的特征值為 - 2 , 0, 2 ; 其重?cái)?shù)依次記為其重?cái)?shù)依次記為1,2,1。故。故Spec A = 121202 對(duì)于左邊的不等式，因?qū)τ谧筮叺牟坏仁?，因A(G) 是對(duì)稱的，故不同的特是對(duì)稱的，故不同的特征值的數(shù)目征值的數(shù)目s 等于最小多項(xiàng)式的次數(shù)，即等于鄰接代數(shù)等于最小多項(xiàng)式的次數(shù)，即等于鄰接代數(shù)的的(G)的維數(shù)，于是所要的不等式由定理的維數(shù)，于是所要的不等式由定理11得到。得到。 編輯ppt75 定理定理14 設(shè)設(shè) m為為 圖圖G 的邊數(shù)，的邊數(shù)，A(G) 的譜為的譜為Spec A(G) = ssmmm2121則則 mmsiii212證明證明 因因A(G)的各特征值的平方組成矩陣的各

60、特征值的平方組成矩陣A(G) 2的特征的特征值組，即值組，即i2 是是A(G) 2 的特征值且重?cái)?shù)相同，故由代數(shù)的特征值且重?cái)?shù)相同，故由代數(shù)理論知理論知 等于等于A(G) 2的的跡跡（A(G) 2的對(duì)角線元素的對(duì)角線元素的和）。的和）。siiim12 而而A(G) 2的跡有的跡有niiia1)2(mvdnii2)(1定理定理10的推論的推論及握手定理及握手定理編輯ppt76mmsiii212故故證明證明 設(shè)設(shè)A(G)的的n 個(gè)特征值為個(gè)特征值為1, 2, n。不妨設(shè)。不妨設(shè)=n。對(duì)向量。對(duì)向量 (1,1,1) 和和 (1, 2, n-1) 應(yīng)用許瓦茲應(yīng)用許瓦茲（Schwarz）不等式，得）不等