1.1 圖論模型的基本理論

對于前面的兩個例子，我們可以這樣來理解，所謂的圖就是由平面上的一些點以及這些點之間的連線構成的結構.這里我們對點的位置，連線的曲折程度、長短不做區分，重點在于哪些點對是相連的，由幾條線相連.圖中的點在圖論中稱為頂點，兩點之間的連線·2 ·稱為邊.和某一點有邊連接的其他點都稱為它的鄰點.

在過河問題的解決方案中，從一點出發，通過一些邊經過不同的點到達另一點的路徑我們稱之為路，所含邊的數目稱為路的長度.一般來說，圖中連接兩點的路不止一條，我們把這些路中所含邊數最少的路所含的邊數稱為這兩點之間的距離.

實際問題中所建立的圖論模型往往比上述問題復雜，因此需要借助計算機并通過好的圖論算法來解決.我們將在本章對一些基本算法逐一介紹，然后在以后的章節里通過模型加以應用.而運用計算機解決圖上的問題，首先我們要讓計算機學會讀取圖的信息.為了做到這一點，我們引進了關聯矩陣和鄰接矩陣.

? 關聯矩陣：當圖G中頂點集和邊集分別為V={v1,v2,…,vn}和E={e1,e2,…,em}時，我們可以寫出其對應的關聯矩陣M（G）=（mij），其中，如果vi是邊ej的一個端點則mij為1，否則為0.

? 鄰接矩陣：當圖G的頂點集為V={v1,v2,…,vn}時，我們可以定義它的鄰接矩陣A（G）=（aij），其中aij為連接頂點vi與vi的邊的數目.

例如，如圖1.4所示，其關聯矩陣和鄰接矩陣分別為

很顯然，圖的鄰接矩陣是對稱的，因此為了節約計算機儲存空間，我們往往只需要讀取對角線及以上部分.

在實際問題中，我們遇到的絕大多數圖中兩點之間至多只有一條邊連接，且沒有自己到自己的邊，這樣的圖稱為簡單圖.如果根據實際問題需要，對圖中的邊賦予一定的權重，我們稱這樣的圖為賦權圖，記邊（vi,vj）的權為w（vi,vj）.對于賦權圖，兩點間的距離的定義和一般圖就不一樣了，它是指連接兩點之間的所有路中權重最小的路的權重.有時我們需要對圖的每一條邊都規定方向，加了定向的圖我們稱為有向圖.當然，為了突出有向圖的方向性，它的鄰接和關聯矩陣都和無向圖有所區別，我們將在后面的章節中介紹.

最后，我們介紹幾類后面章節中將要涉及的圖類，如表1.1所示.

通常我們可以通過去邊和去點的方法得到包含在一個大圖中的小圖，我們稱之為子圖，注意去點時也去掉該點相關聯的邊.包含所有頂點的子圖叫作支撐子圖，特別地，如果一個支撐子圖是樹時，我們稱它為圖的支撐樹[見圖1.5（b）].由兩兩無公共端點的邊所組成的子圖稱為圖的匹配，如果該匹配涵蓋了圖的所有頂點，則稱其為圖的完美匹配.圖1.6所示就是一個二部圖和它的一個完美匹配.

1.1.1 圖的獨立集

圖的一個頂點子集如果滿足其中任何兩個頂點之間都沒有邊相連，那么我們稱其為一個獨立集.如果把圖看成集合上的二元關系，獨立集中的頂點相互沒有關系，所以在信息科學研究中常稱其為穩定集.所含頂點個數最多的獨立集稱為最大獨立集，而這一最大值稱為圖的獨立數.如何找點數多的獨立集以及確定圖的獨立數是圖論研究中一個極其重要的問題.我們可以通過取點然后刪去它的鄰點，再取點再刪鄰點的這種貪婪算法得到獨立集，但并不能保證所得的獨立集所含點數足夠多.如果一個獨立集不包含于任何其他獨立集，我們稱其為極大獨立集.如何將一個圖的頂點集劃分成盡可能少的獨立集的并即為圖的著色問題.

