圖論課件第1章

1、第一章第一章 圖的基本概念圖的基本概念l 圖和簡單圖圖和簡單圖l 子圖與圖的運算子圖與圖的運算l 路與圖的連通性路與圖的連通性l 最短路及其算法最短路及其算法l 圖的代數表示及其特征圖的代數表示及其特征l 極圖極圖1.1 圖和簡單圖圖和簡單圖 一一、圖的定義圖的定義定義定義 一個圖一個圖G 定義為一個有序對定義為一個有序對(V, E)，記為，記為G = (V, E)，其中其中 (1) V 是一個非空集合，稱為是一個非空集合，稱為頂點集頂點集或或點集點集，其元素稱為，其元素稱為頂點頂點或或點點；(2) E 是由是由V 中的點組成的無序點對構成的集合，稱為中的點組成的無序點對構成的集合，稱為邊集邊

2、集，其元素稱為其元素稱為邊邊，且同一點對在，且同一點對在E中可出現(xiàn)多次。中可出現(xiàn)多次。注：注：圖圖G 的頂點集記為的頂點集記為V(G)，邊集記為邊集記為E(G)。圖。圖G 的頂點的頂點數數( (或階數或階數) )和邊數可分別用符號和邊數可分別用符號n(G)和和m(G)表示。表示。例例 設設V =v1, v2, v3, v4，E =v1v2 , v1v2, v2v3 ，則，則G = (V, E)是是一個一個4 4階圖。階圖。若用小圓點代表點，連線代表邊，則可將一個圖用若用小圓點代表點，連線代表邊，則可將一個圖用“圖形圖形”來表示來表示, , 如例中的圖可表示為如例中的圖可表示為v1v2v3v4注

3、：注：也可記邊也可記邊uv為為e，即，即e = uv。v1v2v3v4e1e2e3e4e5例例 設設V = v1,v2,v3,v4，E = e1,e2,e3,e4,e5，其中其中 e1= v1v2，e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4，則則G = (V, E)是一個圖。是一個圖。(1) 若邊若邊e = uv, , 此時稱此時稱u和和v是是e 的的端點端點; ; 并稱并稱u和和v相鄰相鄰，u ( (或或v) )與與e相關聯(lián)相關聯(lián)。若兩條邊有一個共同的端點，則稱這兩條。若兩條邊有一個共同的端點，則稱這兩條邊邊相鄰相鄰。(2) 孤立點：孤立點：不與任何

4、邊相關聯(lián)的點；不與任何邊相關聯(lián)的點； 自環(huán)：自環(huán)：兩端點重合的邊；兩端點重合的邊； 重邊：重邊：連接兩個相同頂點的邊的條數，叫做邊的連接兩個相同頂點的邊的條數，叫做邊的重數重數。 重數大于重數大于1 1的邊稱為的邊稱為重邊重邊。相關概念相關概念(4) 既沒有環(huán)也沒有重邊的圖稱為既沒有環(huán)也沒有重邊的圖稱為簡單圖簡單圖。其他所有的圖都。其他所有的圖都稱為稱為復合圖。復合圖。簡單圖簡單圖非非簡單簡單圖圖例例 平凡圖平凡圖(3) 點集與邊集均為有限集合的圖稱為點集與邊集均為有限集合的圖稱為有限圖有限圖，本書只討論，本書只討論有限圖。只有一個頂點而無邊的圖稱為有限圖。只有一個頂點而無邊的圖稱為平凡圖平凡

5、圖。邊集為空的。邊集為空的圖稱為圖稱為空圖空圖。二、圖的同構二、圖的同構定義定義 設有兩個圖設有兩個圖G1 = (V1, E1)和和G2 = (V2, E2)，若在其頂點，若在其頂點集合之間存在雙射，即存在一一對應的關系，使得邊之間集合之間存在雙射，即存在一一對應的關系，使得邊之間有如下的關系：設有如下的關系：設u1, v1V1 , u2, v2V2, u1 u2, v1 v2, u1v1E1當且僅當當且僅當u2v2E2，且，且u1v1的重數與的重數與u2v2相等，則稱相等，則稱兩圖同構兩圖同構，記為，記為G1 G2。例例 注：注：(1) 兩個同構的圖均有相同的結構，沒有本質上的差兩個同構的圖

6、均有相同的結構，沒有本質上的差異異, , 差異只是頂點和邊的名稱不同。差異只是頂點和邊的名稱不同。(2) 圖同構的幾個必要條件：圖同構的幾個必要條件：頂點數相同；頂點數相同；邊數相同；邊數相同；度數相等的頂點個數相同。度數相等的頂點個數相同。(3) 在圖的圖形表示中我們可以不給圖的點和邊標上符號，稱在圖的圖形表示中我們可以不給圖的點和邊標上符號，稱這樣的圖為這樣的圖為非標定（號）圖非標定（號）圖，否則稱為，否則稱為標定（號）圖標定（號）圖。非標。非標定圖實際上是代表一類相互同構的圖。定圖實際上是代表一類相互同構的圖。不誤解時我們也不嚴不誤解時我們也不嚴格區(qū)分標定圖與非標定圖。格區(qū)分標定圖與非標

7、定圖。 (4) 判定圖的同構是很困難的。對于規(guī)模不大的兩個圖，判判定圖的同構是很困難的。對于規(guī)模不大的兩個圖，判定其是否同構，可以采用觀察加推證的方法。定其是否同構，可以采用觀察加推證的方法。定義定義 設設v為為G的頂點，的頂點，G 中以中以v為端點的邊的條數為端點的邊的條數( (環(huán)計算兩環(huán)計算兩次次) )稱為點稱為點v的的度數度數，簡稱為點，簡稱為點v的的度度，記為，記為dG (v)，簡記為簡記為d(v)。d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2v1v2v3v4v5例例 注：注：該圖中各點的度數之和等于該圖中各點的度數之和等

