Graph
• กราฟเปนโครงสรางแบบไมตอเนอง(Discrete Structure) ทประกอบดวยสวนของ Vertices และสวนของ Edges ทเชอมตอระหวาง Vertices โดยทเราสามารถแบงกราฟไดเปนหลายชนดตามแตลกษณะการเชอมตอของ Edge
• Edge 2 edge ใดๆ ทเชอมคของ 2 Vertices เดยวกนไมสามารถทบกนได• ถาเราม Vertices จ านวนนบไมถวน (Infinite) เราจะพดไดวาเราม Infinite Graph• ถาเราม Vertices จ านวนจ ากด (Finite) เราจะพดไดวาเราม Finite Graph• ในบทนเราจะศกษาเฉพาะ Finite Graph
1
Types of Graph
2
Types of Graph
3
Types of Graph
4
Types of Graph
5
Types of Graph
6
Summary
7
DirectedDirected multigraph
DirectedSimple directed graph
UndirectedPseudograph
UndirectedMultigraph
UndirectedSimple graph
Loops Allowed?Multiple Edges Allowed?
EdgesType
Exercise
• Directed/Undirected?
• Multiple Edges?
• Loops?
• Type?
8
Exercise
9
Directed/Undirected?
Multiple Edges?
Loops?
Type?
Exercise
10
Directed/Undirected?
Multiple Edges?
Loops?
Type?
Exercise
11
Directed/Undirected?
Multiple Edges?
Loops?
Type?
Exercise
12
Directed/Undirected?
Multiple Edges?
Loops?
Type?
Exercise
13
Directed/Undirected?
Multiple Edges?
Loops?
Type?
Exercise
14
Directed/Undirected?
Multiple Edges?
Loops?
Type?
Graph Model
15
Graph Model
16
Graph Model: Influence
17
Graph Terminology
18
a
b c d
ef g
a b c
de
Special Graph
19
Special Graph
20
Special Graph
21
Special Graph: Bipartite
22
Special Graph: Bipartite
23
Special Graph: Bipartite
24
Application of Graph: LAN
25
Construction of New Graph
26
Exercise
• Number of vertices?
• Number of edges?
• Degree of each vertex?
27
Exercise
28
Number of vertices?
Number of edges?
Degree of each vertex?
Exercise
29
Number of vertices?
Number of edges?
Degree of each vertex?
Exercise
30
Number of vertices?
Number of edges?
Degree of each vertex?
Graph Representation
31
Graph Representation
32
Graph Representation:Adjacency Matrix
33
Graph Representation:Adjacency Matrix
34
Graph Representation:Adjacency Matrix
35
Graph Representation:Adjacency Matrix
36
Graph Representation:Adjacency Matrix
37
Graph Representation:Incident Matrix
38
Graph Representation:Incident Matrix
39
Graph Representation:Incident Matrix
40
Graph Isomorphism
• Greek rootsisos: “equal”
morphe: “form”
41
Graph Isomorphism
42
Graph Isomorphism
43
Graph Isomorphism
44
Graph Isomorphism
45
Graph Isomorphism
46
Graph Isomorphism
47
Graph Isomorphism
48
Connectivity
• หลายๆปญหาสามารถ Model ดวยการเดนทางไปตาม Edge ของกราฟ เชนการสงขอมลใน Data Network หรอปญหาในการวางแผนการเดนทางส าหรบรานสงของ การเกบขยะ การ Diagnostic ในระบบเครอขายคอมพวเตอร เปนตน ซงปญหาเหลานสามารถแกไขไดโดยการ Model ดวยกราฟ
49
Connectivity:Path
50
Connectivity:Path
51
Connectivity:Path
52
Connectivity:Path
53
Path of 2 Vertices
54
Euler and Hamilton Path
• เมอง Konigsberg ประเทศ Prussia ในศตวรรษท18 ไดถกแบงออกเปน 4 สวนดวยแมน า Pregel ทไหลผานตวเมอง ซงกอใหเกดเกาะกลางระหวางแขนงของแมน าตามรป ดงนนชาวเมองจงสรางสะพานขน 7 สะพานเพอเชอมสวนตางๆของเมองเขาดวยกน นกทองเทยวทเดนชมเมองเกดขอสงสยวาจะเปนไปไดไหมทเขาจะเดนชมทกสวนของเมองโดยขามสะพานแตละสะพานเพยงครงเดยว และทายสดกลบมาทจดเดม
55
Euler and Hamilton Path
56
Euler and Hamilton Path
57
Euler and Hamilton Path
58
Euler and Hamilton Path
59
Euler and Hamilton Path
60
Euler and Hamilton Path
61
Euler and Hamilton Path
62
Euler and Hamilton Path
63
Euler and Hamilton Path
64
Euler and Hamilton Path
65
Euler and Hamilton Path
66
Euler and Hamilton Path
67
Shortest-Path Problem
68
Ex: Weighted Graph Modeling an Airline System
69
Ex: Weighted Graph Modeling an Airline System
70
Ex: Weighted Graph Modeling an Airline System
71
Shortest-Path Problem
72
Shortest-Path Problem
73
Dijkstra’s Algorithm
74
Dijkstra’s Algorithm
75
Shortest-Path Problem
• จงหา Shortest Path ระหวาง a และ z
76
77
a (0,a) x x x x x
b (4,a) (4,a) (4,a) x x x
c - - (7,c) (7,c) (7,c) x
d (2,a) (2,a) x x x x
e - (5,d) (5,d) (5,d) x x
z - - - (6,e) (6,e) x
Top Related