圖形的起源

圖論起源於1736年，Leonhard Euler(台灣舊譯尤拉)為了解決Seven Bridges of Königsberg問題，而想出來的一種data structure。

圖形 Graph

圖形可以很簡單的描述問題，比起文字更容易讓人理解，所以圖形是應用非常廣泛的資料結構。
ex: 系統分析、電路分析、電話的佈線、公路圖。

定義

常用 G = (V, E) 表示圖形，亦即一個圖形是由兩種集合組成。

• V -> Vertices，頂點的集合。
• E -> Edges，邊的集合。

分類

圖形大概可以分成 有向圖 和 無向圖 兩大類。

• 有向圖 (Directed Graph)，顧名思義就是每個邊都是有方向性的，也就是每個邊都會有箭頭表示方向，且每個有方向的邊都可以用有序對來表示。
  ex: 頂點a指向頂點b的有向邊，其有序對就表示成 <a, b> 。a就是這個有向邊的箭尾(tail)，b則是這個有向邊的箭頭(head)。
• 無向圖 (Undirected Graph)，就是每個邊都沒有方向性，且每個無向邊都是由無序對來表示。
  ex: 頂點a指向頂點b的無向邊，其無序對就表示成 (a, b) 或是 (b, a) 。

• 簡圖 (Simple Graph)
  1. 頂點沒有任何邊連向自己，也就是沒有自成迴路(Self loop)。
  2. 任何一對不同頂點之間，無向圖只會有一個邊相連，有向圖也只能容許雙向各有一個邊。

名詞

1. 相鄰 (adjacent) : 頂點a和頂點b之間如果有邊相連，即稱此兩個頂點為相鄰頂點(Adjacent vertices)。
2. 路徑 (Path) : 路徑就是一個邊或是好幾個邊，頭尾相連，形成一個連續邊的集合。
   • 如果頂點a和頂點b是有路徑可以通的，就會稱這兩個頂點是連通的 (Connected)。
   • 相鄰的兩個頂點一定是連通的，但是連通的兩個頂點不一定會是相鄰的。
3. 環路 (Cycle) : 一條路徑的起點和終點是相同的頂點。
4. 子圖 (Subgraph) : 一個圖形G = (V, E)，若有另一個圖形G1，V1和E2都是屬於圖形G的點且邊，就可以稱G1是G的子圖。
5. 連通圖(Connected graph):圖形G，任何一對不同頂點之間都有路徑可以連通。
   • 強連通圖: 任一對頂點之間都有路徑互通
6. 完全圖 (Complete graph) : 圖形G中任何一對頂點都是相鄰的。
   • 有n個頂點的無向完全圖會有: n(n-1)/2個無向邊。
   • 有n個頂點的有向完全圖會有: n(n-1)個有向邊。
7. 分支度 (Degree) :
   • 在無向圖中，頂點a與n個邊相連，則頂點a的分支度為n。
   • 在有向圖中，頂點a如果有n個邊出去，則頂點a的出分支度(outdegree)為n。
   • 在有向圖中，頂點a如果有n個邊進來，則頂點a的入分支度(indegree)為n。

參考

細談資料結構 第六版
ISBN 978-986-312-014-8

不要跟別人比，而是跟自己比。

可以將對方視為目標，不需與之做比較。
共勉之。

示意圖生產中，請稍後。