8、于14，恰好是邊數，恰好是邊數7的的兩倍兩倍。例例 證明下面兩圖同構。證明下面兩圖同構。證明證明 作映射作映射 f : vi ui (i=1,2.,10)，易知該，易知該映射為雙射。映射為雙射。容易驗證，對容易驗證，對 vi v j E (a)， 有有 f (vivj) ui uj E(b) ，(1 i 10, 1 j 10 )由圖的同構定義知，圖由圖的同構定義知，圖(a)與與(b)是同構的。是同構的。v5v1v2v4v3v10v6v7v8v9(a)u1u2u3u4u5u6u7u8u9u10(b)例例 判斷下面兩圖是否同構。判斷下面兩圖是否同構。u1v1解解 兩圖不同構。兩圖不同構。若兩圖同構

9、，則兩圖中唯一的與環(huán)關聯(lián)的兩個點若兩圖同構，則兩圖中唯一的與環(huán)關聯(lián)的兩個點u1與與v1一定一定相對應，而相對應，而u1的兩個鄰接點與的兩個鄰接點與v1的兩個鄰接點狀況不同，的兩個鄰接點狀況不同，u1鄰接有鄰接有4度點，而度點，而v1沒有。沒有。所以，兩圖不同構。所以，兩圖不同構。例例 指出指出4個頂點的非同構的所有簡單圖。個頂點的非同構的所有簡單圖。分析：分析：四個頂點的簡單圖最少邊數為四個頂點的簡單圖最少邊數為0，最多邊數為，最多邊數為6，所以，所以可按邊數進行枚舉?？砂催厰颠M行枚舉。解解(a)(b)(c)(d)(e)(f)(g)三、完全圖，偶圖，補圖三、完全圖，偶圖，補圖定義定義 任意兩點

10、均相鄰的簡單圖稱為任意兩點均相鄰的簡單圖稱為完全圖完全圖，在同構意義，在同構意義下，下，n 階完全圖只有一個，記為階完全圖只有一個，記為Kn。K2K3K4例例 K2, K3, K4分別為如下圖所示分別為如下圖所示。K30定義定義 若一個圖的點集可以分解為兩個（非空）子集若一個圖的點集可以分解為兩個（非空）子集X 和和Y，使得每條邊的一個端點在使得每條邊的一個端點在X中，另一個端點在中，另一個端點在Y中，則這樣中，則這樣的圖稱為的圖稱為具有二分類具有二分類（X, Y）的偶圖（或二部圖）的偶圖（或二部圖）。完全偶圖完全偶圖是指具有二分類是指具有二分類(X, Y )的簡單偶圖，其中的簡單偶圖，其中X

11、的的每個頂點與每個頂點與Y 的每個頂點相連，若的每個頂點相連，若 |X|=m，|Y|=n，則這，則這樣的偶圖記為樣的偶圖記為Km,n。例例偶圖偶圖不是偶圖例例 K3, 3 K1, 3 G1 G2 四個圖均為偶圖四個圖均為偶圖K1, 3, K3, 3為完全偶圖為完全偶圖 偶圖是一種常見數學模型。偶圖是一種常見數學模型。例例 學校有學校有6位教師將開設位教師將開設6門課程。六位教師的代號分別是門課程。六位教師的代號分別是xi (i=1,2,3,4,5,6 )，六門課程代號是，六門課程代號是yi (i=1,2,3,4,5,6 )。已知教。已知教師師x1能夠勝任課程能夠勝任課程y2和和y3；教師；教師

12、x2能夠勝任課程能夠勝任課程y4和和y5；教師；教師x3能夠勝任課程能夠勝任課程y2；教師；教師x4能夠勝任課程能夠勝任課程y6和和y3；教師；教師x5能夠能夠勝任課程勝任課程y1和和y6；教師；教師x6能夠勝任課程能夠勝任課程y5和和y6。請畫出老師和。請畫出老師和課程之間的狀態(tài)圖。課程之間的狀態(tài)圖。解解x1x5x4x3x2x6y4y3y1y2y5y61, ,Euv uv u vV簡單圖簡單圖G 的的補圖：補圖：設設G =(V, E) )，則圖，則圖H =(V, E1E)稱為稱為G 的的補圖，記為補圖，記為 ，其中集合，其中集合HG例例 下圖中的下圖中的(a)，(b)兩圖是互補的。兩圖是互補

13、的。(a)(b)定理定理 若若n 階圖階圖G是自補的（即是自補的（即 ），則），則 n = 0, 1 (mod 4)。GG證明證明 因為因為G 是自補的，則是自補的，則G 和其補圖有同樣多的邊數，且和其補圖有同樣多的邊數，且邊數邊數(1)( )( )()2nn nm Gm Gm K。從而從而(1)()4n nm G。又因又因G的邊數的邊數m(G)是整數，故是整數，故n(n-1)/4為整數，即只能有為整數，即只能有n0 (mod 4) 或或 (n-1)0 (mod 4)。 四、頂點的度、度序列四、頂點的度、度序列設設v為為G 的頂點，的頂點，G 中以中以v為端點的邊的條數為端點的邊的條數( (環(huán)

14、計算兩次環(huán)計算兩次) )稱稱為點為點v的度數，簡稱為點的度數，簡稱為點v的的度度，記為，記為dG (v)，簡記為簡記為d(v)。奇點：奇點：度數為奇數的頂點度數為奇數的頂點相關術語和記號相關術語和記號 G：圖圖G 的頂點的最小度的頂點的最小度 G：圖圖G 的頂點的最大度的頂點的最大度偶點：偶點：度數為偶數的頂點度數為偶數的頂點k-正則圖正則圖: : 每個點的度均為每個點的度均為k 的的簡單圖簡單圖例如，完全圖和完全偶圖例如，完全圖和完全偶圖Kn, n 均是正則圖。均是正則圖。 對任意的有對任意的有m 條邊的圖條邊的圖G = (V, E )，有有證明證明 因圖因圖G 的任一條邊均有兩個端點的任一

