Foreword: Graph Theory by CK63rd poao899 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from

Size: px

Start display at page:

Download "Foreword: Graph Theory by CK63rd poao899 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from"

掘坟温
4 years ago
Views:

1 Foreword: Graph Theory 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from Wiki) Definition: Graph 圖, 和一般我們看到的圖不一樣, 這裡的圖只有一堆點以及點與點的連接關係一張圖常用一個點集合跟一個邊或弧的集合表示也就是 G=(V,E), 其中 G 代表圖 V 代表點集合 E 代表邊或弧的集合 Vertex 頂點, 別名 Node( 節點 ) 圖論在乎的就是點與其他點的關係 Edge 邊, 是用來表示關係用的單位通常用 e(v 1,v 2 ) 表示, 表示有一條邊連接著 A 和 B 注意邊是 undirected 無向的, 即 e(v 1,v 2 ) 跟 e(v 2,v 1 ) 在講的是同一件事 v 1 和 v 2 有直接聯繫注意的是兩個點之間可能有不只一條邊甚至可能有邊是自己連自己 Arc 弧, 有人也稱為有向邊可紀錄為 arc(v 1,v 2 ) 表示有一個關係是從 v1 到 v2, 注意這個關係是有向的, 即 arc(v 1,v 2 ) arc(v 2,v 1 ) Adjacent 相鄰, 是表達點之間的關係, 當我們說兩個點相鄰, 就表示他們之間存在著至少一條邊即 v1 和 v2 相鄰若且唯若 : (1) 無向圖中, 存在至少一條邊 e(v 1,v 2 ) (2) 有向圖中, 存在至少一條弧 arc(v 2,v 1 ) Directed Graph 有向圖, 這張圖所有連線皆為弧 ( 有向邊 ) Undirected Graph 無向圖, 這張圖所有連線皆為無向邊 Mixed Graph 混合圖, 這張圖有弧 ( 有向邊 ) 也有無向邊 Path(Walk) 路徑, 一個點邊交錯形成的序列 v 1,e 1,v 2,e 2,,e n-1,v n 其中所有的 v V 以及 e E e i =e(v i,v i+1 ) Simple Path 簡單路, 一條路徑, 頂點與邊都不重複 Cycle 環, 一條路徑, 開頭與結尾相等且至少有一個邊 Simple Cycle 簡單環, 一個頂點與邊都不重複的環 Simple Graph 簡單圖, 這張圖不存在著重邊或多重弧及 self cycle 自圈 Connected graph 連通圖, 這張圖任何點對都有路徑相連 Bipartite Graph 二分圖, 這張圖可以把每個點上成黑白兩色之一, 使得所有相鄰的點都塗上不同顏色亦即任兩同色點皆沒有邊相連 Directed Acyclic Graph 有向無環圖, 這張圖為有向且不存在 cycle 環 Tree 樹, 這張圖任兩個點都有路徑相連且不存在 cycle 環

2 Degree 分枝度,deg(v) 即為和點 v 有關係的邊的數量所有頂點度總和 =2 E In-Degree 入度,deg + (v) 有向圖中目標為該點的弧的數量 Out-Degree 出度,deg - (v) 有向圖中起始端為該點的弧的數量對一張有向圖而言, 入度總和 = 出度總和 ( 握手定理 ) Sub-Graph 子圖, 若兩個圖 G=(V,E) G =(V,E ) 其中 V 包含 V 且 E 包含 E, 則稱 G 為 G 的一個子圖 Spanning Tree 生成樹, 樹 T 包含圖 G 的所有頂點則稱 T 為 G 的一棵生成樹 Spanning Sub-Graph 生成子圖,G 的一個子圖 G 包含 G 的所有頂點 Store a Graph 看了那麼多亂七八糟 (?) 的定義, 接下來要考慮的是怎麼儲存一張圖一般常見的用法有 Adjacent Matrix 以及 Adjacent List 兩種, 其他常見的還有 Edge List 以及 Forward Star Adjacent Matrix 相鄰矩陣 : 開一個 adj[v][v] 的陣列對於任一點對 V 1,V 2, 若 adj[v 1 ][V 2 ]=true 表示存在邊 e(v 1,V 2 ) 或弧 arc(v 1,V 2 ) 反之則是沒有邊優點 : 實做方便修改方便缺點 : 枚舉所有邊由 O(E) 變成 O(V 2 ) 不能處理重邊記憶體過大(V 2 ) Adjacent List 相鄰串列 : 對每個點保存一個串列紀錄這個點連出去所有的邊, 雖然要開 V 條串列但是串列總大小會是 E ( 無向圖為 2 E ) 優點 : 稀疏圖效率高枚舉所有邊只需要 O(E) 可處理重邊缺點 : 實做稍複雜刪邊不容易 Edge List 邊表 : 開一個陣列將所有邊存下來並且對於邊依照 (1) 先比較 v 1 大小 (2) 相等則比較 v 2 的規則排序這樣需要 O(E lg E) 預處理, 但只需 E 的記憶體儲存優點 : 省記憶體 ( 相較串列省去開指標 ) 實做算簡易缺點 : 查找每個點連出所有邊需要 O(lg E) 事實上, 可以給邊表一些優化使得預處理作到 O(E) 查找也作到 O(1), 這樣我們通常稱為 Forward Star 前向星算是一種優秀的存圖結構

