Data Structure - Ch4 Graph

Chapter 4   Graph

4.1   Graph相關術語簡介

• Graph專有名詞簡介
• Direction：Directed, Undirected
• Subgraph：subgraph, induced subgraph, spanning subgraph

• Degree：分支度，有向圖又分成 in-degree和out-degree。
• 基本的Graph種類簡介
• Complete graph：有最多非重複邊的圖，所有兩點之間都有一條邊。也就是說無向圖邊個數達 n(n-1)/2，有向圖達n(n-1)。而有此屬性的子圖稱為Clique。
• Connected graph：無向圖任何成對頂點之間皆有路徑存在，而有向圖分成三種連通，Strongly, unilaterally, Weakly。而有此屬性的子圖稱為 Connected component。
• Biconnected graph：為Connected undirected graph但不含cut point。而有此屬性的子圖稱為Biconnected component (注意要是maximal子圖，子圖要盡量大才行)
• Path相關名詞簡介
• length : 一個路徑的邊數稱為length
• Simple path : 路徑上除了起點和終點可以相同之外,其餘頂點均不相同。 
• Cycle : 是一個Simple Path，且起點與終點相同。
• Cut相關名詞簡介
• cut point (articulation point) : 去掉一個點(及其相鄰的邊)使圖不連通
• cut set : 去掉一些邊使圖不連通
• cut edge (bridge) : 去掉一個邊使圖不連通

4.2   Graph Representation

• Adjacency Matrix：n×n的二維矩陣 
• undirected graph必為symmetric matrix
• Operation : 
• 判斷某邊 (i,j) 是否存在：O(1)
• 求頂點 i 的degree : O(n)
• 求圖形邊數 : O(n^2)
• Adjacency List：n 條相鄰串列與一個Size為n的一維矩陣A[1, ..., n]
• Undirected graph的Adjacency list的Node總數 = 2e
• Operation
• 判斷某(i,j)是否存在：O(e)
• 求頂點 i 的degree : O(e)
• 求圖形邊數 : e = 1/2(node總數) : O(n + e)
• [algo.] O(n+e) aggregate analysis : 
• 當圖形的邊很少的情況 : 一個無向圖可以保持連通的最少邊數為 e = n-1。因此 O(n+e) = O(2n-1) ≒ O(n) 
• 當圖形的邊很多的情況 : 一個擁有最多邊數的圖形是Complete Graph，即e = n(n-1)/2。因此 O(n+e) ≒ O(n²) 
• 由上述兩種情況分析，當圖形的邊很多的情況，使用相鄰串列來求圖形的邊數不見得比相鄰矩陣有利。然而，時間複雜度雖然可能會與相鄰矩陣相同,但是相鄰串列在資料結構上多存放了link，需要更多的記憶體空間來執行。 
• Adjacency Matrix適合complete, Adjacency list適合sparse

 4.3   Traverse Graph

• Depth First Search (DFS)
• 利用Stack
• adjacency matrix : O(V^2);   Adjacency list : O(E+V)
• Breadth First Search (BFS)
• 利用Queue  
• adjacency matrix : O(V^2);   Adjacency list : O(E+V)
• 藉由DFS一張directed graph的邊可以分成四類：

1. Tree Edge：樹上的邊。
2. Back Edge：連向祖先的邊，形成環。
3. Forward Edge：連向子孫的邊。
4. Cross Edge：葉、樹之間的邊，可能形成環。

• 藉由 DFS Forest ，undirected graph的邊可以分成兩類：

1. Tree Edge：樹上的邊。
2. Back Edge：連向祖先的邊。（形成環）

• d[x] : discover time, 節點 x 進入遞迴的時刻
• f[x] : finish time, 節點 x 離開遞迴的時刻
• (i, j) is a tree edge or a froward edge : d[i] < d[j] < f[j] < f[i]   
• (i, j) is a back edge : d[j] < d[i] < f[i] < f[j]
• (i, j) is a cross edge : d[j] < f[j] < d[i] < f[i] 

• DFS的應用
• 判斷graph中有無cycle：只要在DFS中有發現back edge則有cycle。
• 找Strongly connected component(SCC)
• DFS(G)，求每個點的finish time
• DFS(GT)，依finish time 遞減進行並輸出所產生的DFS tree
• Computing the Biconnected Components
• Articulation Points：讓一張無向圖維持連通，不可或缺的點
• Biconnected Components：不會產生Articulation Points的connected component
• low(w) = min  { dfn(w) , dfx(x) | x是w(含w)的後代子孫中最多經過一條Backedge所到之點x }
• u is an articulation point iff 
• u is the root of the spanning tree and has two or more children 
• u is not the root and u has a child w s.t. low(w) ≥ dfn(u). 

4.4   AOV network and AOE network

