【圖論Graph】Part2：深入認識Graph的基本概念、組成和應用

上一篇我們初步了解到圖論的簡單定義，以及可應用的範疇，這篇會更深入一點認識 Graph並瞭解其基本概念，還沒有看過上一篇的話可以點連結: 【圖論Graph】Part1：初探圖形與圖形演算法之應用。

Photo by Marvin Meyer on Unsplash

圖形的基本概念與組成

• 定義與重要性：解釋圖形是如何表示實體間的關係
• 節點（Node）：代表實體，例如人、地點或物體
• 邊（Edge）/關係（Relation）：連接節點，表示節點間的關係
• 屬性（Attribute）：節點或邊的額外資訊，如權重、標籤或顏色

舉個社交網絡圖例子

假設我們有一個小型的社交網絡，包含三位用戶：Alice, Bob, 和 Charlie。

• 定義與重要性：在這個社交網絡圖中，用戶被表示為節點（Node），用戶間的友誼關係被表示為邊（Edge）。這樣的圖形表示使我們能夠可視化並分析用戶間的關係結構。
• 節點（Node）: Alice, Bob, 和 Charlie 都是圖中的節點，每個節點代表一個社交網絡中的用戶。
• 邊（Edge）/關係（Relation）

1. • 如果Alice和Bob是朋友，那麼在Alice和Bob之間會有一條邊來表示他們的友誼。
   • 同樣地，如果Bob和Charlie也是朋友，則Bob和Charlie之間也會有一條邊。

• 屬性（Attribute）

1. • 每個節點（人）可以有額外的屬性，例如：
   • • Alice 可能有屬性：{"年齡": 25, "居住地": "紐約"}
     • Bob 的屬性可能是：{"年齡": 30, "居住地": "加州"}
     • Charlie 的屬性可能是：{"年齡": 28, "居住地": "德州"}
   • 邊也可以有屬性，表示關係的強度或類型，例如：
   • • Alice和Bob的友誼邊可以有屬性：{"關係強度": "高"}
     • Bob和Charlie的友誼邊可以有屬性：{"關係強度": "中"}

這個例子說明如何用圖形的方式表示和分析一個社交網絡中的人物及其關係。

圖的類型與種類

圖形有許多的類型與種類，在取得一張 Graph 時、或是在建構一張 Graph 時，可以去思考應該是建構成哪一類型的圖，才符合實際場景。

• 簡單圖與多重圖：簡單圖中不允許有重邊或迴圈，多重圖中則允許。
  應用於：社交網絡分析、交通網絡、物流管理中經常使用簡單圖來表示實體間的單一關係，而多重圖可以用於表示系統中存在多種關係或多條路徑的情況，如航班網絡中同兩地之間的多班次航班。
• 有向與無向圖：有向圖中的邊具有方向，無向圖中的邊則沒有
• 連通與不連通圖：在連通圖中，任意兩個節點間都存在路徑
• 加權與不加權圖：加權圖的邊賦予了權重，不加權圖則沒有。加權圖在考慮成本、時間或距離等因素的最優路徑問題中特別有用，例如在路徑規劃、網絡流量分析中。不加權圖適用於只關心連接性而非連接的強度或成本的情況。
• 子圖、補圖、雙分圖：特定條件下的圖形結構。

圖形演算法三大類型:

1. 路徑查找：如 Dijkstra 算法，用於找到節點間的最短路徑。
2. 中心性分析：度中心性、接近中心性、中介中心性，用於識別網絡中的關鍵節點。
3. 社群檢測：群體最大化，用於發現網絡中的自然分群或社群。

小心得

今天對於圖形有基本的認識、知道它的定義以及種類，並且擬定了之後的學習方向，將會以這三大類型的演算法為學習目標，因為這也是圖形領域中最被廣泛應用，今天的內容比較簡單～之後開始應會包含實作的內容，將會有趣一些！感謝讀到這裡的你～希望有幫助到一起在學習 Graph 的人～下次見囉！

上一篇：【圖論Graph】Part1：初探圖形與圖形演算法之應用。