演算法基礎08圖論下集

『壹』 簡介圖論演算法

圖論101

圖論是數學的一個非常廣泛的分支，非常適用於現實世界中的問題。 最初，圖論是"發明"來解決現實問題的，此後，它像所有其他數學分支一樣，被抽象數學家所劫持。

在本教程和後續教程中，我們將介紹一些圖論演算法及其在python中的實現。 現在，回到主題。

簡而言之，圖是一組頂點/節點和邊。 如果您對" set"不滿意，請用collection代替。

在上圖中，頂點/節點將是人物。

頂點是圖的基本單位。 它幾乎可以代表任何實體，通常以圓圈表示。

在上圖中，連接人的線是邊。

頂點之間的線或連接稱為邊。 它可以表示頂點之間的任何類型的關系。

邊上具有方向的圖稱為有向圖。 它可以用來顯示與前輩（從父母到孩子的箭頭）或祖先（從孩子到父母的箭頭）的關系。

邊上沒有方向的邊的圖稱為無向圖。 它可用於顯示雙向道路。

邊上帶有數字的圖形，代表交易成本，旅途公平，城市之間的距離等。它可以具有任何類型的邊。

沒有循環的無向圖是一棵樹。 在這里，循環意味著只有一種方法可以通過跟隨給定其他節點的邊緣來到達節點。

一棵樹的所有節點都通過一條邊連接到其他某個節點，並且有N個節點的N-1個邊。

表示圖形的方法有很多，最常見的兩種是：

假設圖中有N個節點。 我們可以使用具有N行和N列的矩陣來表示它，其中該矩陣的行和列將代表一個節點，並且其中的條目代表有向邊（有或沒有權重）。

它們形成代錶行的節點到代表列的節點。 通常，0或無窮大用於表示節點之間沒有邊緣。 在Python中，鄰接矩陣可以表示為：

類似地，對於N個節點的圖，我們可以使用鄰接表來表示該圖，其中節點的所有邊都保留在元組列表（節點，權重）中。 在python中，它可以表示為：

我使用嵌套字典（這就是我所說的）和帶集合的字典（如果節點沒有權重的邊）來表示圖。

在下一篇文章中，我將使用不同的方法發布精心設計的圖類的Python代碼，我們將使用該代碼來實現圖演算法。

(本文翻譯自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，參考：https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)

『貳』 圖論基礎-1.查找所有路徑

工作中某塊需求涉及到查找兩點之間全部路徑的需求，嘗試利用圖的演算法來解決這一問題。
目標：找出途中從開始到結束節點中間的所有路徑

圖是網路結構的抽象模型。圖是一組由邊連接的節點（或頂點），任何二元關系都可以用圖來表示。
一個圖G=(V, E)由以下兀素組成：

由一條邊連接在一起的頂點稱為相鄰頂點 比如，A和B是相鄰的
一個頂點的度是其相鄰頂點的數量 比如，A和其他三個頂點相連接，因此，A的度為3
路徑是頂點v1, v2, ...vk的一個連續序列 以上圖為例， 其中包含路徑A B E I 和 A C D G。

用例：

1.鄰接矩陣：（Adjacency Matrix）適用於稠密圖（完全圖）

2.鄰接表（Adjacency Lists）適用於稀疏圖

和樹數據結構類似，我們可以訪問圖的所有節點。有兩種演算法可以對圖進行遍歷：

1.將圖抽象成用例

2生成鄰接矩陣

3獲取所有路徑

參考文檔：
https://juejin.im/post/5de7c053518825125d1497e2
https://juejin.im/post/5a32688b5188254dd9366d6a
不使用遞歸的生成路徑方法： https://juejin.im/entry/5d849fb45188255a8b635058

『叄』 圖論演算法的介紹

圖論演算法在計算機科學中扮演著很重要的角色，它提供了對很多問題都有效的一種簡單而系統的建模方式。很多問題都可以轉化為圖論問題，然後用圖論的基本演算法加以解決。遺傳演算法是解優化問題的有效演算法，而並行遺傳演算法是遺傳演算法研究中的一個重要方向，受到了研究人員的高度重視。

『肆』 圖演算法(一): 圖的概念基本表示

圖並不是現實世界中的一幅畫, 例如

在計算機中, 圖是一種數據結構. 圖是計算機科學的一個概念, 在數學中也有對應的數學分之: 圖論.

計算機中的圖如果表示出來大概長成這樣

可以把上圖想像成一個社交網路, 網路中的每個圓表示一個User, User存在某種關系.

