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

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

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

4、廣泛應用科學，也能應用于社會科學。它非但廣泛應用于電信網絡、電力網絡、運輸能力開關理論、于電信網絡、電力網絡、運輸能力開關理論、編碼理論、控制論、反饋理論、隨機過程、可編碼理論、控制論、反饋理論、隨機過程、可靠性理論、化學化合物的辨認、計算機的程序靠性理論、化學化合物的辨認、計算機的程序設計、故障診斷、人工智能、印刷電路板的設設計、故障診斷、人工智能、印刷電路板的設計、圖案識別、地圖著色、情報檢索，也應用計、圖案識別、地圖著色、情報檢索，也應用于語言學、社會結構、經濟學、運籌學、遺傳于語言學、社會結構、經濟學、運籌學、遺傳學等。學等。圖論作為一個數學分支，有一套完整圖論作為一個數學分支，有一套

5、完整的體系和廣泛的內容，在這里我們的體系和廣泛的內容，在這里我們只準備介紹圖論的初步知識，其目只準備介紹圖論的初步知識，其目的是今后在其它有關學科的學習和的是今后在其它有關學科的學習和研究時，可以用圖論的基本知識作研究時，可以用圖論的基本知識作為工具。為工具。1.1 1.1 圖和簡單圖圖和簡單圖 一圖的定義一圖的定義 定義定義1 一個圖一個圖 G 定義為一個有序對定義為一個有序對(V, E)，記為，記為G = (V, E)，其中其中 （1）V是一個非空集合，稱為頂點集或點集，其元素稱是一個非空集合，稱為頂點集或點集，其元素稱為頂點或點；為頂點或點； （2）E是由是由V中的點組成的無序點對構成的

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

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

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

9、稱為都稱為復合圖。復合圖。簡單圖簡單圖非非簡單簡單圖圖例例3 3 平凡圖平凡圖 (3) 點集與邊集均為有限集合的圖稱為點集與邊集均為有限集合的圖稱為有限圖有限圖，本書只討，本書只討論有限圖。只有一個頂點而無邊的圖稱為論有限圖。只有一個頂點而無邊的圖稱為平凡圖平凡圖。邊集為。邊集為空的圖稱為空的圖稱為空圖空圖。二圖的同構二圖的同構定義定義2 設有兩個圖設有兩個圖G1 = (V1, E1)和和G2 = (V2, E2)，若在其頂，若在其頂點集合之間存在雙射，即存在一一對應的關系，使得邊之點集合之間存在雙射，即存在一一對應的關系，使得邊之間有如下的關系：設間有如下的關系：設1 11u vE2 22u

10、 vE1 1u v2 2u v當且僅當當且僅當， ；且；且的重數與的重數與的重數相同，則稱兩圖同構，記為的重數相同，則稱兩圖同構，記為G1 G2。12uu12vv111,u vV222,u vV，對應為：，對應為：編輯ppt16例如例如 說明：說明：(1) 兩個同構的圖均有相同的結構，沒有本質上的兩個同構的圖均有相同的結構，沒有本質上的差異差異, 差異只是頂點和邊的名稱不同。差異只是頂點和邊的名稱不同。（2）圖同構的幾個必要條件：圖同構的幾個必要條件： 頂點數相同；頂點數相同； 邊數邊數相同；相同； 度數度數相等的頂點個數相同。相等的頂點個數相同。定義定義 設設 v為為 G 的頂點，的頂點，G

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

12、的集合，劃分為一些等價類，即相互同構的圖作成同一個等價類。同一個等價類。編輯ppt18（3）在圖的圖形表示中我們可以不給圖的點和在圖的圖形表示中我們可以不給圖的點和邊標上符號，稱這樣的圖為邊標上符號，稱這樣的圖為非標定（號）圖非標定（號）圖，否，否則稱為則稱為標定（號）圖標定（號）圖。非標定圖實際上是代表一。非標定圖實際上是代表一類相互同構的圖。類相互同構的圖。 不誤解時我們也不嚴格區分標定圖與非標定圖。不誤解時我們也不嚴格區分標定圖與非標定圖。（4）判定圖的同構是很困難的，屬于判定圖的同構是很困難的，屬于NP完全完全問題。對于規模不大的兩個圖，判定其是否同問題。對于規模不大的兩個圖，判定其是

