第六講：圖形 Graphs
- 定義
- Elementary Operation
- MST
- Shortest path
- Activity networks
edge (邊) E集合
沒箭頭 =>undirected(無方向)
有箭頭 =>directed(有方向)
Definition: A graph G consists of two sets
- a finite, nonempty set of vertices V(G)
- a finite, possible empty set of edges E(G)
- G(V,E) represents a graph
An undirected
graph is one in which the pair of vertices in a edge is unordered, (v0, v1) =
(v1,v0)
A directed graph
is one in which each edge is a directed pair of vertices, <v0, v1> ≠
<v1,v0>
G1:Complete graph G2
G3
V(G1)={0,1,2,3}
E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
V(G2)={0,1,2,3,4,5,6} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}
V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>}
Definition: A complete graph is a graph
that has the maximum number of edges
n for undirected graph with n vertices, the maximum number of edges is
n(n-1)/2
n for directed graph with n vertices, the maximum
number of edges is n(n-1)
number of edges is n(n-1)
Example: G1 is a
complete graph
Adjacent and Incident
n If (v0, v1) is an edge in an undirected graph,
n v0 and v1 are adjacent
n The edge (v0, v1) is incident on vertices v0 and v1
n If <v0, v1> is an edge in a directed graph
n v0 is adjacent to v1, and v1 is adjacent from v0
n The edge <v0, v1> is incident on v0 and v1
Simple Path
n A simple path is a path in which all vertices, except possibly the
first and the last, are distinct
n A cycle is a simple path in which the first and the last vertices
are the same
n In an undirected graph G, two vertices, v0 and v1, are connected if
there is a path in G from v0 to v1
n An undirected graph is connected if, for every pair of distinct
vertices vi, vj, there is a path from vi to vj
Connected Component
n A connected component of an undirected graph is a maximal connected subgraph.
n A tree is a graph that is connected and acyclic.
n A directed graph is strongly connected if there is a directed path
from vi to vj and also from vj to vi.
n A strongly connected component is a maximal subgraph that is
strongly connected.
※從Vi到Vj所經過的edge(點)序列，組成path
Simple path =>簡單路徑(不能重複)
「()」 =>代表無方向 「<>」 =>代表有方向
Simple path =>簡單路徑(不能重複)
「()」 =>代表無方向 「<>」 =>代表有方向
Ex:
V(G1)={0,1,2,3}
V(G1)={0,1,2,3}
考題
下圖中邊之數字代表成本
(2)
利用相鄰串列表示此圖成本
ANS：(1) (2)
考題
DFS(先深後廣)→以點的編號做順序
DFS：V1→V2→V4→V8→V5→V10→V9→V6→V3→V7
考題(交大)
Given the following undireeted graph
(1)
show its adjacency matrix
(2)
show its adjacency list
(3)
show the depth-first spanning
tree. Starting from node 0 and in alphabeticral order.
(4)
Show the breadth-first
spanningtree
ANS：
1.
DFS：0→1→3→2→5→6→4
2.
BFS：0→1→2→3→4→6→5
3.
spanning tree不能有”cycle”
4.
考題(雲科大)
(1) DFS: 1→ 2→ 4→ 3→ 5→ 7→ 8→ 6
(2) BFS: 1→ 2→ 3→ 4→ 5→ 8→ 6→ 7
＊Kruskal’s Algrithm
Step1：挑選最小成本的邊而且不會造成cycle。
Step2：重覆執行step1，直到產生n-1邊(頂點個數為n)
(放圖)
＊ Prime’s Algorithm
假設全部點集合為U
一、設定初始點U→放入集合V中，U=U-{V}
二、重復由U-V中挑選與U有edge相連且edge cost最小的點P將P放入V中，U=U-{P}，直到n個頂點選完。
＊ Sollin’s Algorithm
一、最出與各頂點相鄰小cost 的edge
二、刪除重覆的edge(只保留一個)
三、替每棵數挑選最小cost
edge重復直到只剩一棵樹或無可挑為止
考題
Consider the following graph by performing
minimum spanning tree algorithms by
(1) Kruskal’s
(2)Prim’s(start from vertex a)
(3) Sollin’s
(1)、(2)
(3)
＊ 最短路徑演算法(Dijkstra)
單一起點，distance[i]代表從頂點U到頂點i的最短距離
原理：甲→乙最短距離=Min{Dist(甲,乙),Min[Dist(甲,丙i)+ Dist(丙i,乙)]}
例題：
求甲→乙最短路徑
|
|
Dijkstra
疊代次數
|
挑選的點
|
丙1
|
丙2
|
丙3
|
乙
|
初始
|
─
|
10
|
3
|
8
|
28
|
1
|
丙2
|
10
|
3
|
5
|
28
|
2
|
丙3
|
10
|
3
|
5
|
20
|
3
|
丙1
|
10
|
3
|
5
|
20
|
說明：挑n-2次中間點
1.沒被挑過
2.所有U-i中最短距離
＊ 考題
Q：求V5到其他頂點的最短路徑長度
A：
疊代次數
|
挑選點
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
初始
|
V5
|
無限大
|
無限大
|
無限大
|
1500
|
0
|
250
|
無限大
|
無限大
|
1
|
V6
|
無限大
|
無限大
|
無限大
|
1250
|
0
|
250
|
1150
|
1650
|
2
|
V7
|
無限大
|
無限大
|
無限大
|
1250
|
0
|
250
|
1150
|
1650
|
3
|
V4
|
無限大
|
無限大
|
2450
|
1250
|
0
|
250
|
1150
|
1650
|
4
|
V8
|
3350
|
無限大
|
2450
|
1250
|
0
|
250
|
1150
|
1650
|
5
|
V3
|
3350
|
3250
|
2450
|
1250
|
0
|
250
|
1150
|
1650
|
6
|
V2
|
3350
|
3250
|
2450
|
1250
|
0
|
250
|
1150
|
1650
|
＊ 考題
Q：求下最圖中，點b到g的最短路徑 A：b→g最短路徑為 b→c→a→d→g
疊代次數
|
挑選點
|
a
|
b
|
C
|
d
|
e
|
f
|
g
|
初始
|
B
|
7
|
0
|
2
|
無限大
|
無限大
|
無限大
|
無限大
|
1
|
C
|
6
|
0
|
2
|
無限大
|
7
|
無限大
|
無限大
|
2
|
A
|
6
|
0
|
2
|
10
|
7
|
無限大
|
16
|
3
|
E
|
6
|
0
|
2
|
10
|
7
|
14
|
16
|
4
|
D
|
6
|
0
|
2
|
10
|
7
|
14
|
12
|
5
|
F
|
6
|
0
|
2
|
10
|
7
|
14
|
12
|
如何找尋AOV-network的拓樸排序呢？
步驟1：在AOV-network中任意挑選沒有前行者的頂點
步驟2：輸出此頂點，並將此頂點所連接的邊刪除。重覆步驟1及步驟2，一值到全部的頂點皆輸出為止
例：拓樸排序過程如下，假設有一圖形：
A：V1→V2→V6→V3→V4→V5→V7→V8
＊ 考題(元智)
Q：For the graph below, illustrate each step to determine an order by
topological sorting
(1)輸出1 (2)輸出2 (3)輸出3 (4)輸出5 (5)輸出4
A：12354
//============================================================
＊臨界路徑
(1)AOE網路上的活動是可以並行處理的，而一個計畫所需完成的最短時間，是從起始點到結束點間最長的路徑來算。長度為最長的路徑稱為臨界路徑
(2)臨界路徑可能不止一條
＊AOE-network上活動的時間
(1)最早開始時間(Early Start time)表示一活動最早開始的時間，以ES(i)表示活動ai最早開始時間
(2)最晚開始時間(Lastest Start time)指一活動在不影響整個計畫完成之下，最晚能夠開始進行的時間，以LS(i)表示活動ai最晚開始的時間
例：
AOE：頂點代表事件，邊代表工作，ai代表工作所需的時間
Q：(1)求計畫完成所需最少天數(2)求critical path?(3)每件工作Ai最早/晚開始
A：(1)23天
(2)最長路徑(臨界路徑)
(3)
天數
|
A1
|
A2
|
A3
|
A4
|
A5
|
A6
|
A7
|
A8
|
A9
|
A10
|
A11
|
A12
|
A13
|
A14
|
最早開始
|
0
|
0
|
5
|
6
|
6
|
9
|
12
|
12
|
9
|
9
|
16
|
13
|
16
|
21
|
最晚開始
|
4
|
0
|
9
|
6
|
6
|
9
|
15
|
12
|
15
|
15
|
16
|
19
|
19
|
21
|
12-8
|
12-3
|
23-8
|
16-1
|
21-6
|
21-2
|
23-4
|
紅→可delay
＊考題(台北大學)
Q：(1)求計畫完成所需最少天數?
(2)求critical path?
(3)每件工作ai最早/晚開始
A：(1)23天
(2)最長路徑(臨界路徑)
(3)
天數
|
A0
|
A1
|
A2
|
A3
|
A4
|
A5
|
A6
|
A7
|
A8
|
A9
|
A10
|
A11
|
A12
|
A13
|
最早開始
|
0
|
0
|
5
|
6
|
6
|
12
|
12
|
12
|
15
|
15
|
16
|
19
|
16
|
21
|
最晚開始
|
1
|
0
|
6
|
6
|
12
|
12
|
15
|
12
|
15
|
15
|
16
|
19
|
19
|
21
|
紅→可delay
＊
沒有留言:
張貼留言