或者看作是一個城市群, 每個圓表示一個城市, 城市之間通過道路聯通.

直觀的從圖片上看 有3個組成部分:

更一般的叫法是:

有了這些概念, 在理解的基礎上就可以對圖做一個稍微正式點的定義了

上圖中的圖叫做簡單圖, 那什麼樣的圖不叫簡單圖呢? 如下所示

在頂點0, 存在一個邊, 這種邊稱之為 自環邊(self-loop)
在頂點0和1之間, 除了之前那張圖片上的一條邊之外, 又多了一條邊, 多出來的這條邊稱之為 平行邊(parallel)

因此, 擁有自環邊或平行邊的圖不是簡單圖.

上面給出的圖的示例屬於最簡單的 無向無權圖 .

因為圖的邊可以附加一些信息(權), 以及邊是可以有方向的, 因此圖有兩個大類:

進一步的組合可以分為:

不同種類的圖有不同的作用, 在開始學習圖演算法的時候, 應先從最簡單的無權無向圖開始.

通過圖片可以很清楚的知道圖的形狀, 那麼如何轉換到計算機中表示呢?
對於這個問題, 有兩種方式:

這兩種方式各有優缺點, 具體選擇哪一種需要看場景

『伍』 圖論割集問題

回答樓主,圖論大多問題的解決,需要用到遍歷演算法,判斷割集我想不會有其它演算法,遍歷的演算法目前是圖論中最基本最重要的演算法,當然對一些特殊的圖可能會有其它方法.遍歷演算法的計算復雜度不是很大的,是多項式演算法,在計算機上可以實現.當然在選取邊和點時應考慮技巧性,這恐怕是個難題,否則會出現組合爆炸,就象貨郎擔問題一樣,比如選擇點可以首先考慮選取度數最大的點,選取邊一定要選不在迴路上的邊.這需要你的智慧.
割集分為點割集和邊割集,對一個圖G=(V,E)來說如果存在一個結點集V的子集,從G中刪除這些結點後,它的連通分圖的個數增多,則稱該子集為點割集,對一個連通圖來說,刪除這些結點後,連通圖變為不連通.點割集一般不是唯一的,含有最小結點個數的點割集稱為最小點割集,類似可定義邊割集和最小邊割集,僅含1個點的點割集稱為割點,僅含1個邊的邊割集稱為割邊,割邊也稱為橋.
求一個連通簡單圖的割集的演算法,我想可用遍歷的演算法,目前常用的是深度優先搜索或者廣度優先搜索演算法來做,這是圖論中最基本的演算法,這種演算法可求出圖的連通分圖的個數,以此來判斷某子集是否是割集.

『陸』 演算法基礎

謹以此文，感謝我在這個學校最喜歡的兩個老師之一——肖my老師。本文基本為老師上課說講授內容加上一部分自己的感悟拼湊而來，寫作文本的目的是為自己的演算法課程留下一點點東西，站在老師肩膀上形成粗糙的框架，方便以後的復習以及深入。文筆有限，其中包含的錯誤還請多多包容，不吝賜教。

to do list：

時間復雜度中遞歸樹法；動規，分治新的感悟；

點覆蓋：一組點的集合，使得圖中所有邊都至少與該集合中一個點相連。

支配集：一組點的集合，使得圖中所有的點要麼屬於該集合，要麼與該集合相連。

最大團：在一個無向圖中找出點數最多的完全圖。

獨立集：一組點的集合，集合中的頂點兩兩不相鄰。（團轉過來）

SAT問題：也稱布爾可滿足性問題。給一組變

其中Ci被稱為句子。

點覆蓋<->獨立集<->最大團

最小割：割是一組邊集。如s-t割就是如果去掉這些邊，將把原圖劃分為兩個點集，其中一個點集包含s，一個點集包含t。（兩個是指不相連，而不是代表不存在邊相連，如反向邊）

decision problem: 是否存在。

search problem:找到一個解。

（這個還能擴展，比如decision problem在多項式時間內解決，所以他是P問題嗎）

漸進符號：

注意以上三種都是緊的，對應的兩個小寫的符號是不緊的，即如下圖所示：

概念：演算法的時間復雜度是一個函數，用於定性描述演算法的運行時間。注意，這個一個代表演算法輸入字元串長度的函數。

[注]輸入字元串長度是一個比較關鍵的理解，比如在背包問題中，其時間復雜度為O(nW)，因為W不定，所以只能是一個偽多項式時間。

比較：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n

大致：常數<對數<冪函數<指數函數<階乘

對於指數是n相關的進行比較，優先比較指數，再比較底數。

