圖論導論

圖論是對圖的研究，圖是用於模擬物件之間成對關係的數學結構。

你知道嗎，地球幾乎所有的問題都可以轉化為道路和城市的問題，並解決了嗎？圖論是多年前發明的，甚至在計算機發明之前。萊昂哈德尤拉寫了一篇關於柯尼斯堡七橋的論文，這篇論文被認為是圖論的第一篇論文。從那以後，人們逐漸認識到，如果我們能夠將任何問題轉化為這個城市 - 道路問題，我們可以通過圖論輕鬆地解決它。

圖論有許多應用。最常見的應用之一是找到一個城市與另一個城市之間的最短距離。我們都知道，要訪問你的 PC，此網頁必須從伺服器傳送許多路由器。Graph Theory 幫助它找出需要交叉的路由器。在戰爭期間，需要轟炸哪條街道以便將首都與其他城市斷開，這也可以通過圖論來找到。

讓我們首先學習圖論的一些基本定義。

圖形：

比方說，我們有 6 個城市。我們將它們標記為 1,2,3,4,5,6。現在我們將彼此之間有道路的城市連線起來。

這是一個簡單的圖表，其中一些城市顯示連線它們的道路。在圖論中，我們將這些城市稱為 Node 或 Vertex ，道路稱為 **Edge。**圖只是這些節點和邊的連線。

一個節點可以代表很多東西。在一些圖表中，節點代表城市，一些代表機場，一些代表棋盤中的正方形。 Edge 表示每個節點之間的關係。這種關係可以是從一個機場到另一個機場的時間，騎士從一個廣場到所有其他廣場的移動等。

棋枰的騎士路徑

簡單來說， Node 表示任何物件， Edge 表示兩個物件之間的關係。

相鄰節點：

如果節點 A 與節點 B 共享邊緣，則認為 B 與 A 相鄰。換句話說，如果兩個節點直接連線，則將它們稱為相鄰節點。一個節點可以具有多個相鄰節點。

有向圖和無向圖：

在有向圖中，邊緣在一側具有方向標記，這意味著邊緣是單向的。另一方面，無向圖的邊緣在兩側都有方向標記，這意味著它們是雙向的。通常，無向圖表示邊緣兩側沒有任何符號。

我們假設有一個聚會正在進行。聚會中的人是由節點代表的，如果他們握手，兩個人之間就有一條優勢。然後這個圖表是無向的，因為任何人 A 與人 B 握手，當且僅當 B 也與 A 握手時。相反，如果從人 A 到另一個人 B 的邊緣對應於 A 的欣賞 B ，那麼該圖是指向的，因為讚美不一定是往復的。前一種型別的圖形稱為無向圖形，邊緣稱為無向邊緣，而後一種型別的圖形稱為有向圖和邊被稱為有向邊。

加權和未加權圖：

加權圖是將數字（權重）分配給每個邊的圖。這些權重可能代表例如成本，長度或容量，這取決於手頭的問題。

未加權的圖表恰恰相反。我們假設，所有邊緣的權重都相同（大概是 1）。

路徑：

路徑表示從一個節點到另一個節點的方式。它由邊緣序列組成。兩個節點之間可以有多條路徑。

在上面的示例中，從 A 到 D 有兩條路徑。 A-> B，B-> C，C-> D 是一條路徑。該路徑的成本是 3 + 4 + 2 = 9 。此外，還有另一種路徑 A-> d 。這條路的成本是 10 。成本最低的路徑稱為最短路徑。

學位：

頂點的度數是連線到它的邊的數量。如果有任何邊緣連線到兩端的頂點（一個迴圈），則計算兩次。

在有向圖中，節點有兩種型別的度：

• In-degree：指向節點的邊數。
• Out-degree：從節點指向其他節點的邊數。

對於無向圖，它們簡稱為度。

一些與圖論相關的演算法

• Bellman-Ford 演算法
• Dijkstra 演算法
• Ford-Fulkerson 演算法
• Kruskal 的演算法
• 最近鄰演算法
• Prim 的演算法
• 深度優先搜尋
• 廣度優先搜尋