Введение в теорию графов: структура, типы и методы представления

前幾天我們花了很多篇幅在講樹狀結構，今天要進到新單元 圖形結構 了~ 圖形結構是以 頂點 (Vertix)和 邊 (Edge) 所組成的集合 Graph Theory或 拓樸理論(Topology)源自於 Koenigsberg bridge 問題 有興趣可以點開來看 ~ 這邊偏向離散數學的範疇就不細講了 跟樹狀結構差別最大的地方在於，圖形結構的頂點可以任意連接，甚至形成迴圈 頂點 (Vertices) : 圖中的節點 邊 (Edge) : 兩頂點間的連線叫做「邊」 圖 (Graph) : 圖是由頂點和邊組合成的集合，記為 G(E,V) 有向圖 : 邊具有方向性，例如<v1,v2> 其中v1代表前端，v2代表尾端 <v1,v2> ≠ <v2,v1> 無向圖 : 邊不具方向性，(v1,v2)=(v2,v1) 完整圖 : n(n-1) 個邊，為「有向完整圖」n(n-1)/2 個邊，為完整圖 多重圖形 : 多重圖形不是圖，兩個頂點間有多條邊即為多重圖形 相鄰 (adjacent)：若兩個頂點之間有邊直接相連，稱這兩個頂點互為相 鄰。例如邊 (v1, v2)，則 v1 與 v2 相鄰。 附著 (incident) :邊 e 連接頂點 v1 和 v2,則稱邊 e 「附著」於 v1 和 v2,或稱 v1、v2 與邊 e 相互附著 如附著在 頂點 5的邊有 (1,5),(4,5),(5,6) 分支度 (degree) : 一個頂點所連接的邊數量 公式 : 當圖有n個頂點，e個邊，di為頂點i的分支度， 內分支度和外分支度 連通 (connected) : 兩個頂點之間存在至少一條路徑可以互相到達，稱這兩個頂點是連通的 路徑(path) : 路徑是可以由一個邊或數個邊所組成的，從某個頂點出發，經過一連串的邊，到達另一個頂點所形成的頂點序列。如果路徑中所有頂點都不重複，稱為「簡單路徑(Simple Path)」 子圖(subgraph) : 設圖 G 由頂點集合 V(G) 與邊集合 E(G) 組成 若另一個圖 G' 滿足 V(G') ⊆ V(G) 且 E(G') ⊆ E(G) 則稱 G' 為 G 的子圖。 換句話說，子圖的頂點必須是原圖頂點的子集合，而且子圖的邊也必須是原圖中確實存在的邊，不能包含原圖沒有的連線 最常見的有相鄰矩陣表示法 (Adjacency Matrix)、相鄰串列表示法 (Adjacency List) 假設圖有 n 個頂點，則使用 n x n 的矩陣來存放matrix[i][j]= 1 代表頂點 i 和頂點 j 之間有邊相連，0 代表沒有 對應的相鄰矩陣: 無向圖: 任意頂點i的分支度為，或是各列 (各行) 的和，C的分支度為1+0+0+1=2 有向圖 #include <vector> using namespace std; // 用二維陣列表示相鄰矩陣,4個頂點 vector<vector<int>> graph(4, vector<int>(4, 0)); void addEdge(int u, int v) { graph[u][v] = 1; graph[v][u] = 1; // 無向圖,兩個方向都要設定 } 每個頂點對應一個串列(或陣列)，存放與它相鄰的所有頂點 圖 G 的頂點集合 V(G) = {1, 2, 3, 4, 5},邊集合 E(G) = {(1,2), (2,3), (3,4)},請問下列哪一個是 G 的合法子圖? (A ) 頂點 {1, 2, 5},邊 {(1,2), (1,5)} (B ) 頂點 {1, 2, 3},邊 {(1,2), (2,3)} (C ) 頂點 {1, 3},邊 {(1,3)} 參考資料和書籍