15、條邊均有兩個端點 ( (可以相同可以相同) )，在計算，在計算度時恰被計算兩次度時恰被計算兩次 ( (每個端點各被計算了一次每個端點各被計算了一次) )，所以各點，所以各點的度數之和恰好為邊數的兩倍。的度數之和恰好為邊數的兩倍。定理定理 ( (圖論基本定理圖論基本定理) )注：注：該定理也稱為該定理也稱為握手定理握手定理，是由歐拉提出的：，是由歐拉提出的：在一個聚在一個聚會上，朋友相互見面時握一次手，則握手次數是握手人次會上，朋友相互見面時握一次手，則握手次數是握手人次的兩倍的兩倍。歐拉一生發(fā)表論文。歐拉一生發(fā)表論文850余余篇，著作篇，著作25余余部。部。( )2v Vd vm。推論推論 任

16、意圖中，奇點的個數為偶數。任意圖中，奇點的個數為偶數。證明證明 設設V1，V2分別是分別是G 中偶點集和奇點集。則由握手定理中偶點集和奇點集。則由握手定理知：知： 12v Vv Vd vd v偶數。顯然第一個求和式為偶數，而第二個求和式中的每一項均顯然第一個求和式為偶數，而第二個求和式中的每一項均為奇數，所以第二個求和式必然有偶數項，即度數為奇數為奇數，所以第二個求和式必然有偶數項，即度數為奇數的頂點個數必為偶數。的頂點個數必為偶數。推論推論 正則圖的階數和度數不同時為奇數。正則圖的階數和度數不同時為奇數。證明證明 設設G 是是k- -正則圖，若正則圖，若k 為奇數，則由推論知正則圖為奇數，則

17、由推論知正則圖G的點數必為偶數。的點數必為偶數。 例例 設設與與是簡單圖是簡單圖G 的最大度與最小度，求證：的最大度與最小度，求證： 2 mn 。()()2vVGndvmn，證明證明 由握手定理知由握手定理知所以所以2 mn 。定義定義 一個圖一個圖G 的各個點的度的各個點的度d1, d2, dn構成的非負整數組構成的非負整數組(d1, d2, dn)稱為稱為G 的的度序列度序列。定理定理 非負整數組非負整數組(d1, d2,.,dn)是圖的度序列的充分必要條件是圖的度序列的充分必要條件是：是：di 為偶數。為偶數。證明證明 必要性由握手定理立即得到。必要性由握手定理立即得到。如果如果di為偶

18、數，則數組中為奇數的數字個數必為偶數。為偶數，則數組中為奇數的數字個數必為偶數。按照如下方式作圖按照如下方式作圖G: 若若di為偶數，則在與之對應的點作為偶數，則在與之對應的點作di /2個環(huán)；對于剩下的偶數個奇數，個環(huán)；對于剩下的偶數個奇數，兩兩配對后分別在每配對兩兩配對后分別在每配對點間先連一條邊，然后在每個頂點畫點間先連一條邊，然后在每個頂點畫(dj - -1)/2個環(huán)。個環(huán)。該圖的度序列就是已知數組。該圖的度序列就是已知數組。定義定義 對于一個非負整數組對于一個非負整數組(d1, d2, dn)，若存在一個，若存在一個簡單簡單圖圖G，以它為度序列，則稱這個數組是，以它為度序列，則稱這個

19、數組是可圖的可圖的?？蓤D的序列?？蓤D的序列簡稱為簡稱為可圖序列可圖序列或或圖序列圖序列。關于可圖序列，主要研究關于可圖序列，主要研究3個問題：個問題：(1) 存在問題存在問題：什么樣的整數組是可圖序列？：什么樣的整數組是可圖序列？(2) 計數問題計數問題：一個可圖序列對應多少不同構的圖？：一個可圖序列對應多少不同構的圖？(3) 構造問題構造問題：如何畫出可圖序列對應的所有不同構圖？：如何畫出可圖序列對應的所有不同構圖？(1)徹底解決了；徹底解決了；(2)解決得不好；解決得不好；(3)沒有解決。沒有解決。研究現(xiàn)狀研究現(xiàn)狀定理定理 設有非負整數組設有非負整數組= (d1, d2, dn)滿足滿足1

20、212ninddddm且，則則是可圖序列的充分必要條件是：是可圖序列的充分必要條件是：1112312(1,1,1,)ddnddddd 是可圖序列。是可圖序列。證明證明 充分性顯然，我們只需證明必要性。充分性顯然，我們只需證明必要性。設設G 是是對應的簡單圖，對應的簡單圖，d (vi)=di 。情形情形1：點點v1與點與點v2, v3,vd1+1鄰接，則刪去頂點鄰接，則刪去頂點v1及其關聯(lián)及其關聯(lián)的邊所得到的圖的度序列正好為的邊所得到的圖的度序列正好為1。情形情形2：點點v1與點與點vd1+2,vn 的某些頂點鄰接。的某些頂點鄰接。假設：假設：設設v1與與vj0鄰接，但當鄰接，但當kj0 時，時

21、，v1與與vk不鄰接；又設不鄰接；又設v1與與vi0不鄰接，但當不鄰接，但當k2。(非連通圖的直徑定義為非連通圖的直徑定義為)不妨假設不妨假設u和和v1, v2,vk相鄰。相鄰。為了保證為了保證u到各點距離不超過到各點距離不超過2，vk+1,.vn-2這些頂點的每一這些頂點的每一個必須和前面?zhèn)€必須和前面v1, v2, vk中某點相鄰，這樣，圖中至少又有中某點相鄰，這樣，圖中至少又有n- -2條邊。條邊。因此，總共至少有因此，總共至少有2n- -4條邊。條邊。定理定理 若圖若圖G 是不連通的，則其補圖是連通圖。是不連通的，則其補圖是連通圖。證明證明 因因G是不連通，故是不連通，故G中至少兩個分支