圖的覆蓋是與圖的獨立集緊密相關的一個概念.圖的一個頂點子集如果滿足圖中任意一條邊都與其中某一點關聯，則稱該子集為圖的一個覆蓋.所含點數最小的覆蓋稱為最小覆蓋.如果一個點覆蓋不包含其他覆蓋，我們稱其為圖的極小覆蓋.如果以頂點集為全集，每個獨立集的補集為圖的一個覆蓋，而任何一個覆蓋的補集必為一個獨立集.所以極大獨立集與極小覆蓋也為互補關系，因此尋找極大獨立集和尋找極小覆蓋為兩個等價的問題.

如圖1.7所示，{5,7,8}是一個極大獨立集，{1,4,7,8}是一個最大獨立集，{1,2,3,4,6}是一個極小覆蓋，{2,3,5,6}是一個最小覆蓋.

1.1.2 競賽圖

競賽圖是一種特殊的有向圖，它的任何一對頂點之間都有一條唯一的有向邊相連.換句話說，競賽圖實際上是由對完全圖的每條邊都賦上一個方向得到.之所以稱之為競賽圖，是因為我們可以用它來記錄一場小組內循環賽的比賽結果.因為對每一條邊的方向只有兩個選擇，所以，我們只能記錄必須分出勝負的比賽，不允許出現打平的情況，例如籃球比賽.我們可以用頂點來表示運動員或運動隊，用有向邊來記錄兩隊的比賽結果.具體地，如果甲贏了乙，在甲和乙之間用一條由甲指向乙的邊來連接.這樣我們得到了一張競賽圖記錄了所有的比賽.競賽圖當前主要應用于包括投票理論和社會選擇理論在內的研究.

下面我們介紹兩個競賽圖的基本性質.

性質1任何競賽圖都含有一個有向的哈密爾頓路.

我們定義一個無向圖的哈密爾頓路，即從圖某一點出發到達另一頂點且經過圖中所有其他頂點恰好一次的路徑.對于有向圖，我們有類似的定義，所謂有向的哈密爾頓路是從一點出發到達另一頂點并經過所有頂點恰好一次的有向路徑，這里有向路徑是指路徑中的邊的方向都一致.

性質2任何競賽圖都有一個唯一的雙連通分支的線性排序.

如果圖中任意兩個頂點之間都有兩條方向相反的有向路連接，則稱其是雙連通或強連通的.對于不是雙連通的圖，都可以分解成若干個極大的雙連通分支.上述性質指出對于競賽圖，存在極大的雙連通分支的唯一的一個線性排列，即D1,D2,…,Dk，其中對于任何i＜j,Di和Dj之間的有向邊的方向均為從Di的頂點指向Dj的點.

如圖1.8所示是一個競賽圖，它不是雙連通的，D→A→B→C→E為一條有向的哈密爾頓路，該圖有3個雙連通分支且唯一線性排序為D1={D},D2={A,B,C},D3={E}.

1.1.3 Dijkstra算法

Dijkstra算法（迪杰斯特拉算法，一般用其英文）是一個用來計算給定賦權圖中一點到其他各點之間距離的算法，也稱為最短路徑算法.

輸入：n個頂點的賦權圖G，頂點u0.

（1）置l（u0）=0，對v≠u0,l（v）=∞,S0={u0}且i=0.

（2）對每個v∈Si，用min{l（v）,l（ui）+w（ui,v）}代替l（v）.計算，并且把達到這個最小值的一個頂點記為ui+1，置Si+1=Si∪{ui+1}.

（3）若i=n-1，則停止.若i＜n-1，則i+1代替i，并轉入（2）.

輸出：u0和圖中任意點之間的距離.

注意：Dijkstra算法是一個多項式時間算法，事實上它能執行不超過n2次簡單運算（n為圖中頂點的個數），算出賦權圖上任意兩點之間的距離.

下面我們運用Dijkstra算法來計算圖1.9中點u0到其他各點的距離.