記住一個特例：n ^(logn)<n!<n n

計算：

一般來說，計算採用主方法和遞歸樹法，其中遞歸樹技巧性比較強，主方法其實也是遞歸樹推導歸納而來，且主方法能得到一個比較緊的結果。

主方法：

f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )

P：decision problems有一個多項式演算法。

NP（nondeterministic polynomial-time）：decision problems能夠在多項式時間內驗證。

NPC：NP完全問題，首先這個問題是NP的，其次，其他所有問題都可以多項式時間內歸約到它。

NPH：如果所有NP問題都可以多項式時間歸約到某個問題，則稱該問題為NP困難。

因為NP困難問題未必可以在多項式時間內驗證一個解的正確性（即不一定是NP問題），因此即使NP完全問題有多項式時間的解（P=NP），NP困難問題依然可能沒有多項式時間的解。因此NP困難問題「至少與NP完全問題一樣難」。

一些NP問題能在多項式時間內解決，因為 P∈NP

NP難類型問題的證明：

先選好一個已知NP難的問題，然後將已知NP難問題多項式歸約到要證明的問題上。先給出這個歸約，然後再證明這個歸約的正確性。

NPC類型問題的證明：

證明一個問題Y是NPC問題，先說明Y是NP的，然後找到一個NPC問題X，將這個問題X歸約到問題Y上，即證明完成。

常見的NPC問題（重要，規約的時候有用！）：

packing problems: set-packing，獨立集

覆蓋問題：集合覆蓋問題，頂點覆蓋問題

嚴格滿足問題(constraint satisfaction problems)：SAT，3SAT

序列問題：哈密爾頓迴路，旅行商問題

劃分問題：3D-matching, 3著色問題

數字問題：子集合問題（子集元素之和為t），背包問題

其他：分團問題（是否存在一個規模為k的團）

規約的概念與理解

規約：意味著對問題進行轉換，例如將一個未知的問題轉換成我們能夠解決的問題，轉換的過程可能涉及到對問題的輸入輸出的轉換。

自歸約：search problem <=p decision problem

歸約：A歸約到B，也就是說，我們對A套一個函數f，在f函數的作用下形成一個新的問題，對這個問題運用B的黑盒解法，能夠解決問題A。

(B <=p A)一般說來，B問題如果可以歸約到A問題，也就是說，一個解決A問題的演算法可以被用做子函數（子程序）來解決B問題，也就是說，求解B問題不會比求解A問題更困難。因此，如果B問題是困難的，那麼A問題也就是困難的，因為不存在求解A問題的高效演算法。(最後一句不懂)

我簡單說一下我理解的規約，以X規約到Y為准，大概分成兩個方面：

註：在 三 的一些實例中細品。

概念：在對問題求解時，總是做出在當前看來是最好的選擇。

貪心的證明：先假設貪心演算法得到的解不是最優解，假設S1是貪心演算法得到的解，而S2是所有最優解中和S1具有最多相同元素的解，然後比較S1和S2，觀察S1和S2中第一個（最前面一個）不一樣的元素，然後在貪心解S2中將不一樣的元素換成S1中的那個元素得到另一個最優解S3，這樣S3和S1比S2和S1有更多相同元素，和假設S2是與S1有最多相同元素的最優解矛盾，這樣來推導S1是最優解。

我的理解：假設這個不是最優的，但是一定存在一個最優的解在某一個位置之前和我當前解結構是一樣的，那麼在這個位置，選最優解也可以選當前解，不影響最終答案。

[注]概念很簡單，但是實際操作的時候，貪心的角度很重要，同樣的貪心，方向對了，演算法就是對的。

例子：

給你一系列活動，每個活動有一個起始時間和一個結束時間，要求在活動不沖突的情況下找到一種有最多活動的安排。

對於這個問題，我們有一下幾種貪心的角度：

①將任務按照 開始時間 升序排列。

②將任務按照 結束時間 升序排列。

③將任務按照 任務時長 升序排列。

④對於每一個任務，都記錄與其他任務沖突的數量，按照 沖突數量 的升序排列。

其中1，3，4都是不可以的。

任務結束時間的貪心證明（反證法）：

假設貪心不是最最優的，那我們在最優解中找一個與當前解有最相似的解。

由圖可以知道，貪心貪的就是最早結束，所以如果不是最優，那麼最優的結束時間一定晚於貪心的結束時間。

由上圖就可以證明。

最大流通常與最小割相聯系。

f 為任意一個流，cap為容量，對於任意的s-t割出來的點集（A，B），v( f ) <= cap(A, B)。

