Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản

Ví dụ:

v

w

v

w

G H

u

H không là đồ thị con cảm sinh của G.

y

y

x

x

43

H ∪{(x,w)} đúng

Loại bỏ đỉnh The deletion of vertices

• Như vậy nếu ký hiệu đồ thị thu được là GS, ta có GS = .

Định nghĩa. Cho G = (V, E) là đồ thị vô hướng. Giả sử S  V. Ta gọi việc loại bỏ tập đỉnh S khỏi đồ thị là việc loại bỏ tất cả các đỉnh trong S cùng các cạnh kề với chúng.

Nếu S={v}, thì để đơn giản ta viết Gv.

v

w

v

w

G GS

u

u

y

x

y

x

44

Giả sử S={x,u} 

Đồ thị con cảm sinh cạnh Edge Induced Subgraph

Định nghĩa. Cho G = (V, E) là đồ thị vô hướng.

Giả sử X  E, X  . Đồ thị con cảm sinh bởi X là đồ thị con nhỏ nhất của G với tập cạnh là X. (ký hiệu bởi ) Đồ thị con H của G được gọi là đồ thị con cảm sinh cạnh (edge- induced subgraph) nếu H= đối với một tập con nào đó X  E.

Ví dụ:

v

w

v

w

G

u

u

y

x

45

Cho X={(u,v),(v,w)} 

Đồ thị con cảm sinh cạnh và cảm sinh đỉnh

Ví dụ. Cho G=(V,E) là đồ thị vô hướng.

Nếu H=, thì có thể suy ra H= được không?

u

No

G H

v

w

v

w



Dễ thấy, G = .

46

Ví dụ trên cho thấy không nhất thiết trùng với G

Đồ thị con bao trùm Spanning Subgraph

Định nghĩa.

Đồ thị con H  G được gọi là đồ thị con bao trùm của G nếu tập đỉnh của H là tập đỉnh của G: V(H) = V(G).

Định nghĩa.

47

Ta viết H = G + {(u,v), (u,w)} hiểu là E(H) = E(G) ∪ {(u,v), (u,w)}, trong đó (u,v), (u,w)E(G).

Hợp của hai đồ thị

• Hợp G1G2 của hai đơn đồ thị G1=(V1, E1) và G2=(V2,E2) là đơn đồ thị (V1V2, E1E2).

a a b c c b



48

e d d f

Hợp của các đồ thị

Nếu S1, S2, S3, S4, S5, S6 là các hình vuông, khi đó Q3 là hợp của các diện của nó: Q3 = S1S2S3S4S5S6

49

Chương 1 CÁC KHÁI NIỆM CƠ BẢN

1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị

50

Đồ thị đẳng cấu Graph Isomorphism

• Định nghĩa:

• f

đồng nhất.

• Có thể tổng quát định nghĩa này cho các loại đồ thị

còn lại.

51

Hai đơn đồ thị vô hướng G1=(V1, E1) và G2=(V2, E2) là đẳng cấu (isomorphic) iff  song ánh f : V1V2 sao cho  a, b  V1, a và b là kề nhau trên G1 iff f(a) và f(b) là kề nhau trên G2. là hàm đặt tên lại các đỉnh để cho hai đồ thị là

Bất biến đối với đẳng cấu

Điều kiện cần nhưng không phải là đủ để G1=(V1, E1) là đẳng cấu với G2=(V2, E2):

– Ta phải có |V1|=|V2|, và |E1|=|E2|. – Số lượng đỉnh bậc k ở hai đồ thị là như nhau.

52

Ví dụ đẳng cấu

• Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt.

d b

b a a d c

e

f e c

53

f

Có đẳng cấu không?

• Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy

rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt.

• Cùng số lượng đỉnh a

• Cùng số

lượng cạnh

b

d

e c

54

• Khác số lượng đỉnh bậc 2 (1 < >3)

Hai đồ thị sau là đẳng cấu với nhau

A’ A

B E E’ B’

D’

C D

55

C’

Hai đơn đồ thị G1 và G2 sau là đẳng cấu qua phép đẳng cấu f: a x, bu, cz, dv, ey:

56

Ví dụ:

• Hai đồ thị G1 và G2 sau đều có 5 đỉnh và 6 cạnh nhưng không đẳng cấu vì trong G1 có một đỉnh bậc 4 mà trong G2 không có đỉnh bậc 4 nào.

57

Ví dụ:

• Hai đồ thị G1 và G2 đều có 7 đỉnh, 10 cạnh, cùng có một đỉnh bậc 4, bốn đỉnh bậc 3 và hai đỉnh bậc 2. Tuy nhiên G1 và G2 là không đẳng cấu vì hai đỉnh bậc 2 của G1 (a và d) là không kề nhau, trong khi hai đỉnh bậc 2 của G2 (y và z) là kề nhau.

58

Ví dụ:

• Hãy xác định xem hai đồ thị sau có đẳng cấu hay không?

59

Các đồ thị G và G’ sau có đẳng cấu với nhau không?

60

Chương 1 CÁC KHÁI NIỆM CƠ BẢN

1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị

61

Đường đi, Chu trình

• Định nghĩa. Đường đi P độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị G=(V,E) là dãy

P:

x0, x1, . . . , xn-1, xn

• •

trong đó u = x0, v = xn, (xi, xi+1) E, i = 0, 1, 2, ... , n-

1.

Đường đi nói trên còn có thể biểu diễn dưới dạng dãy

•

các cạnh:

(x0, x1), (x1, x2), . . . , (xn-1, xn).

Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối

• •

62

của đường đi.

Đường đi, Chu trình

• Đường đi gọi là đường đi sơ cấp nếu không có đỉnh

nào bị lặp lại trên nó.

• Đường đi gọi

là đường đi đơn giản nếu không có

cạnh nào bị lặp lại trên nó.

• Nếu có đường đi từ u đến v thì ta nói đỉnh v đạt đến được từ đỉnh u. Ta quan niệm rằng một đỉnh v luôn đạt đến được từ chính nó.

63

Đường đi (Path)

5

d

c

b

a

e

3

2

4

1

Ví dụ: 5, 2, 3, 4 hoặc 5, c, 2, b, 3, e, 4. Không có đỉnh lặp nên là đường đi đơn giản

5

d

c

b

a

e

3

2

4

1

Ví dụ: hoặc 1, a, 2, c, 5, d, 3, e, 4

64

1, 2, 5, 3, 4 • Là đường đi đơn giản

Ví dụ (cont.)

• P1=(1,b,2,h,3) là đường

1

đi đơn

b a

4 P1 2 3

• P2=(4,c,5,e,2,g,6,f,5,d,1) nhưng

đường

đi

h d P2 c e

là không là đường đi đơn

5 g

f

65

6

Ví dụ (cont.)

là

• P1=(1, b, 2, h, 3)

1

đường đi đơn

b a

4 P1 2 3

đường

đi

h d P2 c e

5 g

• P2=(4,c,5,e,2,g,6,f,5,d,1) nhưng là không là đường đi sơ cấp

f

66

6

Chu trình

• Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là

u = v) được gọi là chu trình.

• Chu trình được gọi là sơ cấp nếu như ngoại trừ đỉnh đầu trùng với đỉnh cuối, không có đỉnh nào bị lặp lại.