13、否同構，可以采用觀察加推證的方法。構，可以采用觀察加推證的方法。編輯ppt19 例例 證明下面兩圖同構。證明下面兩圖同構。證明證明 作映射作映射 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) 容易驗證容易驗證 ，對，對 vi v j E (a), 有有 f (v i vj,) ui,uj, E(b) ，(1 i 10, 1 j 10 )由圖的同構定義知，圖由圖的同構定義知，圖(a)與與(b)是同構的。是同構的。編輯ppt

14、20 例例 判斷下面兩圖是否同構。判斷下面兩圖是否同構。u1v1解解 兩圖不同構。兩圖不同構。這是因若同構，則兩圖中唯一的與環關聯的兩個點這是因若同構，則兩圖中唯一的與環關聯的兩個點u1 與與v1 一定相對應，而一定相對應，而u1的兩個鄰接點與的兩個鄰接點與v1的兩個鄰接點狀況不的兩個鄰接點狀況不同（同（ u1鄰接有鄰接有4度點，而度點，而v1 沒有）。沒有）。 所以，兩圖不同構。所以，兩圖不同構。編輯ppt21三完全圖三完全圖 ，偶圖，偶圖 ，補圖，補圖 完全圖：完全圖：任意兩點均相鄰的簡單圖稱為完全圖，任意兩點均相鄰的簡單圖稱為完全圖，在同構意義下，在同構意義下，n 階完全圖只有一個，記為

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

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

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

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

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

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

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

22、正是推論推論1的結論。的結論。編輯ppt32推論推論2 正則圖的階數和度數不同時為奇數。正則圖的階數和度數不同時為奇數。證明證明 設設G是是k-正則圖，若正則圖，若k為奇數，則由推論為奇數，則由推論1知正則圖知正則圖G的點數必為偶數。的點數必為偶數。 度序列度序列: 一個圖一個圖G的各個點的度的各個點的度d1, d2, dn構成的非負整數構成的非負整數 組組 (d1, d2, dn)稱為稱為G的度序列的度序列 。它是刻畫圖的特。它是刻畫圖的特 征的重要征的重要“拓撲不變量拓撲不變量”。正整數正整數k的劃分的劃分: 是指將是指將k表示為若干正整數的和表示為若干正整數的和,或指一或指一 個無序正整

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