當流增加到與割的容量相等時候，就不可能再有增長空間了，稱為最大流。

對於割的容量來說，不同的割法會有不同流量，有些割法永遠不會有流達到，比如部分A = {s}, B = {V - s}，這種把源點割出來的割法。

綜上，通過這種感性的認識，如果能找到一個最小的割，那麼這個割就一定是最大能跑到的流（如果流能更高的話在這個割上就會超過容量，反證。）

上圖為一條增廣路，一條增廣路即為一條s-t的路徑，在路徑上仍有流可以跑，其曾廣的流就是該條路徑上最小的剩餘容量。（相當於每找一條增廣路，就至少有一條邊達到滿流。）

直到在圖中找不到增廣路，此時已經達到了最大流。

找ST集合：把滿流的邊去掉，從S出發走到能到的點，遍歷的點就是S集合；剩下的點就屬於T集合。注意，如果找到了在找S集合的時候找到了T點，說明還可以繼續找增廣路。

[補]有一個很有趣的延伸，如多源點多終點問題。問：如果我有兩個源點s1，s2，兩個終點t1，t2，我想求一組流，使得s1-t1，s2-t2的流達到最大，是否可以加一個源點S，S與s1，s2相連，邊流無限大；加一個終點T，T與t1，t2相連，邊流無限大，然後這組ST的最大流即可。——答案是No，無法保證是s1-t1，s2-t2，有可能交錯。

例子講的感覺不是特別好，對理解感覺起不到很大作用，希望以後有新的想法後進行補充。

規約是一個重要的概念和思想。

一個圖的 最大獨立集 與 最小點覆蓋 是不相交的兩個點集，它們的並就是整個點集。

個人理解：獨立集和點覆蓋都是從點的角度進行劃分的，如果我們從邊的角度來看，①一個最小的點覆蓋即為我集合中的每一個點都盡可能與更多的邊相連，②同時，一條邊的兩個端點中，只能有一個端點在最小點覆蓋中[下注]

[注]我們假設有一條邊兩個端點（u，v）都在點覆蓋之中，首先顯然u，v都不是端點，因為假設u是端點的話只需要選擇v即可；

給一個集合S和一堆S的子集S1，S2，...，Sm，問是否存在存在k個子集，使它們的並集為S。

構造：

集合為點，集合中的元素為邊，有相同元素的邊相連。（注意如果某一元素只在一個子集中出現，應該怎麼處理呢！）

規約：在構造的圖中找最小的點覆蓋，選中的點能覆蓋所有的邊即為對應集合的並集能包含所有的元素。所以就完成了集合覆蓋到點覆蓋的規約。

構造：每個句子構造一個三角形，把對應變數但是相反取值的點相連。

規約：3SAT的有一個特點就是，每一個句子中至少有一個為真即可，每個句子都必須是真。將相同變數相反取值相連的目的就是，在最大獨立集中，比如選擇x為真，則剩下所有句子中x-ba一定不會被選中，同時由獨立集和構造出來三角形的性質可以知道，每一個句子，有且僅有一個會被選中（為真）。如上圖，x1-ba為真，x2-ba和x3任選一個為真即可滿足。

search problem <=p decision version

比如：如果能在多項式時間內找到一個哈密爾頓圈，那麼就能在多項式時間內找到一個哈密爾頓圈（刪邊）

在此再談P和NP：

我們知道有些問題是可以從搜索問題規約到判斷問題的，也就是所該問題如果能在多項式內判斷，那麼久能在多項式中搜索到，那麼我們只需要說，這個判斷問題能在多項式時間內求解，就叫做P問題，也就是上圖紅字的意思；那NP問題呢，必須要給出一個解的實例，判斷的是這個實例是否滿足求解問題，這個才是上圖中的紅字。比如，我如果能在多項式時間內判斷哈密爾頓圈是否（Yes/No）存在，那這個就是ploy-time algorithm，如果我給出了一系列點，能過多項式時間內判斷這些點能否構成哈密爾頓圈，那這個就是poly-time certifier。

構造：把一個點拆分成三個點。

構造：（下面兩個圖要連在一起看）

從行的角度看，一行代表一個變數；從列的角度來看，每三列代表一個句子。兩邊中一邊是兩個點，一邊是一個點，所以有k個句子的話，每一行有3k+3個節點。從哈密爾頓圈的答案轉到3SAT的答案看這個圈在每一行是從左到右還是從右到左。

子集和問題：給一個集合S，問是否能在集合中選取元素，使得總和為W。

