圖表和應用

許多現實世界的問題可以使用圖形演算法來解決。圖對於建模和解決現實問題很有用。例如，找到兩個城市之間的最少航班數量的問題可以使用圖來建模，其中頂點代表城市，邊代表兩個相鄰城市之間的航班​​，如下圖所示。求最小聯程航班數的問題
兩個城市之間的問題簡化為尋找圖中兩個頂點之間的最短路徑。

圖問題的研究稱為圖論。圖論由 Leonhard Euler 於 1736 年創立，當時他引入圖術語來解決著名的柯尼斯堡七橋問題。普魯士柯尼斯堡市（現為俄羅斯加里寧格勒）被普雷格爾河分開。河上有兩個島嶼。城市和島嶼由七座橋樑連接，如下圖（a）所示。問題是，一個人可以步行，每座橋只穿過一次，然後回到起點嗎？歐拉證明這是不可能的。

為了建立證明，歐拉首先透過消除所有街道來抽象化柯尼斯堡城市地圖，產生如上圖 (a) 所示的草圖。接下來，他用一個點（稱為頂點或節點）替換每個陸塊，並用一條線（稱為邊）替換每個橋，如圖所示上圖(b)。這種具有頂點和邊的結構稱為圖。

看圖，我們問是否存在一條從任意頂點出發，恰好遍歷所有邊一次，並返回到起始頂點的路徑。歐拉證明，要存在這樣的路徑，每個頂點都必須有偶數條邊。因此，柯尼斯堡七橋問題無解。

圖問題通常使用演算法來解決。圖算法在電腦科學、數學、生物學、工程、經濟學、遺傳學和社會科學等各個領域都有許多應用。

基本圖形術語

圖由頂點和連接頂點的邊組成。本章不假設您具備任何圖論或離散數學的先驗知識。我們使用簡單明了的術語來定義圖表。

什麼是圖表？圖是一種數學結構，表示現實世界中實體之間的關係。例如，上圖代表城市之間的航班​​，下圖(b)代表陸地之間的橋樑。

圖由一組非空頂點（也稱為節點或點）和一組連接頂點的邊組成。為了方便起見，我們將圖定義為 G = (V, E)，其中 V 表示一組頂點，E 表示一組邊。例如下圖的V和E如下：

V = {"西雅圖", "舊金山", "洛杉磯",
「丹佛」、「堪薩斯城」、「芝加哥」、「波士頓」、「紐約」、
「亞特蘭大」、「邁阿密」、「達拉斯」、「休士頓」}；

E = {{"西雅圖", "舊金山"},{"西雅圖", "芝加哥"},
{"西雅圖", "丹佛"}, {"舊金山", "丹佛"},
...
};

圖可以是有向圖或無向圖。在有向圖中，每條邊都有一個方向，這表示您可以透過該邊從一個頂點移動到另一個頂點。您可以使用有向圖來建模父/子關係，其中從頂點 A 到 B 的邊表示 A 是 B 的父項。下圖 (a) 顯示了一個有向圖。

在無向圖中，您可以在頂點之間雙向移動。下圖是無向圖。

邊可以加權也可以不加權。例如，您可以為上圖中圖表中的每條邊分配一個權重，以表示兩個城市之間的飛行時間。

圖中的兩個頂點稱為相鄰如果它們由同一條邊連接。類似地，如果兩邊連接到同一頂點，則稱它們相鄰。圖中連接兩個頂點的邊稱為與兩個頂點關聯。頂點的度是與其相關的邊的數量。

如果兩個頂點相鄰，則稱為鄰居。類似地，如果兩邊相鄰，則稱為鄰居。

循環是將頂點連結到自身的邊。如果兩個頂點透過兩條或多條邊連接，這些邊稱為平行邊。 簡單圖是沒有任何環或平行邊的圖。在完全圖中，每兩對頂點都是相連的，如下圖(b)所示。

如果圖中任兩個頂點之間存在路徑，則該圖是連通的。圖 G 的 子圖 是一個圖，其頂點集是 G 的子集，邊集是 G 的子集。例如，上圖 (c) 的圖是上圖(b)的子圖。

假設圖是連通且無向的。 循環是一條從一個頂點開始並在同一頂點結束的閉合路徑。如果連通圖沒有環，則它是樹。圖 G 的生成樹是 G 的連通子圖，而該子圖是包含 G 中所有頂點的樹。

以上是圖表和應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！