1.1.4 Kruskal算法

要求一張賦權圖的最小支撐樹，我們可以采用如下的Kruskal算法（克魯斯卡爾算法，一般用其英文），也稱為最小支撐樹算法.

輸入：賦權圖G（V,E,w），其中w為各條邊權重的賦值函數.

（1）選擇邊e1，使得w（e1）盡可能小.

（2）若已經選定邊e1,e2,…,ei，則從E＼{e1,e2,…,ei}中選取ei+1，使得

① 由e1,e2,…,ei，構成的子圖G[{e1,e2,…,ei+1}]為無圈圖；

② w（ei+1）是滿足（1）的盡可能小的權.

（3）當第（2）步不能繼續執行時則停止.

輸出：最小支撐樹T（G）.

下面我們運用Kruskal算法，求出圖1.10中的最小支撐樹（最后一張圖加粗邊為支撐樹）.·6 ·

1.1.5 匹配算法

本節中我們將介紹與匹配相關的兩個經典算法——匈牙利算法和Kuhn-Munkres算法（也稱KM算法）。

為了便于理解算法，我們先介紹兩個相關的概念.假設M是圖G的一個匹配，v是G的一個頂點，如果v是M中某條邊的端點，則稱M飽和v，否者稱v是M的非飽和點.

一條連接兩個非飽和點x和y的由M外的邊和M的邊交錯組成的路稱為M的可擴（x,y）路.設S為G中一些頂點組成的集合，記N（S）為S中各點鄰點的并集.

圖1.11中的匹配M中就存在可擴路P，經過更新后得到一個邊數更多的匹配M＾.

1.匈牙利算法

匈牙利算法主要用于求已知二部圖的最大匹配，如果二部圖兩部分頂點一樣多，該算法顯然可以確定完美匹配是否存在.

（1）若M飽和X的每個頂點，則停止.否則，設u是X中的M非飽和點.置S={u}及T=?.

（2）若N（S）=T，由于|T|=|S|-1，所以 |N（S）|＜|S|，因而停止，因為根據Hall定理（參考文獻[1]），不存在飽和X的每個頂點的匹配.否則，設y∈N（S）＼ T.

（3）若y是M飽和的.設yz∈M，用S∪{z}代替S,T∪{y}代替T，并轉到第（2）步.否則，設P是M可擴（u,y）路，用代替M，并轉到第（1）步.其中E（P）為P的邊集.符號Δ表示集合的對稱差運算.通常，對于集合A,B，其對稱差AΔB=（A-B）∪（B-A）=（A∪B）-（A∩B）.

2.Kuhn-Munkres算法

Kuhn-Munkres算法是對匈牙利算法的一個改進，可以用來找出賦權完全二部圖的最優匹配.

假設l是頂點集X∪Y上的實函數，且滿足對于所有的x∈X及y∈Y，均有

l（x）+l（y）≥w（x,y），

其中w（x,y）為邊xy的權重，則稱l為G的一個可行頂點標號.這樣的標號一定是存在的，例如，我們可以對所有Y中的點都標零，而對于X中的點x標上與它關聯的所有邊的權重的最大值即可.記Gl為在標號l下，那些使得上式取等號的邊組成的G的子圖.Gl中與頂點集S關聯的點的集合記為.

從任一可行頂點標號l開始，然后決定Gl，并且在Gl中選取任意一匹配M.

（1）若X是飽和的，則M是完美匹配，并且是最優的，算法終止；否則，令u是一個M非飽和點，置S={u},T=?.

（2）若，則轉入（3）；否則.計算

且由

給出可行頂點標號 以代替l，以代替Gl.

（3）在中選擇一個頂點y.考察y是否M飽和.若y是M飽和的，并且yz∈M，則用S∪{z}代替S，用T∪{z}代替T，再轉到（2）；否則，設P是Gl中M可擴（u,y）路，用代替M，并轉到（1）.

圖1.12所示為一個賦權完全二部圖G=（G,w），以及在標號l和下的子圖以及最優匹配.