3 Graph Traversal 一張圖的 Traversal 是指一張圖經過某種順序通盤讀取整張圖的資訊拜訪過圖內所有頂點常見的有 Depth-First Search 和 Breadth-First Search 兩種其中的差別是訪問節點的優先順序圖經過遍歷後通常會形成一棵生成樹或是許多生成樹的森林對一張有向圖和一個森林, 我們可以把所有邊分成四類 : Tree Edge 生成樹上的邊 Back Edge 連向自己祖先的非生成樹上的邊 Forward Edge 連向自己子孫的非生成樹上的邊 Cross Edge 不屬於以上三種的邊 Depth-First Search 深度優先搜索 (DFS): 深度優先搜索會先搜尋一個點的子節點而非兄弟節點一般會用遞迴進行, 當資料量較大時會採取堆疊實做兩者時間複雜度皆為 O(V+E) 一般來講, 用 DFS 形成的生成樹稱為 DFS 樹, 以下是用堆疊實做的虛擬碼 : Function DFS (bool[] Visited, Vertex Start, Stack Stk) Push Start into Stk While Stk not empty Now the top element of Stk Pop the top element of Stk If Visited[Now] = false Visited[Now] true // 注意這行位置 Foreach Vertex p adjacent to Now If Visited[p] = false Push p into Stk 在 DFS 搜尋樹上, 上述四種邊只會出現兩種 (Tree Edge/Back Edge), 依此性質可以用來解決許多題目不過必須先引入 Timestamp 時間戳記觀念 Timestamp 時間戳記 : 時間戳記就是在每個點戳上數字表示進入頂點 / 離開頂點這個概念雖然簡單但是可以解決很多問題要注意的是用堆疊實做 DFS+ 時間戳記的寫法依照字典順序從 A 開始進行 DFS 進入順序 : A, B, C, E, D, F, G 離開順序 : D, F, E, G, C, B, A

4 Topological Sort 給定一張有向圖,Topological Sort 拓樸排序是希望找到一個拜訪點的順序, 讓該點被拜訪到時所有有弧指向它的點都已經被拜訪過可見的是一個有 Cycle 的圖是不可能存在這類順序, 故必須要是一個 DAG 有向無環圖才能透過拓樸排序找到一組拜訪順序另外, 合法拜訪順序也並不唯一有一個簡單的算法是每次檢查所有頂點是否滿足, 滿足就將該點拔去這個算法複雜度為 O(V 2 +E) 但是對於這個複雜度還不能滿意考慮一下 DFS 離開順序的時間戳記, 該點的離開順序表示所有戳記比該點大的一定是 (1) 自己的子孫 (2) 其他子樹上的點, 故只要將戳記順序倒轉便是一種合法的拓樸順序這樣總複雜度是 O(V+E) 以下是用堆疊實做之虛擬碼: Function Topo_Sort (bool[] Visited, Vertex[] Stamp) Time 0 Foreach Vertex Start in the Graph If Visited[Start] = false Call DFS(Visited, Start, Time, Stamp) Function DFS(bool[] Visited, Vertex Now, int& Time, Vertex [] Stamp) Visited[Now] true Foreach Vertex p adjacent to Now If Visited[p] = false Call DFS(Visited, p, Time, Stamp) Stamp[Time] Now Time Time + 1 TIOJ1092 跳格子遊戲 (NPSC2006 初賽 ) 給你一個 DAG, 兩位玩家輪流由起點各走一步, 走到終點的人贏如果兩人每一步都是選擇對自己最有利的路徑, 問最後獲勝者 UVa 200 Rare Order 有一個不知道順序的字元集給你很多這個字元集組成的字串, 並告訴你這些字串是依照這個字元集的字典順序排好的請輸出每個字符的大小關係

