圖論及其演算法是什麼

A. 簡介圖論演算法

圖論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)

B. 圖論的基本概念有哪些

圖論基本概念
重要定義：
有向圖：每條邊都是有向邊的圖。
無向圖：每條邊都是無向邊的圖。
混合圖：既有有向邊又有無向邊的圖。
自迴路：一條邊的兩端重合。
重數：兩頂點間若有幾條邊，稱這些邊為平行邊，兩頂點a,b間平行邊的條數成為（a,b）的重數。
多重圖：含有平行邊的圖。
簡單圖：不含平行邊和自迴路的圖。
注意！一條無向邊可以用一對方向相反的有向邊代替，因此一個無向圖可以用這種方法轉化為一個有向圖。
定向圖：如果對無向圖G的每條無向邊指定一個方向由此得到的有向圖D。稱為的G定向圖.
底圖：如果把一個有向圖的每一條有向邊的方向都去掉，得無向圖G稱為的D底圖。
逆圖：把一個有向圖D的每條邊都反向由此得到的圖稱為D的逆圖。
賦權圖：每條邊都賦上了值。
出度：與頂點相連的邊數稱為該定點的度數，以該定點為始邊的邊數為出度。 入度：以該定點為終邊的邊數為入度。
特殊！度數為零的定點稱為孤立點。度數為一的點為懸掛點。
無向完全圖：在階無向圖中如果任何兩點都有一條邊關連則稱此圖是無向完全圖。Kn
完全有向圖：在階有向圖中如果任意兩點都有方向相反的有向邊相連則稱此圖為完全有向圖。
竟賽圖：階圖中如果其底圖是無向完全圖，則程此有向完全圖是竟塞圖。
注意！n階有向完全圖的邊數為n的平方；無向完全圖的邊數為n(n-1)/2。
下面介召圖兩種操作：①刪邊：刪去圖中的某一條邊但仍保留邊的端點。
②刪點：刪去圖中某一點以及與這點相連的所有邊。
子圖：刪去一條邊或一點剩下的圖。
生成子圖：只刪邊不刪點。
主子圖：圖中刪去一點所得的子圖稱的主子圖。
補圖：設為階間單無向圖，在中添加一些邊後，可使成為階完全圖；由這些添加邊和的個頂點構成的圖稱為的補圖。
重要定理：
定理5.1.1 設圖G是具有n個頂點m條邊的有向圖，其中點集V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理5.1.2 設圖G是具有n個頂點m條邊的無向圖，其中點集V={v,v,v,……,v}
deg(vi)=2m
推論 在無向圖中，度數為積數的頂點個數為偶數。
通路和富權圖的最短通路
1通路和迴路
基本概念：
通路的長度：通路中邊的條數。
迴路：如果通路中始點與終點相同。
簡單通路：如果通路中各邊都不相同。
基本通路：如果通路中各頂點都不相同。顯然（基本通路一定是簡單通路，但簡單通路不一定是基本通路）
可達：在圖G中如果存在一條v到d通路則稱從v到d是可達。
連通：在無向圖中如果任意兩點是可達的，否則是不連通的。
強連通：在有向圖中如果任意兩點是互可達的。
單向連通：在有向圖中如果存在任意兩點的通路。
弱連通：在有向圖中如果其底圖是連通的。
權：在圖的點或邊上表明某種信息的數。
賦權圖：含有權的圖。
賦權圖的最短通路問題的演算法：先求出到某一點的最短通路，然後利用這個結果再去確定到另一點的最短通路，如此繼續下去，直到找到到的最短通路為止。
指標：設V是圖的點集，T是V的子集，且T含有z但不含a，則稱T為目標集。在目標集T中任取一個點t，由a到t但不通過目標集T中其它點所有通路中，個邊權和的最小者稱為點t關與T的指標記作DT(t)。
圖和矩陣
住意兩個的區別：A·A 中元素的意義：當且僅當a 和a 都是1時，a a =1而a 和a 都為1意味著圖G中有邊(v ,v )和(v ,v )。於是可得如下結論：從頂點v 和v 引出的邊，如果共同終止於一些頂點，則這些終止頂點的數目就是b 的值；特別對於b ，其值就是v 的出度。

A ·A中元素的意義：當且僅當a 和a 都為1時，a a =1，這意味著圖中有邊(v ,v )和(v ,v )。於是的得如下結論：從某些點引出的邊，如果同時終止於v 和v ，則這樣的頂點數就是的值。特別對於b ，其值就是的v 入度。