67

Chu trình (Cycle)

2

a

b

e

1

Chu trình

3

d

c

1, 2, 3, 1. (hay 1, a, 2, b, 3, e) • Chu trình đơn

4

2

a

b

Chu trình: (1, 2, 3, 4, 1) hay

e

1

3

d

c

1, a, 2, b, 3, c, 4, d, 1 • Chu trình đơn

4

68

Ví dụ: Chu trình trên đồ thị vô hướng

• C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn • C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không

là chu trình đơn

V

a b

d C2 U X Z

e h C1 c

W g

f

69

Y

Ví dụ: Chu trình trên đồ thị có hướng

• C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn • C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không

là chu trình đơn

V

a b

U X Z

d C2

e c

W h C1 g

f

70

Y

Chương 1 CÁC KHÁI NIỆM CƠ BẢN

1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị

71

Tính liên thông (Connectedness)

• Đồ thị vô hướng được gọi là liên thông nếu luôn tìm

được đường đi nối hai đỉnh bất kỳ của nó.

• Ví dụ

i

f

G2

G1

• G1 và G2 là các đồ thị liên thông • Đồ thị G bao gồm G1 và G2 không là đồ thị liên thông

72

j k

Tính liên thông (Connectedness)

• Mệnh đề: Luôn tìm được đường đi đơn nối hai đỉnh

bất kỳ của đồ thị vô hướng liên thông.

• Chứng minh.

Theo định nghĩa, luôn tìm được đường đi nối hai đỉnh bất kỳ của đồ thị liên thông. Gọi P là đường đi ngắn nhất nối hai đỉnh u và v. Rõ ràng P phải là đường đi đơn.

73

Tính liên thông (Connectedness)

• Thành phần liên thông (Connected component): Đồ thị con liên thông cực đại của đồ thị vô hướng G được gọi là thành phần liên thông của nó.

• Ví dụ: Đồ thị G có 3 thành phần liên thông G1, G2, G3

b c i

f a

G2

G3

j k d e

G1

74

g

Thành phần liên thông

V(a)={a,b,c,d,e,g};

b c i

f a

G2 ≡G(f)

G3 ≡G(i)

G1≡G(a)

j k d e

Gỉa sử vV. Gọi

• V(v) – tập các đỉnh của đồ thị đạt đến được từ v, • E(v) – tập các cạnh có ít nhất một đầu mút trong V(v).

Khi đó G(v) = (V(v), E(v)) là đồ thị liên thông và được gọi là thành phần liên thông sinh bởi đỉnh v. Dễ thấy G(v) là thành phần liên thông sinh bởi mọi đỉnh uV(v).

75

g

Ví dụ

Ví dụ: Cho G là đồ thị vô hướng n  2 đỉnh. Biết rằng

d(G) = min{deg(v): v V}  (n-1)/2.

Chứng minh rằng G liên thông.

Chứng minh.

Phản chứng. Giả sử G không liên thông, khi đó do

d(G)  (n-1)/2,

nên mỗi thành phần liên thông phải chứa ít ra (n-1)/2+1 = (n+1)/2 đỉnh. Suy ra đồ thị có ít ra (n+1) đỉnh?!

76

Đỉnh rẽ nhánh và cầu (Connectedness) • Đỉnh rẽ nhánh (cut vertex): là đỉnh mà việc loại bỏ nó làm tăng

số thành phần liên thông của đồ thị

• Cầu (bridge): Cạnh mà việc loại bỏ nó làm tăng số thành phần

liên thông của đồ thị .

• Ví dụ:

e là đỉnh rẽ nhánh

b c

a

Cạnh (e,g) là cầu

d e

G

77

g

Ví dụ

Mệnh đề. Cạnh e của đồ thị liên thông G là cầu nếu e không thuộc

bất cứ chu trình nào trên G.

Chứng minh

() Cho e là cầu của G. Giả sử e = (u,v), và giả sử ngược lại là e nằm trên chu trình

C：u, v, w, …, x, u.

Khi đó

C  e：v, w, …, x, u

78

là đường đi từ u đến v trên đồ thị G  e. Ta sẽ chứng minh: G  e là liên thông. (Điều đó sẽ mâu thuẫn với giả thiết e là cầu)

Chứng minh mệnh đề (cont)

Thực vậy, giả sử u1, v1  V(Ge)=V(G)

Do G là liên thông, nên  đường đi P: u1v1 trên G. Nếu e  P, thì P cũng là đường đi trên Ge

  đường đi u1v1 trên Ge

Nếu e  P, thì

(PC)e là đường đi u1v1 trên Ge (xem hình)

Vậy luôn tìm được đường đi u1v1 trên Ge

C

Vậy Ge là liên thông.



P

79

u v u1 v1

Chứng minh mệnh đề (cont)

() Giả sử e=(u,v) là cạnh không nằm trên bất cứ chu trình

nào của G. Khi đó Ge không chứa đường đi uv. Trái lại, nếu P là đường đi uv trên Ge, thì P{(u,v)} là chu trình trên G chứa e ?!

80

k-liên thông (k-Connectivity)

Không phải tất cả các đồ thị liên thông là đồng giá trị! Q: Hãy đánh giá xem đồ thị nào dưới đây là sơ đồ nối

mạng máy tính có giá trị hơn:

1) G1

2) G2

3) G3

4) G4

81

k-Connectivity

A: Ta muốn mạng máy tính vẫn là thông suốt ngay cả

khi có một máy bị hỏng:

1) 2nd best. Vẫn có một điểm

yếu— “cut vertex” 2) 3rd best. Thông suốt

nhưng mỗi máy đều là điểm “yếu”

3) Tồi nhất!

Không thông suốt

4) Tốt nhất! Mạng chỉ không

82

thông suốt nếu hỏng 2 máy

k-Connectivity

Mạng

là tốt nhất bởi vì nó mất tính liên thông chỉ khi có 2 đỉnh bị loại bỏ. Nói cách khác mạng là 2-liên thông (song liên thông).

Định nghĩa. Đơn đồ thị vô hướng liên thông với n3 đỉnh được gọi là song liên thông nếu nó vẫn là liên thông sau khi loại bỏ một đỉnh bất kỳ. Q: Tại sao lại có điều kiện với số đỉnh? A: Tránh trường hợp đồ thị chỉ có 1 cạnh.

83

k-liên thông

Tổng quát: Định nghĩa. Đơn đồ thị vô hướng được gọi là k-liên thông nếu như muốn phá vỡ tính liên thông của nó ta phải loại bỏ ít nhất k đỉnh.

Ví dụ: • Q3 là 3-liên thông • Q4 là ?-liên thông

84

Q3 Q4

Tính liên thông của Đồ thị có hướng

• Đồ thị có hướng được gọi là liên thông mạnh (strongly connected) nếu như luôn tìm được đường đi nối hai đỉnh bất kỳ của nó.

• Đồ thị có hướng được gọi

là liên thông yếu (weakly connected ) nếu như đồ thị vô hướng thu được từ nó bởi việc bỏ qua hướng của tất cả các cạnh của nó là đồ thị vô hướng liên thông.

• Dễ thấy là nếu G là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều ngược lại không luôn đúng.