22、。中至少兩個分支。設設u，v是是G 的任意兩個頂點。的任意兩個頂點。若若u和和v在在G中不鄰接，則在補圖中它們鄰接。中不鄰接，則在補圖中它們鄰接。若若u和和v在在G中鄰接，則它們屬于中鄰接，則它們屬于G的同一分支。的同一分支。在另一個分支中取一點在另一個分支中取一點w，則在補圖中，則在補圖中u和和v均與均與w鄰接，從鄰接，從而而uwv是一條途徑是一條途徑, 故在補圖中它們鄰接。故在補圖中它們鄰接。因此因此G的補圖是連通圖。的補圖是連通圖。定理定理 設圖設圖G為為n階圖，若階圖，若G中任意兩個不相鄰頂點中任意兩個不相鄰頂點u與與v滿足滿足d(u)+d(v)n- -1，則，則G是連通圖且是連通圖且

23、d(G)2。證明證明 我們將證明，對我們將證明，對G中任意兩點中任意兩點x與與y，一定存在一條長，一定存在一條長度至多為度至多為2的連接的連接x與與y的路。的路。若若x和和y相鄰，則上述論斷成立。相鄰，則上述論斷成立。若若x和和y不相鄰，則一定存在一點不相鄰，則一定存在一點w與與x和和y均相鄰。均相鄰。若不然，在若不然，在G的剩下的的剩下的n-2個頂點中，假設有個頂點中，假設有k個與個與x鄰接，但鄰接，但與與y不鄰接，有不鄰接，有l(wèi)個頂點和個頂點和y鄰接，但不與鄰接，但不與x鄰接，同時假定有鄰接，同時假定有m個頂點與個頂點與x和和y均不相鄰。均不相鄰。那么那么d(x)=k，d(y)=l。由于由

24、于k+l+m=n- -2，所以，所以d(x)+d(y)=n- -2- -mn- -2，矛盾！，矛盾！三、偶圖判定定理三、偶圖判定定理定理定理 一個圖是偶圖當且當它不包含奇圈。一個圖是偶圖當且當它不包含奇圈。證明證明 一個圖是偶圖當且僅當每個連通分支是偶圖，一個圈一個圖是偶圖當且僅當每個連通分支是偶圖，一個圈只能屬于一個連通分支，因此我們只需對連通圖證明即可。只能屬于一個連通分支，因此我們只需對連通圖證明即可。設設G是具有二分類是具有二分類(X, Y)的偶圖，并且的偶圖，并且C = v0v1vkv0是是G的任的任意一個圈。意一個圈。不失一般性，可假定不失一般性，可假定v0X。這樣，。這樣，v2i

25、X，且，且v2i +1Y。又因為又因為v0X，所以，所以vkY。由此即得。由此即得C是偶圈。是偶圈。接下來證明充分性。接下來證明充分性。設設G是不包含奇圈的連通圖。是不包含奇圈的連通圖。任選一個頂點任選一個頂點u且定義且定義V 的一個分類的一個分類（X, Y）如下：如下：X = x | d (u, x) 是偶數，是偶數，xV(G) ，Y = y | d (u, y) 是奇數，是奇數，yV(G) ?，F(xiàn)在證明現(xiàn)在證明( X, Y )是是G的一個二分類。的一個二分類。斷言：斷言：對對X中任意兩點中任意兩點v與與w，必不相鄰！，必不相鄰！設設P是一條最短是一條最短(u , v)路，而路，而Q是一條最短

26、是一條最短的的(u, w)路。路。設設u1是是P和和Q的最后一個交點。的最后一個交點。由于由于P，Q是最短路，所以是最短路，所以P，Q中中u到到u1段長段長度相同，因此奇偶性相同。度相同，因此奇偶性相同。又因為又因為P，Q的長度均是偶數，所以的長度均是偶數，所以P，Q中中u1v段和段和u1w段段奇偶性相同。奇偶性相同。 如果如果v與與w相鄰，則可得到奇圈，矛盾！相鄰，則可得到奇圈，矛盾！所以所以(X, Y )是是G的一個二分類。的一個二分類。類似地，類似地，Y中任意兩個頂點也不相鄰。中任意兩個頂點也不相鄰。QPvuwu11.4 最短路及其算法最短路及其算法定義定義 若圖若圖G的每一條邊的每一條

27、邊e都附有一個實數都附有一個實數w(e)，稱為稱為e的的權權,則則G連同它邊上的權稱為連同它邊上的權稱為賦權圖賦權圖。若若H是一個賦權圖，則是一個賦權圖，則H的各邊權之和稱為的各邊權之和稱為圖圖H的權的權，記為，記為W(H)。例例 右圖右圖G為賦權圖，為賦權圖，v1v3v2v4 G 1 3 5 6 5其中其中w(v1v2) = 1，w(v1v3) = 5，W(G) = 20。一、一、 賦權圖賦權圖 定義定義 設設G為賦權圖，為賦權圖，u與與v是是G中兩點，在連接中兩點，在連接u與與v的所有路的所有路中，各邊權值之和最小的路，稱為中，各邊權值之和最小的路，稱為u與與v間的間的最短路最短路，最短路

28、，最短路的長度稱為的長度稱為u與與v的的距離距離，仍記為，仍記為 d(u, v)。例例 求求v2與與 v4的距離。的距離。v1v3v2v4 G 1 3 1 6 3易知，各邊的權均為易知，各邊的權均為1的賦權圖中的路長與非賦權圖中的的賦權圖中的路長與非賦權圖中的路長是一致的。路長是一致的。解解 d(v2, v4) = 5。相應的最短路為相應的最短路為 ：v2v1v3v4。二、最短路問題二、最短路問題 許多最優(yōu)化問題都可轉化為在一個賦權圖中找出某類具有最許多最優(yōu)化問題都可轉化為在一個賦權圖中找出某類具有最?。ɑ蜃畲螅嗟淖訄D，其中之一就是?。ɑ蜃畲螅嗟淖訄D，其中之一就是最短路問題：給出一最短路問