冪A 中元素的意義：當m=1時，a 中的元素=1，說明存在一條邊(v ,v )，或者說從v 到v 存在一條長度為一的通路。

A 中元素a 表示從v 到v 的長度為m的所有通路的數目。
歐拉圖
主要定義：
如果圖中存在一條通過圖中個邊一次且僅一次的迴路，則稱此迴路為歐拉迴路，具有歐拉迴路的圖稱為歐拉圖。

如果圖中存在一條通過圖中各邊一次且僅一次的通路，則稱此迴路為歐拉通路，具有歐拉通路的圖稱為半歐拉圖。

主要定理：一個無向連通圖是歐拉圖的充要條件是圖中各點的度數為偶數。

一個無向連通圖是半歐拉圖的充要條件是圖中至多有兩個奇數度點。

設圖G是有向連通圖，圖G是歐拉圖的充要條件是圖中每個頂點的入度和出度相等。

設圖G是有向連通圖，圖G是半歐拉圖的充要條件是至多有兩個頂點，其中一個頂點入度比它的出度大1，另一個頂點入度比它的出度少1；而其他頂點的入度和出度相等。
哈密頓圖
主要定義：如果圖G中存在一條通過圖G中各個頂點一次且僅一次的迴路，則稱此迴路為圖的哈密頓迴路；具有哈密頓迴路的圖稱為哈密頓圖。

如果圖G中存在一條通過圖G中各個頂點一次且僅一次的迴路，則稱此迴路為圖的哈密頓迴路；具有哈密頓迴路的圖稱為哈密頓圖。
主要定理：設圖G是哈密頓圖，如果從G中刪去個p頂點得到圖G』，則圖G』的連通分支數小於等於p。

設圖G是具有n個頂點的無向簡單圖，如果G中任意兩個不同頂點的度數之和大於等於n-1，則具有哈密頓通路，即G是半哈密頓圖。

設圖G是具有n個頂點的無向簡單圖，如果G中任意兩個不同頂點的度數之和大於等於n，則G具有哈密頓迴路，即G是哈密頓圖。

C. 求解：圖論中常見的最短路徑演算法有幾種都是什麼

主要是有三種、、

第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、

第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、

第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、

D. 圖論演算法的介紹

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

E. 圖論演算法的教材

我想很多學習圖論的人都知道J.A. Bondy和U.S.R. Murty著的《Graph Theory with Application》(Elsevier,1976)是圖論教材中的經典，時至今日，仍不失為初學者較好的入門書。還記得蘭州交通大學的張忠輔教授說過，國內第一屆圖論學會就是把大家集中起來學習邦迪的《Graph Theory with Application》，由此可見這本書對國內圖論屆的影響是如此之大。吳望名等人將其譯成中文版本《圖論及其應用》（北京：科學出版社，1984），1988年張克民等人編寫了該書的參考答案《圖論及其應用習題解答》（清華大學出版社，1988）。
在2008年J.A. Bondy和U.S.R. Murty出了新書《Graph Theory》(GTM 244, Springer, 2008), 大家可不妨將其看成是《Graph Theory with Application》的第二版，這本書在內容上做了重新調整，畢竟在第一版出版後的近30年裡涌現出了很多新的結果，所以《Graph Theory》在內容上加進了一些新的結果，這本書我只是讀了其中的幾章，覺得寫的非常棒，建議大家能夠讀讀，這里也值得一提的是將第一版最後提出的50個問題進行了更新，並補充了一些新的問題。總之，我個人認為，《Graph Theory》的確是一部很優秀的圖論教材。
中國科學技術大學出版社出版的《圖論及其演算法》，融有向圖和無向圖為一整體，系統地闡述了圖論的基本概念、理論、方法及其演算法，內容包括圖的基本概念、Euler圖與Hamilton圖、圖論演算法、樹及其應用、平面圖、獨立集與匹配、網路流和Petri網。 書中附有大量例題和習題，而且大部分習題有詳細解答。 該書選材精煉全面，內容處理恰當且有新意，立論嚴謹，敘述條理清晰，語言流暢。 該書可用作高校計算機、電子、信息、管理、數學等專業本科生必修課教材，也可供相關專業的研究人員、教師及圖論工作者參考。