• AOV (Activity On Vertex) Network
• 定義：G = (V,E)有向圖，Vertex表示工作(Activity)，Edge表示工作執行先後次序關係
• 應用：求合理的工作執行順序，Topological sort
• 找出一個無前導的頂點 (Indegree = 0)
• 將此頂點輸出,且刪除此點所Leading-out之edge.
• Repeat直到所有Vertex已輸出,或剩下的點皆有前導存在 
• 若AOV Network有cycle，則無Topological Order。(∵無法決定誰先做!!) 
• 不具cycle的AOV Network，其Topological Order ≥ 1組。 (不一定唯一)

• AOE (Activity On Edge) Network
• 定義：G = (V , E)有向圖，以Edge表示工作 (Activity)，Vertex表示事件 (Event)，Edge上具有加權值，表示工作完成所需的時數。 
• 應用：critical path calculation 
• 臨界路徑(Critical Path)：由於無次序關係之作業可平行執行，因而一個計劃最短完成時間，即由起始點至結束點之最長路徑，稱為Critical Path。此路徑之作業若有耽誤，將導致整個行程的延誤。
• Critical Task (臨界任務)：加速此工作可以加速計畫之完成 (縮短計畫完成時數) 即: 求所有Critical Path的交集工作

• 若要由一AOE Network中找出其Critical Path,需先定義以下名詞: 
• a. 作業最早開始時間(e(i)) : 一作業i可開始進行的最早時間.
  如:下圖之e(a4)=6 e(a5)=4
• b. 事件最早時間(ee(i)) : 達成一事件i的最早時間.(其所有前置作業均完成)
  如:下圖之ee(V5)=7 ee(V6)=7
• c. 作業最晚開始時間(l(i)) : 一作業在不增加整個計劃的完成時間下,所能開始進行的最晚時間(再晚就會使整個計劃的完成時間延後)
  如:下圖之l(a4)=6 l(a5)=6
• d. 事件最晚時間(le(i)) : 達成一事件的最晚時間.
  如:下圖之le(V5)=7 le(V6)=10
• e. 臨界作業:所有滿足e(i)=l(i)的作業邊.
  如:下圖之a1,a4,a7,a8,a10,a11均為臨界作業.
• 臨界路徑的求法:
• a. 根據圖形,先由起始點開始陸續推斷各作業邊之e(i).再根據e(i)求出各頂點(事件)之ee(i).
• b. 由結束點往回推斷各頂點(事件)之le(i).再依據le(i)求出各作業邊之l(i).
• c. 所有e(i)=l(i)之作業所形成的路徑即為臨界路徑. 

4.5   Domination

• Domination相關：專指「支配鄰近元件」這一類的圖論主題，例如 Packing 與 Covering
• Packing：盡量蓋住圖上全部的點、或者邊；不可重複蓋住，或不可相鄰蓋。元件用量越多越好。
• Independent set
• Independent Edge Set (Matching)：無向圖上，選定數邊，互不相鄰，稱作「邊獨立集」。
• Independent Set：無向圖上，選定數點，互不相鄰，稱作「獨立集」。
• Maximum Independent Set [NP-complete]：無向圖上，點數最多的Maximum Independent Set。
• Maximum Independent Set in Tree [P]：當給定的圖是樹，得利用Greedy Method求解。
• Maximum Independent Set in Bipartite Graph [P]：當給定的圖是二分圖，得利用Maximum Cardinality Bipartite Matching求解。
• Covering：蓋住圖上全部的點、或者邊。元件用量越少越好。
• Vertex Cover
• Vertex Cover：一張無向圖上，挑選數個點，碰觸到所有邊，這些點就叫做一個「點覆蓋」
• Dominating Set：無向圖上，選定數點，使所有點與之相鄰，稱作「支配集」。
• Minimum Vertex Cover [NP-complete]：一張圖上點數最少的Vertex Cover。
• Minimum Vertex Cover in Tree [P]：當給定的圖是樹，得利用Greedy演算法，從樹葉往樹根方向選出節點。
• Minimum Vertex Cover in Bipartite Graph [P]：當給定的圖是二分圖，得化作Maximum Cardinality Bipartite Matching解決。

• Clique ⇔ Independent Set ⇔ Vertex Cover
• Clique：一個點集合，這些點兩兩相鄰。
• Independent Set：一個點集合，這些點必不相鄰。
• Vertex Cover：一個點集合，所有邊皆與之相鄰。
• Clique 、 Independent Set 、 Vertex Cover ，三者等價，可以互相轉換。原圖的 Clique ，即是補圖的 Independent Set 。一張圖的 Independent Set 與 Vertex Cover 互補。 

• König's Theorem：二分圖中，最大點覆蓋、最大邊獨立集（最大匹配）大小相等。