24、是，以它為度序列，則稱這個數組是可圖的可圖的。 編輯ppt34mdnii21), 1, 1, 1(213211nddddddd定理定理5 設有非負整數組設有非負整數組 = (d1, d2, dn)，且，且是一個偶數，是一個偶數，n-1d1d2dn， 是可圖的充要條件為是可圖的充要條件為是可圖的。是可圖的。例例 試判斷下列非負整數組試判斷下列非負整數組 是否可圖是否可圖?5 5 3 3 2 2 2 4 2 2 1 1 2 解解 利用定理利用定理5可得下列非負整數組可得下列非負整數組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 關于圖序列，主要研究的關于圖序列，主要研究的3個問題個問題：（：（1）存在問題（什存在問題（什么樣的整數組是圖序列？）已么樣的整數組是圖序列？）已解決；解決；(2) 計數問題（一個圖計數問題（一個圖序列對應多少不同構的圖？）序列對應多少不同構的圖？）解決得不好；解決得不好；(3) 構造問題構造問題（如何畫出圖序列對應的所有不同構圖？）（如何畫出圖序列對應的所有不同構圖？）沒有解決。沒有解決。編輯ppt361.2 子圖與圖的運算子圖與圖的運算一一. 子圖子圖 定義定義1 1 設設G 和和H為兩個圖，若為兩個

26、圖，若V(H) V(G) , E(H) E(G) ,且且H中邊的重數不超過中邊的重數不超過G中對應邊的重數，則稱中對應邊的重數，則稱H 是是G 的的子圖子圖. 記為記為H G 。有時又稱。有時又稱G是是H的母圖。的母圖。 當當H G ，但，但H G時，則記為時，則記為H G ，且稱，且稱H為為G的的真子圖真子圖。G的的生成子圖生成子圖是指滿足是指滿足V(H) = V(G)的子圖的子圖H。例如例如編輯ppt37 上圖中，上圖中，H1與與H2均為均為G 的子圖，其中的子圖，其中H2 是是G 的生成子圖，的生成子圖，而而H1 則不是。則不是。v1v2v3v4v5v1v3v4v2G H1 v1v3v4

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

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

29、的運算圖的運算設設G1，G2是是G 的子圖的子圖, 有下列術語與概念有下列術語與概念 G1和和G2不相交不相交: 指它們無公共頂點指它們無公共頂點.G1和和G2邊不重邊不重 : 指它們無公共邊指它們無公共邊.并圖并圖G1G2 ：是指其頂點集為是指其頂點集為V(G1)V(G2)，邊集，邊集為為E(G1)E(G2) 的的G 的一個子圖的一個子圖 ；如果；如果G1和和G2是不是不相交的，有時就記其并圖為相交的，有時就記其并圖為G1+G2。 交圖交圖G1G2 ：類似地定義類似地定義對稱差對稱差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的每個頂的每個頂點和點和G2的每個頂點連接起來所得到的圖稱為的每個頂點連接起來所得到的圖稱為G1和和

31、G2的聯的聯圖，記為圖，記為G1G2。例例v1 v2v4 v3 G2v1 v2v4 v3 G1G2u1u1G1有：有： K1K4=K5，K2K3=K5 K6= K1K5 = K2K4 = K3K3。編輯ppt43定義定義3 設設G1= (V1, E1)，G2 = (V2, E2)，對點集，對點集V = V1V2中中的任意兩個點的任意兩個點u = (u1,u2)和和v = (v1,v2)，當，當(u1 = v1和和 u2 adj v2) 或或 (u2 = v2 和和 u1 adj v1) 時就把時就把 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個點，它的點可以用個點，它的點可以用a1 a2an來標定，其中來標定，其中ai是是0或者或者1。

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

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

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

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

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

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

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

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

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

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

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

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

45、0相鄰相鄰的三個點的標號的三個點的標號;（c）取小圓點中標號取小圓點中標號最小者得最小者得 u1； u0 742155813 2 4 7u1 （d）對與對與u1相鄰的小圓點，相鄰的小圓點，用用 l (u1) + w (u1v) = 2+1 = 3更新標號更新標號4； 2+5=7 更新兩個更新兩個；u0 742155813 2 7 37 7u1 （e）取小圓點中標號取小圓點中標號 最小者得最小者得 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三三. . 算法分析算法分析好算法好算法 一個圖論算法如果在任何一個具有一個圖論算法如果在任何一個具有m條邊的條邊的n階階圖圖G上施行這個算法所需要的計算步數都可由上施行這個算法所需要的計算步數都可由n和和m的一的一個多項式（例如個多項式（例如3n2m）為其上界）為其上界, 則稱該算法是好的則稱該算法是好的. Dijkstra算法總共需作算法總共需作 n(n-1)/2 次加法和次加法和 n(n-1)/2 次比次比較較, 確定一個點是否屬于或不屬于確定一個點是否屬于

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

48、31238,8,5,3.xxxxxx容易算出容易算出(x1,x2,x3) 的組合形式共的組合形式共24種。種。 每種組合用一個點表示，若點每種組合用一個點表示，若點u能通過倒酒的方式變能通過倒酒的方式變換為換為v,則則 u向向v 連有向邊，并將各邊賦權連有向邊，并將各邊賦權1，得一個有向權，得一個有向權圖。圖。于是問題轉化為在該圖中求于是問題轉化為在該圖中求 (8,0,0)到到(4,4,0)的一條最短路的一條最短路(求最短路的算法在有向圖中仍適用求最短路的算法在有向圖中仍適用)。結果如下：。結果如下：(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 圖的代數表示及特征圖的代數表示及特征一一. 鄰接矩陣鄰接矩陣 定義：定義：設設 n 階標定圖階標定圖G = (V,E)，V = v1,v2, vn，則則 G 的鄰接矩陣是一個的鄰接矩陣是一個nn 矩陣矩陣A(G) = aij (簡記為簡記為A)，其中若，其中若 vi鄰接鄰接vj，則，則aij =1;否則否則aij =0。 注注: 若若aij 取為連接取為連接vi與與vj 的邊的數目的邊的數目, 則稱則稱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) 鄰接矩陣是一個對稱方陣。鄰接矩陣是一個對稱方陣。 (2) 簡單標定圖的鄰接矩陣的各行簡單標定圖的鄰接矩陣的各行 (列列) 元素之和是該行元素之和是該行 (列列) 對應的點的度。對應的點的度。 （3）若若A1和和A2是對應于同一個是對應于同一個G的兩種不同的標定的鄰的兩種不同的標定的鄰接矩陣，則接矩陣，則 A1和和A2 是相似的。即存在一個可逆矩陣是相似的。即存在一個可逆矩陣P有有112AP A P（4）G是連通的當且僅當沒有是連通的當且僅當沒有G的點的一種標定法使的點的一種標定法使 它的鄰接矩

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 的長為的長為2的的通道的數目為的的通道的數目為1 v1到到 v2 的長為的長為2的的通道的數目為的的通道的數目為0v1到到 v3 的長為的長為2的的通道的數目為的的通道的數目為2v1到到 v4的長為的長為2的的通道的數目為的的通道的數目為0 v2到到 v2 的長為的長為2的的通道的數目為的的通道的數目為5 編輯ppt67定理定理

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

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

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

55、e7 e2 e4v3 e3 v4例例B = e1 e2 e3 e4 e5 e6 e7v1v2v3v4v500110001001100010011000000111110001編輯ppt70說明：說明：定義中定義中“無無環環”的條件可去掉，此時的條件可去掉，此時bij =點點vi 與邊與邊ej 關聯的次數（關聯的次數（0, 1, 2(環環).性質：性質：關聯矩陣的每列和為關聯矩陣的每列和為2；其行和為對應頂點的度數；其行和為對應頂點的度數.例如：例如：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三、鄰接代數三、鄰接代數 給定圖給定圖G , 容易驗證容易驗證G 的鄰接矩陣的全體復系數多項的鄰接矩陣的全體復系數多項式在通常的矩陣運算下構成一個有限維的線性空間，它式在通常的矩陣運算下構成一個有限維的線性空間，它也是一個代數，稱為圖也是一個代數，稱為圖G的鄰接代數，記為的鄰接代數，記為(G)。 用圖用圖G的點數和直徑可以給出鄰接代數的點數和直徑可以給出鄰接代數(G)的維數的的維數的界。界。定理定理11 n階連通圖階連通圖G的鄰接代數的維數有的鄰接代數的維數有 d(G)dim(G)n編輯ppt72 回憶線性代數的一些概念。設回憶線性代數的一些概念。設A = (aij

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

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

59、值為的特征值為 - 2 , 0, 2 ; 其重數依次記為其重數依次記為1,2,1。故。故Spec A = 121202 對于左邊的不等式，因對于左邊的不等式，因A(G) 是對稱的，故不同的特是對稱的，故不同的特征值的數目征值的數目s 等于最小多項式的次數，即等于鄰接代數等于最小多項式的次數，即等于鄰接代數的的(G)的維數，于是所要的不等式由定理的維數，于是所要的不等式由定理11得到。得到。 編輯ppt75 定理定理14 設設 m為為 圖圖G 的邊數，的邊數，A(G) 的譜為的譜為Spec A(G) = ssmmm2121則則 mmsiii212證明證明 因因A(G)的各特征值的平方組成矩陣的各

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