構造：如下圖，按照前六行和前三列進行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，變數v列和 變數為v（包括變數及取反）的行對應的格子為0，其餘為0；第三部分全為0；第四部分按照12依次寫下來。第二部分，如果Ci句子中有變數v，則記為1，因為一個句子只有三個變數，可以簡單通過第二部分每一列和為3進行判定。此時集合已經構造出來，W為111444，與上面的規約相似，可以通過3SAT的簡單性質進行感性的認知。

近似的想法很簡單，要解決一個問題，我們希望能夠做到①求解結果是最優的 ②在多項式時間內解決 ③對於任意的實例都能夠通過該演算法解決。現在對於部分問題，無法完全滿足以上要求，所以就犧牲了①，但是我們希望結果不是盲目的，所以就引入了近似的概念。

近似演算法。比如2-近似，認為W為近似解，W 為最優解，在求最小值的情況下W<=2W ；在求最大值的情況下，W>=1/2W*

給m個機器和n個任務，每個任務有一個ti的執行時間，我們認為完成最後一個任務所需的時間為負載時間，希望能夠讓這個負載時間最短。

第一種：將任務依次放在機器上，當某個機器空閑時立即放入新任務。此時是2近似的。

證明：

引理1.最短時間安排是大於等於任務中時間最長的任務，L* >= max tj

我們在考慮放入最後一個任務前，根據我們放置的規則，該機器是耗時最短，也就是說，該機器此時的用時是低於除掉最後一個任務後的平均時長，更低於所有任務的平均時長（引理2）；再根據引理1，最後一個任務應該是小於最優解的。

補充：

在這里，我還想討論一下這個近似演算法的中等於符號，先上結論：等號不一定能夠找到一個實例，但是可以構造出一種結構，通過取極限求得，我們認為這樣 也算是緊的。

構造實例：有m個機器，其中m(m-1)個任務的用時為1，1個任務的用時為m。肯定有一種任務集合，可以按照以下方式進行安排，此時的貪心解為19。

此時最佳的解為10，如下圖：

通過推廣可以知道此時的比為（2m-1）/m，當m取極限，能夠達到2倍。

第二種：將任務從大到小排序，然後依次放在機器上，當某個機器空閑時立即放入新任務。此時是2近似的。

引理3：如果有大於m個任務，那麼L*>=2t(m-1)。證明：t(m+1)是目前最短的任務，且目前所有機器上都有任務了，所以該任務加入時最優的情況不過是加入設備的原有任務剛好和t(m+1)相等，即等號。

（2近似）在n個點中，選取k個中心點，使得這些中心點能夠以半徑R的圓包含所有的點，讓其中最大的半徑最小，如下圖所示：

基礎：距離需要滿足的三個定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)

r(C)為C集合中所有點的最大覆蓋半徑。（需要求min r(C)）

演算法：在點集中任選一個作為中心點，然後重復以下步驟k-1次:選取距離已選點集中最遠的點，加入點集。

證明：先假設r(C )< 1/2 * r(C)以選好的點畫半徑為1/2 * r(C)的圓，顯然可知[注]，這個圓里有且僅有一個r(C )中的點。那麼根據在下圖中，根據三角不等式可以得出：

[注]在每個點上r(c )一定會包含到c點，而r(C )<1/2 * r(C)，相當於大圓套小圓，所以c*一定在c的圓中。

（2近似）問題還是很好理解的，在點上加權值，要找一個點覆蓋，使得權值最小。如下圖左邊就是一個帶權的最小點覆蓋。

演算法： 任選一條邊(i, j)加上代價，這個代價從零開始，且這個代價的最大值低於i和j節點的權值。顯然，這個邊權值的最大值取決於兩個端點權值的最小值，我們認為當邊權值與點權值相等時，對應的那個點是緊的。把所有緊的點找出來即為點覆蓋。

流程：

證明：

引理：邊權之和小於等於點覆蓋的點權之和。這主要是由於涉及到一條邊上兩個點都被選（緊的）的情況，感性認知可以看上圖，縮放證明如下：

w(S)是等於所選的節點的權值之和的，等於所選節點節點所對應的邊權之和，可以把它放大到所有節點對應邊權之和，這樣因為一條邊(u, v)在u上算過一次後還要在v上算一次，所以等於邊權和的兩倍。再由上面引理可得。

主要為了線性規劃和整數規劃。

（2近似）沒啥好說的，只需要把方程構造出來就行了。

由於求解出來結果不一定是整數，所以我們認為某一點的值大於1/2，就選入點集。

證明：

