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