85

Ví dụ

b c b c

f f a a

• Đồ thị liên thông mạnh Đồ thị liên thông yếu

d e d e

b c

f a

86

d e

Chương 1 CÁC KHÁI NIỆM CƠ BẢN

1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị

87

Một số dạng đơn đồ thị vô hướng đặc biệt

• Đồ thị đầy đủ (Complete graphs) Kn • Chu trình (Cycles) Cn • Bánh xe (Wheels) Wn • n-Cubes Qn • Đồ thị hai phía (Bipartite graphs) • Đồ thị hai phía đầy đủ (Complete bipartite graphs) Km,n • Đồ thị chính qui • Cây và rừng • Đồ thị phẳng

88

Đồ thị đầy đủ Complete Graphs

• Với nN, đồ thị đầy đủ n đỉnh, Kn, là đơn đồ thị vô hướng với n đỉnh trong đó giữa hai đỉnh bất kỳ luôn có cạnh nối: u,vV: uv  (u,v)E.

K4 K3 K1 K2

n

 1

)1

 i

nn  ( 2

 1

i

K6 K5

89

Để ý là Kn có cạnh.

Đồ thị đầy đủ Complete Graphs

K25

90

Đồ thị đầy đủ Complete Graphs

91

K42

Chu trình (Cycles)

• Giả sử n3. Chu trình n đỉnh, Cn, là đơn đồ thị vô hướng

với V={v1,v2,… ,vn} và E={(v1,v2),(v2,v3),…,(vn1,vn),(vn,v1)}.

Có bao nhiêu cạnh trong Cn?

92

C3 C4 C5 C6 C8 C7

Bánh xe (Wheels)

• Với n3, bánh xe Wn, là đơn đồ thị vô hướng thu được bằng cách bổ sung vào chu trình Cn một đỉnh vhub và n cạnh nối

{(vhub,v1), (vhub,v2),…,(vhub,vn)}.

Có bao nhiêu cạnh trong Wn?

93

W3 W4 W5 W6 W8 W7

Siêu cúp (n-cubes /hypercubes)

• Với nN, siêu cúp Qn là đơn đồ thị vô hướng gồm hai bản sao của Qn-1 trong đó các đỉnh tương ứng được nối với nhau. Q0 gồm duy nhất 1 đỉnh.

Q0

Q4 Q1 Q2 Q3

94

Số đỉnh: 2n. Số cạnh: ?

Siêu cúp (n-cubes /hypercubes)

• Với nN, siêu cúp Qn là đơn đồ thị vô hướng gồm hai bản sao của Qn-1 trong đó các đỉnh tương ứng được nối với nhau. Q0 gồm duy nhất 1 đỉnh.

Q1 Q0

Q2 Q3 Q4

95

Số đỉnh: 2n. Số cạnh: ?

Siêu cúp Q4

96

Siêu cúp (n-cubes /hypercubes)

• Với nN, siêu cúp Qn có thể định nghĩa đệ qui như sau:

và E={e1,…,eb}, thì Qn+1=(V{v1´,…,va´}, E{e1´,…,eb´}{(v1,v1´),(v2,v2´),…,(va,va´)})

và Q’

• Nghĩa là siêu cúp Qn+1 thu được từ hai siêu cúp Qn n bằng việc nối các cặp đỉnh tương ứng.

97

– Q0={{v0},} (một đỉnh và không có cạnh) – Với mọi nN, nếu Qn=(V,E), trong đó V={v1,…,va}

Đồ thị hai phía (Bipartite Graphs)

• Định nghĩa. Đồ thị G=(V,E) là hai phía nếu và chỉ nếu

V = V1 V2 với V1∩V2= và eE: v1V1, v2V2: e=(v1,v2).

• Bằng lời: Có thể phân hoạch tập đỉnh thành hai tập sao cho mỗi cạnh nối hai đỉnh thuộc hai tập khác nhau.

Định nghĩa này là chung cho cả đơn lẫn đa đồ thị vô hướng, có hướng.

98

V2 V1

Đồ thị hai phía đầy đủ

(Complete Bipartite Graphs)

• Với m, nN, đồ thị hai phía đầy đủ Km,n là đồ thị hai phía

trong đó |V1| = m, |V2| = n, và E = {(v1,v2)|v1V1 và v2V2}.

• Km,n có m đỉnh ở tập bên trái, n đỉnh ở tập bên phải, và mỗi đỉnh ở phần bên trái được nối với mỗi đỉnh ở phần bên phải.

Km,n có _____ đỉnh và _____ cạnh.

99

K4,3

Đồ thị chính qui r-regular graph

• Định nghĩa. Đồ thị G được gọi là đồ thị chính qui bậc r

nếu tất cả các đỉnh của nó có bậc bằng r.

• Ví dụ:

Đồ thị chính qui bậc 0

Đồ thị chính qui bậc 1

Đồ thị chính qui bậc 2

Đồ thị chính qui bậc 3

100

Đồ thị Platonic

• Xét các khối đa diện Platonic trong không gian 3-chiều

Tetrahedron Tứ diện

Hexahedron (cube) Lục diện

Octahedron Bát diện

Dodecahedron Thập nhị diện

Icosahedron Thập bát diện

101

Đồ thị Platonic

• Đồ thị platonic thu được bằng việc chiếu các khối đa diện tương

ứng xuống mặt phẳng

Tetrahedron

Hexahedron (cube)

Octahedron

Dodecahedron

Icosahedron

102

Bài tập

• Một đồ thị bánh xe Wn có 36 cạnh. Tìm số đỉnh của đồ

thị?

• Cho đồ thị G= (V,E) có 10 đỉnh, mỗi đỉnh có bậc bằng 6.

Tìm số cạnh của đồ thị?

• Đồ thị nào có kích thước ma trận liên kề bằng ma trận

liên thuộc.(vẽ hình minh họa)

103

Bài tập

• Đồ thị vòng có phải là đồ thị phân đôi không? Giải thích,

vẽ hình minh họa?

104

• Cho biết tên gọi của đồ thị?

105

Cây và rừng (Tree and Forest)

• Định nghĩa. Ta gọi cây là đồ thị vô hướng liên thông không có chu

trình. Đồ thị không có chu trình được gọi là rừng.

• Như vậy, rừng là đồ thị mà mỗi thành phần liên thông của nó là

T1

T2

T3

một cây.

Rừng F gồm 3 cây T1, T2,, T3

106

VÍ DỤ

G1, G2 là cây

107

G3, G4 không là cây

Các tính chất cơ bản của cây

• Định lý. Giả sử T=(V,E) là đồ thị vô hướng n đỉnh. Khi

đó các mệnh đề sau đây là tương đương:

(1) T là cây; (2) T không chứa chu trình và có n-1 cạnh; (3) T liên thông và có n-1 cạnh; (4) T liên thông và mỗi cạnh của nó đều là cầu; (5) Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một

đường đi đơn;

(6) T không chứa chu trình nhưng hễ cứ thêm vào nó một

108

cạnh ta thu được đúng một chu trình.

Đồ thị phẳng

(Planar Graphs)

• Định nghĩa. Đồ thị vô hướng G được gọi là đồ thị phẳng nếu như có thể vẽ nó trên mặt phẳng sao cho không có hai cạnh nào cắt nhau ngoài ở đỉnh.

• Ví dụ: K4 là đồ thị phẳng?

K4 là đồ thị phẳng!

109

Các đồ thị Platonic đều phẳng

• Tất cả 5 đồ thị Platonic đều là đồ thị phẳng

110

3-Cube là đồ thị phẳng

111

4-Cube có là đồ thị phẳng không?

Có vẻ phẳng, nhưng chứng minh bằng cách nào?

112

K3,3 và K5 không là đồ thị phẳng

• Đồ thị K3,3 và K5 không là đồ thị phẳng

• Mọi cách vẽ K3,3 đều phải có ít nhất một giao điểm ngoài

đỉnh (gọi là vết cắt).

113

Khảo sát đồ thị phẳng

• Để khảo sát đồ thị phẳng ta có thể chỉ hạn chế ở đơn đồ

thị. Bởi vì:

• Nếu đồ thị phẳng có cạnh lặp hay là khuyên (loop) – Chập các cạnh lặp lại thành một cạnh đơn. – Loại bỏ tất cả các khuyên.

• Vẽ đơn đồ thị thu được sao cho không có vết cắt. • Sau đó chèn vào các khuyên và cạnh lặp.

114

Khảo sát đồ thị phẳng

• Loại bỏ khuyên và cạnh lặp: • Ví dụ: Xét đồ thị phẳng

115

• Vẽ đơn đồ thị thu được: • Bổ sung khuyên và cạnh lặp:

Công thức Euler Euler's Formula

• Nếu G là đồ thị phẳng, thì mọi cách vẽ phẳng G đều chia mặt phẳng ra thành các vùng mà ta sẽ gọi là các diện (faces).

• Một trong các diện này là không bị chặn và nó được gọi

là diện vô hạn.

• Giả sử f là một diện nào đó, ta gọi bậc của f , ký hiệu bởi deg(f ), là số cạnh trên đường đi vòng quanh biên của diện f.

• Nếu tất cả các diện đều có cùng bậc (chẳng hạn, g), thì G

được gọi là diện chính quy bậc g.

116

Công thức Euler Euler's Formula

• Ví dụ: Đồ thị G sau đây có 4 diện, trong đó f4 là diện vô hạn.

• Dễ thấy là trong đồ thị trên:

117

deg(f1)=3, deg(f2)=4, deg(f3)=9, deg(f4)=8. • Nhận thấy là tổng bậc của các diện là bằng 2 lần số cạnh của đồ thị, bởi vì mỗi cạnh là biên chung của hai diện (ví dụ, bg, cd, và cf) hoặc xuất hiện hai lần khi đi vòng quanh một diện (ví dụ, các cạnh ab và gh).

Công thức Euler

• Công thức Euler cho biết mối liên hệ giữa số đỉnh, số cạnh và số theo thứ tự là số đỉnh, cạnh

diện của đồ thị phẳng. Nếu n, m, và f và diện của đồ thị phẳng liên thông thì ta có n – m+f = 2.

• Công thức Euler khẳng định rằng mọi cách vẽ phẳng của đồ thị phẳng liên thông đều cho cùng một số diện như nhau là 2 – n + m.

118

• Định lý (Euler's Formula) Cho G là đồ thị liên thông phẳng, và n, m và f lần lượt là số đỉnh, số cạnh và diện của đồ thị phẳng. Khi đó n – m + f = 2.

Chứng minh công thức Euler

• Chứng minh. Qui nạp theo số cạnh m. • Cơ sở qui nạp: Khi m=0, ta có n=1 và f=1. Do đó n–m+f = 2. • Bước qui nạp: Giả sử khẳng định đúng cho mọi đồ thị phẳng liên thông có ít hơn m cạnh, trong đó m  1, và giả sử rằng G có m cạnh. Nếu G là cây, thì n=m+1 và f=1 và do đó công thức là đúng. Mặt khác, nếu G không là cây thì gọi e là một cạnh trên chu trình của G và xét G\e. Đồ thị phẳng liên thông G\e có n đỉnh, m-1 cạnh, và f – 1 diện, do đó theo giả thiết qui nạp

n – (m – 1) + (f – 1) = 2

từ đó suy ra

n – m + f = 2.

119

• Ta sẽ phát biểu một loạt hệ quả thú vị suy ra từ công thức Euler.

Hệ quả

• Hệ quả 1. Giả sử G là đơn đồ thị phẳng liên thông với n đỉnh,

trong đó n ≥ 3 và m cạnh. Khi đó m ≤ 3n – 6.

• Chứng minh. Đối với đồ thị G có f diện, từ bổ đề về các cái bắt tay, suy ra 2m = (tổng bậc của các diện) ≥ 3f (bởi vì bậc của mỗi diện của đơn đồ thị ít nhất là 3), do đó f ≤ 2/3 m.

• Kết hợp với công thức Euler n – m + f = 2

ta thu được

m – n + 2 ≤ 2/3 m.

Từ đó suy ra

120

m ≤ 3n – 6.

K5 không là đồ thị phẳng

• Hệ quả 2. K5 không là đồ thị phẳng. • Chứng minh. Giả sử K5 là đồ thị phẳng. Do K5 có 5

đỉnh và 10 cạnh, nên từ bổ đề 1 suy ra

10 (3 × 5) – 6 = 9.

Điều phi lý này đã chứng minh K5 không là đồ thị phẳng. • Chú ý: K3,3 có 6 đỉnh và 9 cạnh, và bất đẳng thức 9 ≤ (3 × 6) – 6 = 12 là đúng. Sự kiện này cho thấy là ta không thể sử dụng hệ quả 1 để chỉ ra K3,3 không là phẳng.

• Ta sẽ phải sử dụng hệ quả khác.

121

Hệ quả 3

• Hệ quả 3. Giả sử G là đơn đồ thị phẳng liên thông với n đỉnh và m

cạnh và không chứa tam giác. Khi đó m ≤ 2n – 4.

• Chứng minh. Giả sử G có f diện, khi đó từ bổ đề về các cái bắt tay đối với đồ thị phẳng ta có 2m ≥ 4 f (bởi vì bậc của diện của đơn đồ thị không chứa tam giác ít nhất là 4), vì thế f ≤ 1/2 m.

• Theo công thức Euler ta có

n – m + f = 2 hay m – n + 2 = f.

Từ đó ta thu được

m – n + 2 ≤ m/2.

Từ đó suy ra

122

m ≤ 2n – 4.

K3,3 không là đồ thị phẳng

• Hệ quả 4. K3,3 không là đồ thị phẳng. • Chứng minh. Giả sử K3,3 là phẳng. Do K3,3 có 6 đỉnh, 9 cạnh và không chứa tam giác, nên từ hệ quả 3 suy ra

9 ≤ (2×6) – 4 = 8.

Điều phi lý này đã chứng tỏ K3,3 không là đồ thị phẳng.

• Kết quả trên đã giải quyết bài toán đố hóc búa về: ba căn

nhà và 3 nguồn cung cấp năng lượng

123

Bài toán xây dựng hệ thống cung cấp năng lượng

124

• Tìm cách xây dựng hệ thống đường ống nối 3 nguồn cung cấp khí ga, nước và điện cho 3 ngôi nhà sao cho chúng không cắt nhau:

Chứng minh Q4 không phẳng

•

Ta chứng minh Q4 không là đồ thị phẳng. Trước hết ta tính số đỉnh và cạnh: • |V | = 16 (gấp đôi số đỉnh của 3-cube) |E | = 32 (hai lần số cạnh của 3-cube cộng với số đỉnh của 3-cube) Bây giờ, giả sử 4-cube là đồ thị phẳng, khi đó theo hệ quả 3 ta phải có:

32 = m  2n – 4 = 2*16 – 4 = 28 ?!

Tổng quát: Qn không là đồ thị phẳng khi n  4.

125

Nhận biết đồ thị phẳng

• Các hệ quả 1 và 3 là các điều kiện cần để đồ thị là phẳng và vì thế chỉ có thể sử dụng để chỉ ra một đồ thị không phải là phẳng. Có nhiều đồ thị thoả mãn các hệ quả này nhưng không phải là phẳng. Vì thế ta cần đưa ra tiêu chuẩn nhận biết đồ thị phẳng. Ta bắt đầu bằng một số nhận xét

– Không phải mọi đồ thị là phẳng. – Ví dụ, ta đã chứng minh K5 và K3,3 không phẳng.

• Nhận xét 1

– Nếu G là đồ thị phẳng thì mọi đồ thị con của nó cũng là phẳng; – Ta thường sử dụng dạng phủ định – Nhận xét 2a: Nếu G chứa đồ thị không phẳng như đồ thị con thì G không là

đồ thị phẳng

126

• Nhận xét 2

• Ví dụ: Đồ thị G1 chứa K5 như là đồ thị con, còn đồ thị G2 chứa K3,3 như là đồ thị con, nên G1 và G2 không là đồ thị phẳng:

G1

G2

127

Nhận xét

– Nếu G là phẳng thì mọi cách chia cạnh của G đều là đồ thị phẳng. – Nhận xét 3a: Nếu G thu được bằng cách chia cạnh của một đồ thị không

phẳng thì nó không là đồ thị phẳng

• Nhận xét 3.

• Ví dụ: Đồ thị G3 thu được từ K5 còn G4 thu được từ K3,3

G3 :

128

G4: • Từ nhận xét (2a) và (3a) ta suy ra nếu đồ thị G chứa đồ thị con thu được bằng phép chia cạnh của K5 hoặc K3,3 thì G không phẳng..

Nhận biết đồ thị phẳng

• Định nghĩa. Ta gọi phép chia cạnh (u,v) của đồ thị G là việc thêm vào G một đỉnh w, loại bỏ cạnh (u,v) và thêm vào hai cạnh (u,w) và (w,v).

• Định nghĩa. Hai đồ thị G và H được gọi

là đồng phôi (homeomorphic) nếu ta có thể thu được chúng từ đồ thị nào đó bởi các phép chia cạnh.

•

đồng phôi với

đồng phôi với

129

• Ví dụ:

Định lý Kuratowski

• Định lý Kuratowski (1930). Đồ thị G là đồ thị phẳng khi và chỉ

khi nó không chứa đồ thị con đồng phôi với K5 hoặc K3, 3.

• Ví dụ: Đồ thị Petersen không là đồ thị phẳng bởi vì nó là đồng

phôi với đồ thị K5

K5

Đồ thị Petersen

K. Kuratowski 1896-1980 Poland

130

Đồ thị Euler

• Định nghĩa • Nhận biết đồ thị Euler

131

Bài toán về 7 cái cầu ở Königsberg

• Hiện nay là Kaliningrad (thuộc Nga) • Sông Pregel

A

D B

C

Leonhard Euler

1707-1783

132

Bài toán về 7 cái cầu ở Königsberg

• Tồn tại hay chăng cách đi qua tất cả 7 cái cầu mỗi cái

đúng một lần rồi lại quay về vị trí xuất phát?

A A

D

D B B

C

C

Sơ đồ 7 cái cầu

Đa đồ thị vô hướng tương ứng 133

Đường đi và chu trình Euler

• Định nghĩa: Xét 1 đồ thị liên thông G.  Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Lúc này G còn được gọi là một đường đi Euler.  Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Lúc này G còn được gọi là một chu trình Euler.

 Một đồ thị chứa chu trình Euler được gọi là đồ thị Euler.

134

Đường đi và chu trình Euler

• Định lý 2.1: (Định lý Euler 1) • Cho 1 đồ thị vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn.

A

B

E

Chu trình Euler: DEABCEBD

C

D

135

Đường đi và chu trình Euler

• Thuật toán tìm chu trình Euler của đồ thị G(V, E)

Kết quả sẽ cho ra C là một chu trình Euler bao gồm thứ tự các cạnh của chu trình.

136

137

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 1 1 0 0 0

3

2

4

6

5

1 2 3 4 5 6

1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0

C = Ø, v = 1

138

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 1 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0

C = 1,2

139

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 1 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0

C = 1,2,3

140

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 0 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0

C = 1,2,3,1

E  Ø

141

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 0 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0

C = 1,2,4, ,3,1

142

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 0 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0

C = 1,2,4,3, ,3,1

143

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 0 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0

C = 1,2,4,3,6, ,3,1

144

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 0 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

C = 1,2,4,3,6,5, ,3,1

145

Đường đi và chu trình Euler

1

1 2 3 4 5 6

0 0 0 0 0 0

3

2

4

6

5

1 2 3 4 5 6

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

C = 1,2,4,3,6,5,2,3,1

E = Ø

146

Ví dụ: Tìm đường đi và chu trình Euler

• G1: Đồ thị Euler • G3: Đồ thị nửa Euler • G2: kho6nt nửa Euler

147

Ví dụ: Tìm đường đi và chu trình Euler

• H2: Đồ thị Euler • H3: Đồ thị nửa Euler • H1:Không nửa Euler

148

Đường đi và chu trình Euler

• Định lý 2.2 (Định lý Euler 2):

Cho một đồ thi vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu G có đúng 2 đỉnh bậc lẻ.

A

B

E

Đường đi Euler: DEABECBDC, DEABCEBDC

C

D

149

Tìm chu trình Euler

150

Đường đi và chu trình Euler

• Định lý 2.3 (Định lý Euler 3):

Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có chu trình Euler nếu và chỉ nếu G cân bằng.

A

B

E

Chu trình Euler: DEABCEBD

C

D

151

Đường đi và chu trình Euler

• Định lý 2.4 (Định lý Euler 4):

Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu trong G có 2 đỉnh a, b thỏa:

dout(a) = din(a) + 1 din(b) = dout(b) + 1

mọi đỉnh còn lại đều cân bằng và đường Euler phải bắt đầu tại a và kết thúc tại b.

152

Đường đi và chu trình Euler

A

B

E

Đường đi Euler: DEABCEBDC, DEBCEABDC

C

D

153

Định nghĩa:

Một đồ thị liên thông (liên thông yếu đối với đồ thị có hướng) có chứa một đường đi Euler được gọi là đồ thị nửa Euler. • Hệ quả: Đồ thị liên thông G là nửa Euler khi và chỉ khi

có đúng hai đỉnh bậc lẻ trong G.

154

Bài tập:

• Với giá trị nào của n các đồ thị sau đây có chu trình Euler

?

• Với giá trị nào của m và n các đồ thị phân đôi đầy đủ

Km,n có:

• a) chu trình Euler ? b) đường đi Euler ?