因為xi+xj >=1,且都是正數，那必至少一個點是大於1/2的（反證，兩個都小於1/2則和小於1）。

給你n個物品和一個背包，每個物品有一個價值v和一個大小w，背包的容量是W，要求讓背包裝下盡可能大價值。

背包的時間復雜度：O(nW)

注意其中n表示物品的個數，無論是1個還是999個，他都是多項式的，這個很好理解。但是W就不一樣了，這是一個數字。我理解的是這個數字會很奇特，比如1.00001，比如99999，這些有可能看起來不大但是實際在處理的時候很難處理的數字，統一的來說，如果我們把這些數字放在電腦上，都會以二進制的方式存儲起來，有些數字用十進製表示很小，但是放在二進制上面就會很大，由W導致不能在多項式時間內解決（找不到一個范圍/上界來框它）。

演算法： 為了處理這個問題，我們改動了dp的狀態轉移方程，要讓這個轉移方程和W無關[注]。

此時還不是多項式的，然後我們再對value進行約。[注]

[注]這兩步中，我們把w改成v，並對v進行近似處理。OPT的含義變成了，在面對是否選擇第i個物品時，要想讓價值達到當前值，最少的weight。理由是更改後的誤差是可以忍受的：對v進行近似，結果只會出現最大價值的上下誤差，如果對w進行近似，則有可能出現該物品不能放入背包中，導致整個物品直接放棄的情況。

『柒』 運籌學中的圖論問題

很多實際的生產問題都能被抽象成一張大的圖。具體一點的例子，比如需要在若干個城市之間鋪設鐵路或者架設電網，那麼城市就是圖裡面的點，鐵路電網就是圖裡面的邊。抽象一點的例子，比如完成一個項目的過程中所有可能出現的狀態都可以視為一個點，而狀態到狀態之間的轉換就是邊。上一篇文章中我們說過運籌學是處理實際生產生活中遇到的問題的。一旦實際問題被抽象成了一個圖的模型（注意與機器學習裡面的圖模型區分開來），很多圖論裡面的演算法就可以用來解決實際問題，所以圖論是運籌學當中的一個很大的分支。今天我們就介紹一下幾個圖論的基本演算法及其在生產生活中的應用。

一最小生成樹

比如現在要在若干個村子之間架設電網，保證每個城市都通上電（先不考慮電網輸電能力大小）。雖然理論上講，任何兩個村子之間都可以架設電線，不過那樣的話成本很到，不劃算，我們需要在所有可能的連線裡面找到一組總長最短的邊，保證這些邊把每個村子都連上了。在圖論中，這是一個典型的最小生成樹問題。有兩種解決最小生成樹的方法，第一種辦法是把所有的邊按照從小到大的順序添加到圖裡面，如果產生迴路就舍棄它，直到覆蓋了所有的點。另一種方法是把圖上的邊按照從大到小的順序刪除，直到再刪下去就一定會產生離散的點為止。

二最短路徑

圖論中應用最廣的問題可能就是最短路徑問題了。地圖上很多城市之間都有道路相連，想從一個城市到另一個城市，往往有多種選擇，可是走那條路距離最短呢？如果地圖規模不大，我們可以一眼就看出來。可是隨著地圖規模變大，就很難再一眼看出來了，需要有嚴格的演算法保證找到最短路徑。目前已經有了很多種最短路徑演算法，他們的基本思想也不盡相同。以著名的Dijkstra演算法為例，它每次會選擇距離「所有已經選擇過了的點」中距離最近的下一個點，一步步的迭代下去。這個流程保證了演算法會按照距離出發點由近到遠的順序選擇每一個點。

三最大流-最小割問題

油氣輸送網路又許多不同的邊組成，每一條邊的運輸能力有限。輸送油氣資源的時候，為了最大化運輸量，需要合理安排通過每一條邊的油氣流量。這就是在一個網路尋找最大流的問題（等價於尋找最小割）。解決問題的想法很簡單，找到一組邊，它們把整個網路分成了兩部分，流的源和目的地址分屬於這兩個部分。我們稱這樣一組邊為圖的一個分割。由於所有的油氣流都要通過分割中的邊，所以最大流其實受制於分割的流通能力的。於是最大流應該等於流通能力最小的分割。剩下的問題，就是一步步調整，找到最小分割了。

『捌』 圖論基礎

圖 是由頂點V和邊E的集合組成的二元組，記G=(V,E)

有向圖、無向圖、有權圖、無權圖、連通圖（聯通分量）、二分圖