5 Strong-Connected Component Strong-Connected 強連通性質是, 對於一張有向圖而言, 選定任一點對 (V 1,V 2 ), 一定找得到至少一條路徑始於 V 1 終於 V 2 而現在的任務是把任意有向圖分成許多個符合強連通性質的子圖, 我們稱它為 Strong-Connected Component 強連通元件 (SCC) 而且希望每個元件是 maximal 的 ( 加入任何其他點皆會破壞強連通性質 ) 對於這個問題, 有兩種常見算法 :Kosaraju s 以及 Tarjan s 兩種在時間複雜度皆是 O(V+E), 下面只介紹 Kosaraju s: Kosaraju s: 先對一張圖以任意順序進行 DFS 遍歷並進行離開時間戳記 ( 第一次遍歷 ), 再依照時間戳記由大至小在反向圖上進行遍歷, 形成一個森林森林內每一棵子樹的點集都是一個 SCC 由於是兩次遍歷故複雜度是 O(V+E) 以下是虛擬碼: Function Kosaraju (bool[] Visited, Graph G, List[] SCC) count 0 G rev reverse every arc in G // 第一次遍歷 Foreach Vertex v in G If Visited[v] = false Call DFS G start from v with timestamp // 第二次遍歷 For Vertex v with the reverse order of timestamp If Visited[v] = false Call DFS G rev start from v and Add every Vertex into SCC[count] count count + 1 如果我們建一張新的圖, 把所有 SCC 都縮成一個點 arc(scc 1,SCC 2 ) 存在若且唯若原圖中存在至少一個 arc(u,v) 且 u SCC1 v SCC2 這樣的過程稱為縮點, 且 SCC 縮完點後的圖會是一張 DAG 這樣就有一些性質可以利用, 那就直接看例題吧 : 例題 : TIOJ 1451 八卦傳播系統 (08 校內培訓第二次模擬考試 ) 給一張有向圖, 選一些起點使得所有的點都可以被到達, 問最少要選幾個點?

6 Articulation Point Articulation Point, 割點或 AP 無向圖中一個點 u 為 AP 若且唯若存在至少一個點對 (v 1,v 2 ) 且任何始於 v 1 終於 v 2 的 Path 都經過 u 也就是如果把 u 從該連通塊中移除, 該連通塊會變成兩個或以上互不連通的子圖想要找出一張圖中所有 AP 需要先定義 Low 值以及 Dfn Dfn[v] 在一棵 DFS 樹中點 v 的深度 Low[v] = Min(Dfn[v], Low[u], Dfn[w]) 其中 u 表示 v 的所有子節點 w 表示 v 的所有 Back Edge 到達的點所以可以發現一個性質 : 若一個非樹根結點 v, 它至少有一個子結點 u 的 Low[u] Dfn[v], 那麼 v 即為 AP 樹根的話則是若該點的子節點數量以此性質, 即可在 O(V+E) 的時間複雜度內求出所有 AP 下面是遞迴版本的虛擬碼 : Function Find_AP (bool[] Vst, int[] Dfn, int[] Low, List AP) Set Vst[] all false Foreach Vertex v in G If Vst[v] = false Dfn[v] 0 Call DFS(null, v, Vst, Dfn, Low, AP) Function DFS(Vertex PreV, Vertex Now, bool[] Vst, int[] Dfn, int[] Low, List AP) Vst[Now] true Low[now] Dfn[Now] count 0 isap false Foreach Vertex p adjacent to Now If Vst[p] = true And p is not PreV Low[Now] Min(Low[Now], Dfn[p]) If Vst[p] = false count count + 1 Dfn[p] Dfn[Now] + 1 Call DFS(Now, p, Vst, Dfn, Low, AP) If DFn[Now] Low[p] isap true Low[Now] Min(Low[Now], Low[p]) If(Dfn[Now] = 0 And count > 1) Or (isap) Add Now into AP

7 Bi-Connected Component Bi-Connected Component 雙連通元件 (BCC) 我們可以把一個無向圖的邊集分成很多個元件, 讓每個元件符合雙連通性質且為 maximal 雙連通性質是指, 圖上任兩個點之間皆有不只一條路徑連通如果把所有 BCC 縮點, 那麼會得到一棵樹, 並且我們把樹上每個邊叫做 Bridge 橋至於求出 BCC 的作法亦是透過 Low 值以及 Dfn, 在此不贅述例題 : 謠言問題 (TOI 2009 入營考 prob.5) 給定一張無向圖和一個起始點要選擇拔掉一個頂點使得拔掉後該起始點能到達的點數最少請輸出該點編號 ( 相同取編號小 ) 以及拔掉後能到達點數圖論本來就比較多而且雜有空可以去想想額外題單裡面的題目, 相信會很痛苦受益良多有遇到困難也可以互相討論, 相輔相成才是學習的正確方向筆記區

建中資訊科校內培訓講義 – 圖論

建中資訊科校內培訓講義 – 圖論 Chapter 1 緒論 1-1 起源大數學家尤拉 Euler (1707~1783) 由於在 1735 年時右眼失明, 所以便到山明水秀的 Königsberg 去度假, 希望能抒解一下工作壓力, 而故事就從這裡開始 Königsburg 市有一條 Pregel 河流經, 河的中心有兩個小島, 小島與河的兩岸有七座橋相連接當地流傳的一則謎題是, 要如何才能從某一塊土地開始將每一座橋恰好經過一次

Foreword: Graph Theory by CK63rd poao899 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學 它也可以說是研究一維的拓樸學的一門學派 (from

Foreword: Graph Theory by CK63rd poao899 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from