155

Đồ thị Hamilton

• Định nghĩa • Nhận biết đồ thị Hamilton

156

Đường đi và chu trình Hamilton (1805- 1865)

• Định nghĩa:

Xét 1 đồ thị liên thông G có hơn 1 đỉnh

 Một đường đi Hamilton của G là một đường đi sơ cấp

qua tất cả các đỉnh của G.

 Một chu trình Hamilton của G là một chu trình sơ cấp qua tất cả các đỉnh của G. Một đồ thị chứa chu trình Hamilton được gọi là đồ thị Hamilton.

157

Đồ thị Hamilton

• Đồ thị có hai đỉnh bậc 1 không là đồ thị Hamilton

• Dễ thấy đồ thị trên là đồ thị nửa Hamilton

158

Trò chơi vòng quanh thế giới

(Round-the-World Puzzle)

Sir William Rowan Hamilton 1805-1865

• Bạn có thể chỉ ra cách đi qua tất cả các đỉnh của dodecahedron (thập nhị diện) mỗi đỉnh đúng một lần?`

Hộp trò chơi Dodecahedron puzzle

159

Đồ thị tương ứng

Ví dụ

• Đồ thị Hamilton

160

Ví dụ

Ví dụ: CM Qn (n  3) là đồ thị Hamilton. Chứng minh. Qui nạp theo n.

Cơ sở: n=3 đúng Chuyển qui nạp: Giả sử Qn1 là hamilton. Xét Qn:

x

x’

x’

x

y

y’

y

y’

3 - cube

(n 1)-cube

(n 1)-cube

161

Đường đi và chu trình Hamilton

A

Đường đi Hamilton: ABECD

E

B

D

C

A

E

B

Đường đi Hamilton: BAECD

D

C

162

Đường đi và chu trình Hamilton

A

B

Chu trình Hamilton: ABCDA

D

C

A

B

Chu trình Hamilton: ACBDA

D

C

163

Đường đi và chu trình Hamilton

• Qui tắc tìm chu trình Hamilton 1. Nếu tồn tại 1 đỉnh của G có bậc  1 thì G không có chu

trình Hamilton.

2. Nếu đỉnh x có bậc 2 thì cả 2 cạnh tới x đều phải thuộc

chu trình Hamilton.

3. Chu trình Hamilton không chứa bất kỳ chu trình con

thực sự nào.

4. Trong quá trình xây dựng chu trình Hamilton, sau khi đã lấy 2 cạnh tới 1 đỉnh x đặt vào chu trình rồi thì không thể lấy thêm cạnh nào tới x nữa. Do đó có thể xóa mọi cạnh còn lại tới x trong G.

164

Đường đi và chu trình Hamilton

4

3

5

Xét đỉnh 1, chọn 2 cạnh (1,2) và (1,6)

2

6

1

9

7

8

165

Đường đi và chu trình Hamilton

4

3

5

•Xóa các cạnh (1,5), (1,4), (1,3), (1,7), (1,8), (1,9) (theo quy tắc 4).

2

6

1

•Các đỉnh 3, 4, 5 bậc 2, do đó các cạnh (2,3), (3,4), (4,5), (5,6) phải thuộc chu trình Hamilton (quy tắc 2).

9

7

8

•Chu trình con: 1,2,3,4,5,6,1 (không xóa được cạnh nào trong chu trình này).

166

Đường đi và chu trình Hamilton

4

3

5

•Chọn cạnh (1,2), (1,3). Xóa các cạnh (1,4), (1,5), (1,6), (1,7), (1,8), (1,9) (quy tắc 4).

•Xóa cạnh (2,3) để không tạo chu trình (quy tắc 3).

2

6

1

•Các đỉnh 4, 5, 6, 7, 8, 9 có bậc 2 nên thuộc chu trình Hamilton (quy tắc 2).

9

7

8

•Chu trình nhận được: 1,3,4,5,6,7,8,9,2,1.

167

Ví dụ: Tìm chu trình và đường đi Hamilton

• G3: Đồ thị Hamiton • G2: Đồ thị nửa Hamiton • G1: không nửa Hamiton

168

Thuật toán liệt kê tấc cả các chu trình Hamilton

• Thuật toán dựa trên cơ sở thuật toán quay lui cho phép

liệt kê tấc cả các chu trình Hamilton.

169

170

171

Ví dụ: Liệt kê tấc cả các chu trình Hamilton cho hình sau:

172

Cây nhị phân mô tả thuật toán trên

173

Đường đi và chu trình Hamilton

• Định lý 2.5: Mọi đồ thị đầy đủ đều có chu trình

Hamilton.

174

Đường đi và chu trình Hamilton

• Định lý 2.6: Cho một đồ thị G. Giả sử có k đỉnh của G sao cho

nếu xóa đi k đỉnh này cùng với các cạnh liên kết với chúng khỏi G thì đồ thị nhận được có hơn k thành phần. Khi đó, G không có chu trình Hamilton.

1

1

2

2

3

4

5

5

6

7

6

7

175

9

8

10

8

10

Đường đi và chu trình Hamilton

• Định lý 2.7 (Định lý Dirac):

Coi đồ thị G liên thông và có n đỉnh (n  3). Nếu mọi đỉnh của G đều có bậc  n/2 thì G có chu trình Hamilton.

176

Đường đi và chu trình Hamilton

• Định lý 2.8 (tổng quát của định lý 2.7):

Một đồ thị G có n đỉnh và 2 đỉnh bất kỳ nào cũng có tổng các bậc  n thì G có một chu trình Hamilton.

177

Đường đi và chu trình Hamilton

• Định lý 2.9:

Mọi đồ thị có hướng đầy đủ đều có đường đi Hamilton.

B

A

Đường đi: CBDA

C

D

178

Định nghĩa:

• Một đồ thị có chứa một đường đi Hamilton được gọi là

đồ thị nửa Hamilton.

• Định lý (Rédei): Nếu G là một đồ thị có hướng đầy đủ

thì G là đồ thị nửa Hamilton.

• Hệ quả: Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn 2/n −1 thì G là đồ thị nửa Hamilton.

179

• Định lý: Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n ≥ 2) và bậc của mỗi đỉnh lớn hơn n/2 thì G là một đồ thị Hamilton.

180

Tóm tắt

 Một đường đi Euler của G là một đường đi đơn giản có đỉnh bắt đầu khác đỉnh kết thúc và qua tất cả các cạnh của G. Khi này G còn được gọi là một đường đi Euler.

 Một chu trình Euler của G là một chu trình đơn giản đi qua tất cả các cạnh của G. Khi này G còn được gọi là một chu trình Euler.

181

Tóm tắt

• Cho 1 đồ thị vô hướng G liên thông và có hơn 1 đỉnh.

Khi đó, G có chu trình Euler nếu và chỉ nếu mọi đỉnh của G đều có bậc chẵn.

• Cho một đồ thi vô hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu G có đúng 2 đỉnh bậc lẻ.

182

Tóm tắt

• Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó,

G có chu trình Euler nếu và chỉ nếu G cân bằng.

• Cho đồ thị có hướng G liên thông và có hơn 1 đỉnh. Khi đó, G có đường đi Euler nếu và chỉ nếu trong G có 2 đỉnh a, b thỏa:

dout(a) = din(a) + 1 din(b) = dout(b) + 1

mọi đỉnh còn lại đều cân bằng và đường Euler phải bắt đầu tại a và kết thúc tại b.

183

Tóm tắt

• Một đường đi Hamilton của G là một đường đi sơ cấp

qua tất cả các đỉnh của G.

• Một chu trình Hamilton của G là một chu trình sơ cấp

qua tất cả các đỉnh của G.

• Chưa có một điều kiện cần và đủ để xác định chu trình

Hamilton.

184

Tutte Graph

1. Đồ thị Tutte là 3-liên thông và chính qui bậc 3. 2. Đồ thị Tutte không là đồ thị Hamilton.

185

Đồ thị không là nửa Hamilton

• Các đỉnh bậc 1 phải là đỉnh bắt đầu hoặc kết thúc của

đường đi Hamilton.

186

Đồ thị có ba đỉnh bậc 1  không là nửa Hamilton

Đồ thị không là nửa Hamilton

• Đồ thị sau đây không là nửa Hamilton.

• Chú ý: Phần khó nhất trong chứng minh đồ thị Tutte

không là Hamilton dựa vào kết quả này.

187

Định lý về sự tồn tại đường đi Hamilton

• Định lý Dirac: Nếu G là đơn đồ thị vô hướng liên thông với n3 đỉnh, và v deg(v)  n/2, thì G có chu trình Hamilton.

• Định lý Ore: Nếu G đơn đồ thị vô hướng liên thông với n3 đỉnh, và deg(u) + deg(v)  n với mọi cặp đỉnh không kề nhau u, v, thì G có chu trình Hamilton.

188

Oystein Ore 1899 - 1968 (Norway)

Paul Adrien Maurice Dirac 1902 - 1984 (USA)

189

HAM-CIRCUIT là NP-đầy đủ

• Gọi HAM-CIRCUIT là bài toán:

– Cho đơn đồ thị vô hướng G, hỏi G có chứa chu trình Hamilton

• Bài toán này được chứng minh là thuộc lớp bài toán

NP-đầy đủ! – Có nghĩa là, nếu như tìm được thuật toán để giải nó trong thời gian đa thức, thì thuật toán này có thể sử dụng để giải mọi bài toán thuộc lớp NP trong thời gian đa thức.

190

hay không?

Chương 1 CÁC KHÁI NIỆM CƠ BẢN

1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị

191

Tô màu đồ thị

Graph Coloring • Tô màu đỉnh (Vertex Coloring) • Tô màu cạnh (Edge Coloring)

192

Tô màu đồ thị - Graph Coloring

Xét bản đồ

193

Tô màu bản đồ - Map Coloring

Ta muốn nhận biết các nước bằng cách tô màu. Rõ ràng: Tô bởi 1 màu là không thể phân biệt được:

194

Map Coloring

Bổ sung thêm 1 màu nữa. Thử tô các nước bởi 2 màu.

195

Map Coloring

Cho phép sử dụng hai màu, ta thử tô mỗi nước bởi một trong hai màu.

196

Map Coloring

Cho phép sử dụng hai màu, ta thử tô mỗi nước bởi một trong hai màu.

197

Map Coloring

Cho phép sử dụng hai màu, ta thử tô mỗi nước bởi một trong hai màu.

198

Map Coloring

Hai nước bị tô bởi cùng màu. Không phân biệt được danh giới.

199

Map Coloring

Vậy thì thêm 1 màu nữa:

200

Map Coloring

Vẫn không đủ. Cần ít ra là 4 màu bởi vì chính nước này.

201

Map Coloring

Với 4 màu, có thể tô được.

202

4-Color Theorem

Định lý 4 màu: Mọi bản đồ hành chính đều có thể tô bởi bốn màu sao cho không có 2 đơn vị hành chính có chung biên giới nào bị tô bởi cùng màu.

Proof. Năm 1976, Haken và Appel chứng minh được định lý 4 màu “bằng máy tính”. (Thực hiện kiểm tra tô bởi 4 màu gần 2000 bản đồ đặc biệt bằng máy tính.)

203

Từ tô màu bản đồ đến tô màu đồ thị

Bài toán tô màu bản đồ có thể dẫn về bài toán tô màu đồ thị:

204

Từ tô màu bản đồ đến tô màu đồ thị

Mỗi vùng đặt tương ứng với một đỉnh:

205

Từ tô màu bản đồ đến tô màu đồ thị

Hai vùng có chung biên giới có cạnh nối:

206

Từ tô màu bản đồ đến tô màu đồ thị

Thực ra, ta cũng có thể xem bản đồ là đồ thị và khi đó sẽ xét đồ thị đối ngẫu của nó.

207

Từ tô màu bản đồ đến tô màu đồ thị

Đồ thị đối ngẫu (Dual Graphs) : 1) Đặt mỗi miền ứng với 1 đỉnh:

208

Từ tô màu bản đồ đến tô màu đồ thị

Đồ thị đối ngẫu (Dual Graphs) : 2) Nối các đỉnh bởi các cạnh:

209

Định nghĩa đồ thị đối ngẫu

Định nghĩa:

Đồ thị đối ngẫu G* của đồ thị phẳng G = (V, E) với tập các miền R là đồ thị với tập đỉnh và cạnh được xây dựng như sau – Tập đỉnh của G*: V (G*) = R – Tập cạnh của G*: E (G*) = tập các cạnh dạng (F1,F2)

210

trong đó 2 miền F1 và F2 có cạnh chung.

Từ tô màu bản đồ đến tô màu đồ thị

Như vậy đồ thị đối ngẫu là:

211

Từ tô màu bản đồ đến tô màu đồ thị

Tô màu miền tương đương với tô màu đỉnh của đồ thị đối ngẫu.

212

Định nghĩa sắc số

Định nghĩa: Giả sử c là số nguyên dương. Đơn đồ thị vô hướng được gọi là tô được bởi c màu nếu có thể tô các đỉnh của nó bởi c màu sao cho không có hai đỉnh kề nhau nào bị tô bởi cùng một màu. Sắc số (chromatic number) của đồ thị G, ký hiệu bởi (G), là số c nhỏ nhất sao cho có thể tô được G bởi c màu.

Ví dụ:

Ta có (G) = 2, nếu G là đồ thị hai phía. Dễ thấy điều ngược lại cũng đúng.

213

Rõ ràng (G)  (G).

Từ tô màu bản đồ đến tô màu đồ thị

Bản đồ không tô được bởi 2 màu, vì thế đồ thị đối ngẫu không tô được bởi 2 màu:

214

Từ tô màu bản đồ đến tô màu đồ thị

Bản đồ không tô được bởi 3 màu, vì thế đồ thị đối ngẫu không tô được bởi 3 màu:

215

Từ tô màu bản đồ đến tô màu đồ thị

Đồ thị tô được bởi 4 màu vì thế bản đồ cũng tô được bởi 4 màu:

216

Định lý 4 màu trong ngôn ngữ đồ thị

Định lý. Mọi đồ thị phẳng đều tô được bởi 4 màu.

217

Thuật toán tham lam

3

2

1

1

4

2

5

3

2

2

3

3

5

1

6

4

4

4

6

1

• Khởi tạo. Sắp xếp các đỉnh của đồ thị theo thứ tự v1, v2, …, vn • Bước i (i=1, 2,..., n): Tô đỉnh vi bởi màu có chỉ số nhỏ nhất trong số các màu chưa được sử dụng để tô các đỉnh kề của nó.

• Chú ý: Kết quả thực hiện thuật toán là phụ thuộc vào trình tự 218 sắp xếp các đỉnh của đồ thị.

Cận trên cho sắc số

Định lý. Đối với đơn đồ thị vô hướng bất kỳ G ta có

(G)  (G)+1.

Chứng minh

• Trong dãy đỉnh, mỗi đỉnh có nhiều nhất (G) đỉnh kề.

• Do đó, thuật toán tham lam không thể sử dụng nhiều hơn

(G)+1 màu.

Một cận trên tốt hơn được cho trong định lý sau đây

Định lý Brook (1941). Giả sử G là đơn đồ thị vô hướng liên thông khác với đồ thị đầy đủ và chu trình độ dài lẻ. Khi đó

219

(G)  (G).

Tô màu đồ thị và Lập lịch

Ví dụ: Ta cần lập lịch thi kết thúc môn học cho các chuyên đề có mã số:

1007, 3137, 3157, 3203, 3261, 4115, 4118, 4156

• Giả sử các môn học sau không có sinh viên nào đồng thời

cùng thi (do điều kiện tiên quyết) : 1007-3137 1007-3157, 3137-3157 1007-3203 1007-3261, 3137-3261, 3203-3261 1007-4115, 3137-4115, 3203-4115, 3261-4115 1007-4118, 3137-4118 1007-4156, 3137-4156, 3157-4156

220

Hỏi lịch thi gồm ít nhất bao nhiêu ngày? (Lịch thi phải đảm bảo mỗi sinh viên trong một ngày phải thi không quá 1 môn)

Tô màu đồ thị và Lập lịch

3203

3261

3137

4115

1007

4118

3157

4156

221

• Đưa bài toán về bài toán tô màu đồ thị: Các đỉnh tương ứng với các môn học, cạnh nối có giữa hai đỉnh nếu hai môn tương ứng có thể có chung sinh viên dự thi (vì thế không được tổ chức đồng thời):

Tô màu đồ thị và Lập lịch

• Trước hết ta đưa vào cạnh nối giữa các môn chắc chắc không có chung sinh viên (từ điều kiện tiên quyết)…

3203

3261

3137

4115

1007

4118

3157

4156

222

Tô màu đồ thị và Lập lịch

…và sau đó xây dựng đồ thị bù (complementary graph):

3203

3261

3137

4115

1007

4118

3157

4156

223

Tô màu đồ thị và Lập lịch

…và sau đó làm việc với đồ thị bù (chỉ các môn học có

cạnh nối mới có thể có chung sinh viên):

3203

3261

3137

4115

1007

4118

3157

4156

224

Tô màu đồ thị và Lập lịch

Vẽ lại:

3137

3203

3261

4115

1007

3157

4118

4156

225

Tô màu đồ thị và Lập lịch

Không thể tô bởi 1 màu vì cạnh này

3137

3203

3261

4115

1007

3157

4118

4156

226

Tô màu đồ thị và Lập lịch

2 màu không đủ tô vì có tam giác này

3137

3203

3261

4115

1007

3157

4118

4156

227

Tô màu đồ thị và Lập lịch

3 màu là đủ tô tam giác này. Ta tô bởi ba màu Red, Green, Blue.

3137

3203

3261

4115

1007

3157

4118

4156

228

Tô màu đồ thị và Lập lịch

3203-Red, 3157-Blue, 4118-Green:

3137

3203

3261

4115

1007

3157

4118

4156

229

Tô màu đồ thị và Lập lịch

do đó 4156 phải tô bởi Blue:

3137

3203

3261

4115

1007

3157

4118

4156

230

Tô màu đồ thị và Lập lịch

vì thế 3261 và 4115 phải là Red.

3137

3203

3261

4115

1007

3157

4118

4156

231

Tô màu đồ thị và Lập lịch

3137 và 1007 dễ dàng tô.

3137

3203

3261

4115

1007

3157

4118

4156

232

Tô màu đồ thị và Lập lịch

Vậy cần 3 ngày:

Ngày 2

3137

3203

3261

Ngày 1

4115

1007

3157

4118

4156

Ngày 3

233

Tô màu cạnh

• Ở phần trên ta xét tô màu đỉnh của đồ thị. Một cách hoàn toàn tương tự, ta có thể phát biểu bài toán tô màu cạnh của đồ thị.

• Định nghĩa. Ta gọi một phép tô màu cạnh của đơn đồ thị vô hướng G=(V,E) là phép gán cho mỗi cạnh của đồ thị một màu sao cho không có hai cạnh có chung đỉnh nào bị tô bởi một màu.

• Số màu ít nhất cần sử dụng để tô màu các cạnh của đồ thị

G được gọi là sắc số cạnh và ký hiệu là ’(G)

234

Tô màu cạnh

• Định lý Vizing. Đối với đơn đồ thị vô hướng G ta có

(G)  ’(G)  (G)+1.

• Chứng minh.

• Định lý. Đối với đơn đồ thị hai phía G ta có

’(G) = (G). • Chứng minh. Thuật toán tô màu /

235

– Vế trái của bất đẳng thức là hiển nhiên – Vế phải có thể chứng minh bằng qui nạp

Thuật toán tô màu /

• Ký hiệu C = {1, 2, …, (G)} là tập màu được sử dụng. • Lần lượt tô màu các cạnh của đồ thị theo qui tắc sau: • Giả sử ta đang xét việc tô màu cạnh e=(u,v). Ký hiệu

M(z) là tập màu đã dùng để tô các cạnh kề của đỉnh z. Rõ ràng |M(u)| < (G) và |M(v)| < (G). Có hai tình huống:

• 1) Nếu tìm được màu c  C \ (M(u)  M(v)) thì có thể

dùng màu c để tô màu cạnh e.

236

Thuật toán tô màu /

237

2) Không tìm được màu c  C \ (M(u)  M(v)). Do |M(u)| < (G) và |M(v)| < (G) suy ra phải tìm được α là màu chưa được dùng để tô bất cứ cạnh nào kề với u nhưng đã được dùng để tô cạnh kề với v, và β là màu chưa được dùng để tô bất cứ cạnh nào kề với v nhưng đã được dùng để tô cạnh kề với u. Khi đó xuất phát từ u ta đi theo cạnh màu β ta đến đỉnh v1, nếu trong số các cạnh kề v1 đã có cạnh được tô màu α thi đi theo cạnh này ta đến đỉnh v2, … Gọi đường đi tìm được là P. Lật ngược màu α/ β của các cạnh trên đường đi này, khi đó cách tô màu cạnh vẫn hợp lệ, đồng thời màu β có thể được dùng để tô cạnh e.