29、題：給出一個連接各城鎮(zhèn)的鐵路網絡，在這個網絡的兩個指定城鎮(zhèn)之間個連接各城鎮(zhèn)的鐵路網絡，在這個網絡的兩個指定城鎮(zhèn)之間試確定一條最短路線。試確定一條最短路線。數學模型：數學模型：在一個賦權圖中的兩個指定頂點在一個賦權圖中的兩個指定頂點a和和b之間找出一之間找出一條最短條最短(a, b)路。路。1959年，年，Dijkstra發(fā)表了一篇名為發(fā)表了一篇名為“A Note on Two Problems in Connexion with Graphs ”，這篇僅有兩頁半的文章發(fā)表在，這篇僅有兩頁半的文章發(fā)表在一流一流期刊期刊Numerische mathematik 上面。上面。這篇文章給出了解決最短

30、路問題的著名的這篇文章給出了解決最短路問題的著名的Dijkstra算法算法，同，同時指出：在此之前時指出：在此之前Ford和和Berge已經分別給出了解決最短路已經分別給出了解決最短路問題的方法。問題的方法。巧合的是，同年巧合的是，同年11月，月，“線性規(guī)劃之父線性規(guī)劃之父”Dantzig提交了一提交了一篇名為篇名為“ On the Shortest Path Route Through a Network ”的論文的論文，該論文第二年正式發(fā)表在，該論文第二年正式發(fā)表在Top期刊期刊Management Science上面。上面。該論文只有三頁半，也提出了解決最短路問題的算法，同時該論文只有三

31、頁半，也提出了解決最短路問題的算法，同時也提到也提到Ford的工作。的工作。2003年，年，Dantzig在其著作在其著作Linear Programming中曾提中曾提到到“About the same time, Dijkstra independently proposed a refined version of the same algorithm for finding the shortestdirected paths from a node to all other nodes.”，但，但Dantzig并并未給出具有說服力的依據。未給出具有說服力的依據。但肯定的是，但肯定的是

32、，F(xiàn)ord在在Network Flow Theory方面的工作是最方面的工作是最短路問題的先驅，也是短路問題的先驅，也是Dijkstra和和Dantzig工作的基礎。工作的基礎。Dantzig算法算法( (頂點標號法頂點標號法) ) t (ak)：點：點ak的標號值，表示點的標號值，表示點a1=a 到到ak的最短路長度；的最短路長度；Ai =a1, a2,., ai：已經標號的頂點集合；：已經標號的頂點集合；Ti ：a1到到ai的最短路上的邊所在的集合；的最短路上的邊所在的集合； l(e)：邊：邊e的權重；的權重；記號說明記號說明：Dantzig算法不僅找到了最短的算法不僅找到了最短的(a,

33、b)路，而且給出了路，而且給出了a到圖到圖G的所有其他頂點的最短路。的所有其他頂點的最短路。 N(ak)：與點：與點ak相鄰的所有點的集合，稱為相鄰的所有點的集合，稱為ak的鄰集的鄰集。Dantzig算法算法(1) 記記 a1=a, t(a1) =0, A1= a1, T1= ;(2) 若已經得到若已經得到Ai = a1, a2, ai ，且對于，且對于 1ki，已知已知 t(ak)。對每一個對每一個ak Ai，求一點：，求一點：( )( )()iikkikbN aAB使得：使得：()()()m in()ikikkkvBla blav；(3) 設有設有mi ，1mii，而，而bmi(i)是使是

34、使 取最小取最小值。令：值。令：( )()()iiiimmmt al a b( )11111, ()()(), iiiiiimimmiiimiabt at al a aTTa a；(4) 若若ai+1=b， 停止；否則，記停止；否則，記 ， 轉轉(2)。11iiiAAa例例 如圖所示，求點如圖所示，求點a到點到點b的距離。的距離。812614227924693av1v2v3v4v5v6b 1. A1= a，t(a) = 0，T1 = ;2. b1 (1)= v3 ;3. m1 = 1，a2 = v3，t(v3) = t(a) + l(av3) = 1 (最小最小)，T2 =av3;解解14.

35、A2 =a, v3， b1 (2) =v1，b2 (2) =v2 ；812614227924693av1v2v3v4v5v6b15. m2 = 1，a3 = v1， t(v1) = t(a) + l(av1) = 2 (最小最小)， T3 =av3, av1； 6. A3 =a, v3, v1，b1 (3) =v2，b2 (3) =v2， b3 (3) =v4 ； 7. m3 = 3, a4 = v4, t(v4) = t(v1) + l(v1v4) = 3 (最小最小)， T4 =av3, av1, v1v4 8. A4 = a, v3, v1, v4，b1 (4) = v2，b2 (4)

36、= v2，b3 (4) = v2, b4 (4) = v5 ；9. m4 = 4, a5 = v5, t(v5) = t(v4) + l(v4v5) = 6 (最小最小)， T5 =av3, av1, v1v4, v4v5 ;236236812614227924693av1v2v3v4v5v6b110. A5 = a, v3, v1, v4, v5，b1 (5) = v2，b2 (5) = v2，b3 (5) = v2 , b4 (5) = v2, b5 (5) = v2 ;11. m5 = 4, a6 = v2, t(v2) = t(v4) + l(v4v2) = 7 (最小最小)， T6

37、=av3, av1, v1v4, v4v5, v4v2;12. A6 = a, v3, v1, v4, v5, v2, b2 (6) = v6, b4 (6) = b，b5 (6) = v6， b6 (6) = v6 ;13. m6 = 6, a7 = v6, t(v6) = t(v2) + l(v2v6) = 9 (最小最小)， 7914. A7 = a, v3, v1, v4, v5, v2, v6, b4 (7) = b，b5 (7) =b，b7 (7) =b ;15. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小最小)， T8 =av3

38、, av1, v1v4, v4v5, v4v2, v2v6, v6b;于是知于是知a與與b的距離的距離d (a, b) = t (b) = 11，最短路為，最短路為 1426avvvvb 。T7 =av3, av1, v1v4, v4v5, v4v2, v2v6 ;1179236812614227924693av1v2v3v4v5v6b11.5 圖的代數表示及特征圖的代數表示及特征一、一、 鄰接矩陣鄰接矩陣定義定義 設設n階標定圖階標定圖G = (V, E)，V = v1, v2, vn，則則G的的鄰鄰接矩陣接矩陣是一個是一個nn 矩陣矩陣A(G) = aij (簡記為簡記為A)，其中若，其中