頂點的 度 （無向圖種與頂點相連的邊的數目）、 入度 （有向圖中以該頂點為終點的邊的數目）、 出度 （有向圖中以該頂點為起點的邊的數目），度等於入度和出度之和，所有邊的入度和=所有邊的出度和=邊數

圖的定義是指將邊作為一個集合，從而允許兩個無向邊具有相同的端點。對於兩個有向邊可以有相同的起點和終點。這種邊稱為 平行邊 或者 多重邊 。另一種邊的特殊類型是頂點和自己連接，也就是說兩個頂點重合，我們稱這樣的邊為 自循環 。除了少數例外，圖沒有平行邊和自循環

圖G中從頂點u到頂點v有一條路徑，我們稱u到達v，並且v是從u 可達 的。在無向圖中，可達性的概念是對稱的。

如果一個圖是 連通 的，則意味著對於任何兩個頂點，它們中間都是有路徑的。

如果對於G的任何兩個頂點u和v，都有u可達v並且v可達u，則有向圖是 強連通 的

圖G的 子圖 是頂點和邊是G的頂點和邊的各自的子集的圖H。G的 生成子圖 是包含圖G的所有頂點的圖。

如果圖G是不連通的，它的最大聯通子圖稱為G的連通分支。

森林 是沒有循環的圖。 樹 是連通的森林，即沒有循環的聯通圖。圖的 生成樹 是樹的生成子圖

特性1 ：如果G是由m條邊和頂點集V的圖，那麼 ，即邊對頂點度數的總貢獻度是邊數目的兩倍

特性2 ：如果G是有m條邊和頂點集V的有向圖，那麼 即邊對它的起點u的出度貢獻了一個單元，對終點v的入度貢獻了一個單元。因此邊對頂點出度的總貢獻和邊的數目相等，入度也是一樣。

特性3 ：給定G為具有n個頂點m條邊的簡單圖。如果G是無向的，那麼 ，如果G是有向的，那麼

特性4： 給定G是有n個頂點和m條邊的無向圖。

邊列表 ：對所有邊採用無序的列表。但是沒有有效的辦法找到特定的邊(u,v)​，或者將所有的邊入射到頂點v

鄰接列表 ：為每個頂點維護一個單獨的列表，包括入射到頂點的那些邊。可以通過取較小集合的並集來確定完整的邊集合，也可以更高效地找到所有入射到給出頂點的邊

鄰接圖 ：和鄰接列表非常相似，但是所有入射到頂點的邊的次級容器被組織成一個圖，而不是一個列表，用相鄰的頂點作為鍵。這允許在O(1)的時間內訪問特定的邊(u,v)

鄰接矩陣 ：對於有n個頂點的圖維持一個n*n矩陣來提供最壞的情況下訪問特定邊(u,v)的時間O(1)。每一項專用於為頂點u和v的特定對存儲一個參考邊(u,v)；如果沒有這樣的邊存在，該表項即為空

可能是最簡單的，但不是最有效的。所有頂點存儲在一個無序的列表V中，並且所有的邊對象存儲在一個無序的列表E中

將圖形的邊存儲在較小的位置來對其進行分組，從而和每個單獨的頂點相關聯的次級容器結合起來。具體的，對每個頂點v維持一個集合l(v)，該集合被稱為v的 入射 列表，其中全部都是入射到v的邊。（在有向圖的情況下，輸出邊和輸入邊分別存儲在兩個單獨的集合lout(v)和lin(v)中。

同時要求鄰接列表的基本結構在某種程度上保持頂點集合V，因此可以在O(1)時間內為給出的頂點v找出次級結構l(v)

命題 ：對於i=1，...，n，當且僅當有向圖 從 到 有一條有向路徑時，有向圖 有邊 ，其中中間的頂點在集合 中，特別的， 和 相等， 是 的傳遞閉包

該命題為計算G的依賴於一系列界限的每個 傳遞閉包提出了一個簡單演算法。這個演算法被稱為 Floyd_Warshall演算法

沒有有向循環的有向圖被叫作 有向非循環圖 ，或者簡稱 DAG

『玖』 圖論演算法及其MATLAB實現的圖書目錄

