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

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

Photo by Marvin Meyer on Unsplash

圖形的基本概念與組成

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

舉個社交網絡圖例子

• 定義與重要性：在這個社交網絡圖中，用戶被表示為節點（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：初探圖形與圖形演算法之應用。