39、若 vi鄰接鄰接vj，則，則aij =1；否則；否則aij =0。注：注：若若aij 取為連接取為連接vi與與vj 的邊的數目，則稱的邊的數目，則稱A為為推廣的鄰接推廣的鄰接矩陣矩陣。 用鄰接矩陣或關聯(lián)矩陣表示圖，稱為用鄰接矩陣或關聯(lián)矩陣表示圖，稱為圖的代數表示圖的代數表示。用矩陣表示圖，主要有兩個優(yōu)點：用矩陣表示圖，主要有兩個優(yōu)點： (1) 能夠把圖輸入到計能夠把圖輸入到計算機中；算機中；(2) 可以用代數方法研究圖論。可以用代數方法研究圖論。鄰接矩陣鄰接矩陣 推廣的鄰接矩陣推廣的鄰接矩陣 v1v2v4v3e1e2e3e4e5例例0100101001010011A01001020020100

40、11A(1) 鄰接矩陣是一個對稱方陣。鄰接矩陣是一個對稱方陣。 (2) 簡單標定圖的鄰接矩陣的各行簡單標定圖的鄰接矩陣的各行 (列列) 元素之和是該行元素之和是該行 (列列) 對應的點的度。對應的點的度。 (3) 若若A1和和A2是對應于同一個是對應于同一個圖圖的兩種不同的標定的鄰的兩種不同的標定的鄰接矩陣，則接矩陣，則 A1和和A2 是相似的，即是相似的，即存在一個可逆矩存在一個可逆矩陣陣P使得使得A1=P- -1A2P。(4) G是連通的當且僅當沒有是連通的當且僅當沒有G的點的一種標定法使它的點的一種標定法使它 的鄰接矩陣有約化的形式的鄰接矩陣有約化的形式112200AAA。鄰接矩陣的性質

41、鄰接矩陣的性質v1到到v1的長為的長為2的通道的數目為的通道的數目為1 v1到到v2的長為的長為2的通道的數目為的通道的數目為0v1到到v3的長為的長為2的通道的數目為的通道的數目為2v1到到v4的長為的長為2的通道的數目為的通道的數目為0 v2到到v2的長為的長為2的通道的數目為的通道的數目為5 v1v2v4v3e1e2e3e4e5左圖的推廣的鄰接矩陣為左圖的推廣的鄰接矩陣為0100102002010011A例例計算得計算得21020050220510212A圖中圖中定理定理 令令G是一個有推廣鄰接矩陣是一個有推廣鄰接矩陣A的的 p階標定圖，則階標定圖，則An的的i 行行 j 列元素列元素a

42、ij(n)等于由等于由vi到到vj的長度為的長度為n的通道的數目。的通道的數目。證明證明 當當n = 0時，時，A0 = In (n階單位矩陣階單位矩陣)，從任一點到自身有，從任一點到自身有一條長度為零的通道，任何不同的兩點間沒有長度為零的一條長度為零的通道，任何不同的兩點間沒有長度為零的通道，從而命題對通道，從而命題對n = 0成立。成立。由于由于aik是聯(lián)結是聯(lián)結vi和和vk的長度為的長度為1的通道的數目，的通道的數目，akj(n)是聯(lián)結是聯(lián)結vk和和vj的長度為的長度為n的通道的數目，所以的通道的數目，所以 aikakj(n) 表示由表示由vi經過經過vk到到vj的長度為的長度為n+1的

43、通道的通道數目。數目。假設命題對假設命題對n成立，由成立，由An+1=AAn，故，故(1)( )1pnnijikkjkaa a。這表明命題對這表明命題對n+1成立。成立。于是對所有的于是對所有的k求和便得到求和便得到了由了由 vi 到到 vj 的長度為的長度為n+1的通道的通道數目，即數目，即 aij(n+1) 為由為由 vi 到到 vj 的長度為的長度為n+1的通道的通道數目。數目。推論推論 設設A為簡單圖為簡單圖G的鄰接矩陣，則的鄰接矩陣，則(1) A2 的元素的元素 aii(2) 是是 vi 的度數。的度數。A3 的元素的元素 aii(3) 是含是含 vi 的三角的三角形的數目的兩倍。形

44、的數目的兩倍。(2) 若若G是連通的，對于是連通的，對于ij，vi 與與vj 之間的距離是使之間的距離是使An 的的aij(n) 0 的最小整數的最小整數n。二、關聯(lián)矩陣二、關聯(lián)矩陣定義定義 無環(huán)圖無環(huán)圖G的的關聯(lián)矩陣關聯(lián)矩陣B(G) = bij (簡記為簡記為B)是一個是一個nm 矩陣，當點矩陣，當點vi 與邊與邊ej 關聯(lián)時關聯(lián)時 bij =1，否則，否則 bij =0。例例B = e1 e2 e3 e4 e5 e6 e7v1v2v3v4v500110001001100010011000000111110001注：注：定義中定義中“無無環(huán)環(huán)”的條件可去掉，此時的條件可去掉，此時bij =點

45、點vi 與邊與邊ej 關關聯(lián)的次數（聯(lián)的次數（0, 1, 2(環(huán)環(huán))）。）。例例e1v4v3v2v1e7e5e4e3e2e61 1 0 0 1 0 11 1 1 0 0 0 0( )0 0 1 1 0 0 10 0 0 1 1 2 0M G e1 e5v2 v5 e6 e7 e2 e4v1v3 e3 v4性質性質 關聯(lián)矩陣的每列和為關聯(lián)矩陣的每列和為2；其行和為對應頂點的度數。；其行和為對應頂點的度數。三、鄰接譜三、鄰接譜12121( )( )nnnnnf GE AGaaaa定義定義 圖的鄰接矩陣圖的鄰接矩陣A(G)的特征多項式：的特征多項式：稱為稱為圖圖G的特征多項式的特征多項式。定義定義