第1章 圖論的基礎知識1
1.1圖論的起源1
1.2著名的圖論學者——歐拉1
1.3圖2
1.4特殊圖類3
1.5有向圖4
1.6圖的矩陣表示5
1.6.1鄰接矩陣5
1.6.2關聯矩陣5
1.7圖論的基本性質和定理6
1.8計算有向圖的可達矩陣的演算法及其MATLAB實現6
1.9關聯矩陣和鄰接矩陣的相互轉換演算法及其MATLAB實現7
習題一11
第2章 最短路12
2.1路12
2.2最短路問題13
2.3求連通圖最短距離矩陣的演算法及其MATLAB實現14
2.4求兩點間最短路的Dijkstra演算法及其MATLAB實現15
2.4.1 Dijkstra演算法16
2.4.2 Dijkstra演算法的MATLAB實現16
2.5求兩點間最短路的改進的Dijkstra演算法及其MATLAB實現18
2.5.1 Dijkstra矩陣演算法Ⅰ18
2.5.2 Dijkstra矩陣演算法Ⅱ18
2.6 求兩點間最短路的WarshallFloyd演算法及其MATLAB實現21
2.6.1 Floyd演算法的基本思想22
2.6.2 Floyd演算法的基本步驟22
2.6.3 WarshallFloyd演算法的MATLAB實現22
2.7求任意兩點間最短路的演算法及其MATLAB實現25
2.8求從一固定點到其他所有點最短路的演算法及其MATLAB實現27
2.9求必須通過指定兩個點的最短路的演算法及其MATLAB實現29
2.10求圖的兩頂點間最短路與次短路的演算法及其MATLAB實現32
2.11求最大可靠路的演算法及其MATLAB實現34
2.12求最大期望容量路的演算法及其MATLAB實現36
習題二38
第3章 連通圖40
3.1判斷圖的連通性演算法及其MATLAB實現40
3.2連通圖的中心和加權中心的演算法及其MATLAB實現42
3.3連通無向圖一般中心的演算法及其MATLAB實現44
習題三46
第4章 樹48
4.1樹及其性質48
4.2割點、割邊、割集50
4.3二元樹與Huffman樹51
4.3.1有序二元樹51
4.3.2 Huffman樹51
4.4求Huffman樹及其MATLAB實現52
4.5廣度優先搜索演算法及其MATLAB實現55
4.6深度優先搜索演算法及其MATLAB實現57
4.7求割點演算法及其MATLAB實現61
4.8生成樹及其個數65
4.9求無向圖的生成樹演算法及其MATLAB實現67
4.10求有向圖的生成樹演算法及其MATLAB實現69
4.11求有向連通圖的外向樹與內向樹數目的演算法及其MATLAB實現71
4.12最小生成樹問題73
4.13求最小生成樹的Kruskal演算法及其MATLAB實現74
4.13.1 Kruskal演算法的基本思想74
4.13.2 Kruskal演算法的MATLAB實現74
4.14求最小生成樹的Prim演算法及其MATLAB實現76
4.14.1 Prim演算法的基本思想76
4.14.2 Prim演算法的MATLAB實現77
習題四79
第5章Euler圖和Hamilton圖81
5.1 Euler圖81
5.2「一筆畫」問題及其理論81
5.3中國郵遞員問題82
5.4 Fleury演算法及其MATLAB實現82
5.4.1 Fleury演算法的步驟82
5.4.2 Fleury演算法的MATLAB實現82
5.5 Hamilton圖87
5.6旅行售貨員問題88
5.7改良圈演算法及其MATLAB實現89
習題五92
第6章 匹配問題及其演算法93
6.1問題起源——婚配問題93
6.2二分圖的有關知識93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5應用案例——BernolliEuler錯放信箋問題95
6.6尋求圖的一個較大基數匹配演算法及其MATLAB實現95
6.7人員分配問題97
6.8匈牙利演算法及其MATLAB實現97
6.8.1匈牙利演算法基本步驟97
6.8.2匈牙利演算法的MATLAB實現98
6.8.3案例及其MATLAB實現100
6.9最優分配問題101
6.10 KuhnMunkres演算法及其MATLAB實現101
6.10.1 KuhnMunkres演算法的基本思想101
6.10.2利用可行頂點標記求最佳匹配的KuhnMunkras演算法步驟102
6.10.3 KuhnMunkres演算法的MATLAB實現102
6.10.4簡單實驗105
習題六107
第7章 網路流的演算法108
7.1網路、流和割108
7.1.1網路和流108
7.1.2割109
7.2網路的最大流問題110
7.3最大流最小割定理110
7.4 FordFulkerson標號演算法及其MATLAB實現111
7.4.1 FordFulkerson標號演算法的基本步驟111
7.4.2 FordFulkerson 標號演算法的MATLAB實現112
7.4.3案例及其MATLAB實現113
7.5 Dinic演算法及其MATLAB實現114
7.5.1 Dinic演算法的基本思想114
7.5.2 Dinic演算法的MATLAB實現115
7.5.3案例