圖論導論

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

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

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

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

圖形:

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

StackOverflow 文件

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

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

StackOverflow 文件

棋枰的騎士路徑

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

相鄰節點:

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

有向圖和無向圖:

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

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

加權和未加權圖:

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

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

路徑:

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

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

學位:

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

在有向圖中,節點有兩種型別的度:

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

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

StackOverflow 文件

一些與圖論相關的演算法

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