46、圖的鄰接矩陣圖的鄰接矩陣A(G)的特征多項式的特征值及其重數，的特征多項式的特征值及其重數，稱為稱為圖圖G的鄰接譜的鄰接譜，簡稱，簡稱譜譜，記為，記為Spec(G)。例例 求求Kn的譜。的譜。0111110111()11110nA K解解 Kn的鄰接矩陣為：的鄰接矩陣為：計算得計算得11111111()(1)(1)1111nnEA Kn -1。因此因此11Spec()11nnKn。例例 若兩個非同構的圖具若兩個非同構的圖具有相同的譜，則稱它們有相同的譜，則稱它們是同譜圖。求證：右面是同譜圖。求證：右面兩圖是同譜圖。兩圖是同譜圖。GH解解 G與與H顯然不同構。顯然不同構。通過直接計算得通過直接計

47、算得6432( )()74741f GfH 。所以所以G與與H是同譜圖。是同譜圖。例例 設簡單圖設簡單圖G=(n, m)的譜為的譜為1212Spec( )ssGmmm，則則212siiimm。證明證明 因因A的各特征值的平方組成矩陣的各特征值的平方組成矩陣A2的特征值，所以的特征值，所以2(2)11sniiiiiima。又因為又因為A2的對角線元素的和為的對角線元素的和為(2)11( )2nniiiiiad vm，因此因此212siiimm。例例 設設是簡是簡單圖單圖G=(n, m)的任意特征值，則：的任意特征值，則：2(1)m nn。證明證明 設設=1, 2, ,n是是G 的全部特征值。的全

48、部特征值。因為因為G是簡是簡單圖，從而單圖，從而A(G)的對角元全為零，所以的對角元全為零，所以123n 。22221232nm，又因為又因為對向量對向量(1, 1,1)與與(2,3,4,n) )應用柯西應用柯西- -施瓦茨不等式，施瓦茨不等式，得得22223231111nnn。將上述兩式分別代入第一個式子的左端和右端，便可得證。將上述兩式分別代入第一個式子的左端和右端，便可得證。注：注：對于圖譜的研究，開始于對于圖譜的研究，開始于20世紀世紀60年代。形成了代數圖年代。形成了代數圖論的主要研究方向之一。圖譜研究在流體力學，量子化學，論的主要研究方向之一。圖譜研究在流體力學，量子化學，量子物理

49、與非線性物理以及網絡技術中都有重要的應用。量子物理與非線性物理以及網絡技術中都有重要的應用。四、圖的鄰接代數四、圖的鄰接代數定義定義 設設A是無環(huán)圖是無環(huán)圖G的鄰接矩陣，容易驗證的鄰接矩陣，容易驗證01(),kkiGa Ia Aa AaC kZ對于矩陣的加法和數與矩陣的乘法來說構成復數域對于矩陣的加法和數與矩陣的乘法來說構成復數域C上的向上的向量空間，稱該空間為量空間，稱該空間為圖圖G的鄰接代數的鄰接代數。定理定理 設設G為為n階無環(huán)連通圖，則階無環(huán)連通圖，則 d(G)1dim(G)n。證明證明 由矩陣理論知，鄰接代數的維數等于鄰接矩陣的最小由矩陣理論知，鄰接代數的維數等于鄰接矩陣的最小多項式

50、的次數。多項式的次數。111( )0,nnnnfAAa AaAa I所以最小多項式的次數不超過所以最小多項式的次數不超過n，因此，因此dim(G)n。下面證明下面證明I, A, A2, Ad(G) 線性無關。線性無關。若不然，則存在不全為零的數若不然，則存在不全為零的數a0, a1, ad(G)使得使得2()012()0d Gd Ga Ia Aa AaA。設設al- -10，但當，但當l k d(G) 時，有時，有ak =0，從而，從而2101210lla Ia Aa AaA。由哈密爾頓由哈密爾頓凱萊定理知凱萊定理知顯然，顯然，d(G) n。于是，于是，d(v1, vk ) = k- -1，(

51、k=1, 2, d(G)+1)。注意到：注意到：Ak 的元素的元素a1 l(k)在在 k 0。第第1行第行第 l 列的元素為列的元素為al- -1a1 l ( l- -1 )0。210121lla Ia Aa AaA所以矩陣所以矩陣因此因此2101210lla Ia Aa AaA，產生矛盾！產生矛盾！假定假定v1v2vd(G)+1 是是G中一條最短的中一條最短的 (v1, vd(G)+1)路。路。定理定理 設設G 為為n階連通無環(huán)圖，則階連通無環(huán)圖，則A(G)的不同特征值的個數的不同特征值的個數 s 滿足不等式滿足不等式證明證明 s n 顯然成立。顯然成立。dim()()1sGd G 。由矩陣

52、理論知：非負對稱矩陣的不同特征值的個數等于其最由矩陣理論知：非負對稱矩陣的不同特征值的個數等于其最小多項式的次數，而最小多項式的次數等于小多項式的次數，而最小多項式的次數等于G的鄰接代數的的鄰接代數的維數，所以：維數，所以：()1d Gsn 。注：注：具有具有n個點的路的直徑顯然為個點的路的直徑顯然為n- -1，因此，因此n點路的鄰接代點路的鄰接代數的維數為數的維數為n。注：注：n點路的不同特征值的個數為點路的不同特征值的個數為n。完全圖。完全圖Kn的直徑顯然為的直徑顯然為1，不同特征值的個數恰好為，不同特征值的個數恰好為2。五、圖空間五、圖空間具有具有m條邊的簡單圖的生成子圖的個數顯然為條邊

53、的簡單圖的生成子圖的個數顯然為2m。設設G1, G2, GN（N=2m）表示簡單圖）表示簡單圖G的全部生成子圖。的全部生成子圖。定理定理 集合集合M=G1, G2, GN在對稱差運算在對稱差運算與數乘運算與數乘運算0 Gi= ， 1 Gi= Gi下，構成數域下，構成數域F=0, 1上的一個上的一個m維向量空間。維向量空間。注：注：圖空間是網絡圖論中的一個基本概念。學習網絡圖論的圖空間是網絡圖論中的一個基本概念。學習網絡圖論的主要基礎是電工學與矩陣理論知識。研究通信網絡，如果涉主要基礎是電工學與矩陣理論知識。研究通信網絡，如果涉及圖論方法，建議參看及圖論方法，建議參看陳樹柏，陳樹柏，網絡圖論及其

54、應用網絡圖論及其應用，科學出版社，科學出版社，1982年。年。1.6 極圖極圖 P. Erdos是該研究領域的杰出人物，也是數學界的傳奇是該研究領域的杰出人物，也是數學界的傳奇人物，國際圖論大師，獲過人物，國際圖論大師，獲過Wolf數學獎。他是數學獎。他是20世紀最偉大世紀最偉大的數學家之一，也是人類歷史上發(fā)表數學論文最多的數學家的數學家之一，也是人類歷史上發(fā)表數學論文最多的數學家(1525篇篇)，第二名是歐拉，第二名是歐拉(850余篇余篇)，第三名是柯西，第三名是柯西(789篇篇)。他于他于1996年年9月月20日因心臟病去世，享年日因心臟病去世，享年83歲，他的逝世當歲，他的逝世當時驚動了

55、整個數學界。時驚動了整個數學界。 極圖屬于極圖屬于極值圖論極值圖論的范疇，主要研究滿足某個條件下的范疇，主要研究滿足某個條件下的最大圖或最小圖問題。的最大圖或最小圖問題。 20世紀世紀70年代末，極值圖論已經形成了相對完整的理論年代末，極值圖論已經形成了相對完整的理論體系，但還有很多引人入勝的公開性問題沒有解決，所以，體系，但還有很多引人入勝的公開性問題沒有解決，所以，直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困難的數學研究方向之一。難的數學研究方向之一。一、一、l 部圖的概念與特征部圖的概念與特征定義定義 若簡單圖若簡單圖G的點集的

56、點集V有一個劃分：有一個劃分：1, , liijiVVVVij 且所有的且所有的Vi 非空，非空，Vi 內的點均不鄰接，稱內的點均不鄰接，稱G是一個是一個 l 部圖部圖。4部圖部圖例例注：注：(1) 如果如果l=2，則，則G 就是偶圖就是偶圖;(2) 任何一個任何一個n階圖必是一個階圖必是一個n部圖部圖;(3) 若若l1l2n，任意的，任意的l1部圖也是部圖也是 l2部圖。部圖。定義定義 如果在一個如果在一個l 部圖部圖G中中, |Vi|=ni, 任何兩點任何兩點uVi , v Vj , ij , i, j =1, 2, l 均鄰接，則稱均鄰接，則稱G為為完全完全l 部圖部圖。記作。記作12,

57、lnnnGK。例例注；注；完全完全l 部圖也可表示為部圖也可表示為 。llnnnnnnKKKK2121,ljijinn1邊數：邊數：liin1點數：點數： v1 v2 v3 v4 v6v5K1,2,3定義定義 如果在一個如果在一個n個點的完全個點的完全l 部圖部圖G中，中，n=kl + r (0r l) |V1| = |V2| = = |Vr| = k + 1, |Vr+1| = |Vr+2 | = = |Vl | = k則稱則稱G 為為n 階階完全完全l 幾乎等部圖幾乎等部圖，記為，記為Tl, n。|V1| = |V2| = = |Vl | 的完全的完全l 幾乎等部圖稱為幾乎等部圖稱為完全完

58、全l 等部圖等部圖。v1 v2 v3v4 v5 v6考察考察1. 這是一個連通的這是一個連通的3部圖部圖, 點集點集V 的劃分的劃分為為V1= v4，V2 = v3, v5，V3 =v1, v2, v6 ;2. V 的劃分也可為的劃分也可為V1= v1, v5，V2 = v2, v3，V3 = v4, v6 ; 3. 這也是一個這也是一個2部圖部圖, 點集的劃分為點集的劃分為V1= v4, v2, v6 ，V2 = v1, v3, v5 且劃分唯一且劃分唯一 。定理定理 連通偶圖的連通偶圖的2部劃分是唯一的。部劃分是唯一的。證明證明 設連通偶圖設連通偶圖G的的2部劃分為部劃分為V1V2 =V。

59、 取取vV1，由于，由于G 連通，對任何連通，對任何uV1V2， G中有聯(lián)結中有聯(lián)結u 和和v的路，故的路，故d (v, u)有定義。有定義。 因為任何一條以因為任何一條以v為起點的路交替地經過為起點的路交替地經過V1和和V2 的點，可知的點，可知一個點一個點uV2 當且僅當當且僅當d (v, u)是奇數。是奇數。該準則唯一地決定了該準則唯一地決定了G 的的2部劃分。部劃分。定理定理 n 階完全偶圖階完全偶圖Kn1, n2的邊數的邊數m=n1n2，且，且2/4mn。證明證明 m=n1n2顯然。下面證明第二結論：顯然。下面證明第二結論：1222222,222()()()()424n nn nnn

60、nnm Km Knnnn。定理定理 n階階l 部圖部圖G 有最多邊數的充要條件是有最多邊數的充要條件是 G Tl, n。證明證明 首先首先12,()()lnnnm Gm K。其次，考慮其次，考慮121(,), s.t. llijiijif n nnn nnn，則則 f 取最大值的充分必要條件：對任何的取最大值的充分必要條件：對任何的1 i j l，有，有| |ni- -nj | |1。此時此時G 的對應的頂點劃分形成的的對應的頂點劃分形成的 l 部圖正好為部圖正好為Tl, n。從而定理得證。從而定理得證。二、二、 Turn定理定理定義定義 設設G 和和H是兩個是兩個n階圖，稱階圖，稱G度弱于度