TOÁN R I R C NG D NG TRONG TIN H C

Ờ Ạ Ọ

Ụ

Ứ

 Gi ng viên:

ả

 Cao Thanh Tình (Email: tinhct@uit.edu.vn)  Bộ môn Toán Lý – ĐHCNTT – ĐHQGTPHCM

1

N i dung môn h c

ộ

ọ

 Ph n 1: Lý thuy t đ th ế ồ ị

ng đi

ẳ

ồ ị

 Ph n 2: Đ i s Boole

ạ ố

ầ ng v đ th  Đ i c ề ồ ị ạ ươ  Các bài toán v đ ề ườ  Đ th ph ng và bài toán tô màu đ th ồ ị  Cây ầ  Đ i s Boole ạ ố  C ng logic ổ  C c ti u hóa hàm Boole ự

ể

2

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

 Đ th (Graph)

ồ ị

ỉ ạ

ứ

ỉ

u, v˛ V ề (hay

e liên

ỉ ớ

 G = (V, E) v i ớ V≠˘  V: t p các đ nh ậ  E: t p các c nh ậ e˛ E  C nh ạ  ng v i 2 đ nh ớ  v, w là 2 đ nh k liên k t) v i nhau, ế thu c v i ộ

ớ v và w

 Ký hi u: ệ e = vw (…)  u ”

ượ

v: e đ vòng (khuyên) t

c g i là ọ i ạ u

3

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

t cùng

 Đ th (Graph) ồ ị  C nh b i ộ (song song) ạ ạ

 Hai c nh phân bi ứ

ệ ộ ặ

ng ng v i m t c p ớ

B

x

A

t ươ đ nhỉ  Đ n đ th ồ ị ơ

C

 Đ th không có vòng và

y

z

D

ồ ị c nh song song ạ  Đa đ thồ ị

 Các đ th không ph i là

ả

ồ ị đ n đ th ồ ị

ơ

4

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

ồ ị

ọ ặ

ỉ

 Đ th (Graph)  Đ th đ y đ ồ ị ầ ủ  Đ th mà m i c p đ nh ồ ị đ u k nhau ề ề ơ

ồ ị ầ

ủ

 Kn: đ n đ th đ y đ

ồ ị G’ = (V’, E’)

 Đ th con ồ ị  Đ th  V’ ˝

E

V, E’ ˝ ạ

 E và V h u h n

 Đ th h u h n ồ ị ữ ạ

 Đ th vô h n

ữ ạ

ồ ị

5

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Bi u di n đ th ồ ị ễ

ể

ể

”

ng (cong ho c th ng) n i 2

ẳ

ặ

ố

c dùng đ bi u di n trên máy tính

ườ

ễ

ậ ể ể ng dùng

ườ

ễ

ề

 Bi u di n hình h c ọ ễ m t đi m  M i đ nh ể ộ ỗ ỉ m t đ  M i c nh ỗ ạ ộ ườ đ nh liên thu c v i nó ớ ộ ỉ  Bi u di n b ng ma tr n ễ ằ ể ng đ  Th ượ  2 cách bi u di n th ể  Ma tr n kậ  Ma tr n liên thu c ộ

ậ

”

6

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Bi u di n đ th ồ ị ễ

ể

ằ

ậ

ễ

ể

 Ma tr n kậ

ậ

 Bi u di n b ng ma tr n ề  Ma tr n vuông c p ấ n (s đ nh c a đ th ) ồ ị  Các ph n t ượ

ủ ố ỉ c xác đ nh b i ở ị

ầ ử aij đ

ủ G

ộ ạ

ủ G

 aij = 1: N u ế vivj là m t c nh c a  aij = 0: N u ế vivj không là m t c nh c a ộ ạ

li

t kê c a các đ nh

ụ

ứ ự ệ

ủ

ỉ

ậ

 Tính ch tấ  Ph thu c vào th t ộ  Ma tr n là đ i x ng  M t vòng đ

c tính là m t c nh (

ố ứ ượ

ộ

ộ ạ

akk = 1)

7

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Bi u di n đ th ồ ị ễ

ể

ể

ễ

ằ

ậ

 Bi u di n b ng ma tr n ề

 Ma tr n kậ  Ví d 1ụ

8

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Bi u di n đ th ồ ị ễ

ể

ể

ễ

ằ

ậ

 Bi u di n b ng ma tr n ề

 Ma tr n kậ  Ví d 2ụ

D

B

A

E

C

A B C D E A 0 1 1 0 0 B 1 0 1 1 1 C 1 1 0 1 2 D 0 1 1 1 2 E 0 1 2 2 0

9

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Bi u di n đ th ồ ị ễ

ể

 Bi u di n b ng ma tr n

ể

ậ

ằ

ễ ậ

 Ma tr n liên thu c ộ  Ma tr n ậ M = (mij)nxm  Các ph n t ượ

c xác đ nh b i ở ị

ầ ử mij đ ế

ạ

ộ

ớ vi c a ủ G

ế

ạ

ộ

 mij = 1: N u c nh e  mij = 0: N u c nh e

j liên thu c v i j không liên thu c v i

ớ vi c a ủ G

ng ng v i các c nh b i là gi ng nhau trong ma

 Tính ch tấ  Các c t t

ộ ươ

ứ

ạ

ộ

ố

ớ

trân liên thu cộ

b ng 1 ng

 Các vòng ng v i m t c t có đúng m t ph n t ộ ộ

ầ ử ằ

ứ

ớ

ộ

ứ ố ớ

v i đ nh n i v i nó. ớ ỉ ng v đ th ề ồ ị

10

Ch ng 1. Đ i c ươ ạ ươ

Bi u di n đ th ồ ị ễ

ể

 Bi u di n b ng ma tr n

ậ

ể

ằ ễ  Ma liên thu cộ

 Ví dụ

11

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Bi u di n đ th ồ ị ễ

ể

ằ

ể

ễ

 Bi u di n b ng b ng ả (danh sách li n k ) ề  L u tr các đ nh li n k ề ề

ề ỉ

Đ nh li n k

ề

ỉ

ề

Đ nỉ h

ữ ư v i m t đ nh ộ ỉ ớ  Ví dụ

b

c

a

e

d

a b c d e

b, c, e a a, c, d, e c, e a, c, d

12

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

 B c c a đ nh ủ

ậ

ỉ

ỉ

ồ ị

ậ

 Đ nh c a đ th G có b c ề ớ n đ nh

ủ ế

ỉ

g

là n n u nó k v i khác.

e

f

ớ

c

deg(v)=0

a

d

b

deg(v)=1

ầ

deg(v)=0 " v

 Ký hi u: ệ deg(v) hay d(v)  M i vòng đ c k là 2 ượ ỗ ể i m t đ nh c nh t ộ ỉ ạ ậ (cid:219)  Đ nh cô l p ỉ (cid:219)  Đ nh treo ỉ  C nh treo có đ u mút là ạ m t đ nh treo ộ ỉ  Đ th r ng: ồ ị ỗ

13

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

ậ

 B c c a đ nh ỉ ủ  Đ nh lý 1.1

ị

 Trong m i đ th G = (V, E), t ng s b c c a các đ nh

ố ậ ủ

ỉ

c a G b ng 2 l n s c nh c a nó ủ

ố ạ

ọ ồ ị ầ ằ

ổ ủ

 H quệ

ả

 Trong m i đ th G = (V, E) ta có ọ ồ ị  S đ nh b c l là m t s ch n ẵ ộ ố ậ ẻ  T ng b c c a đ nh b c l ậ ẻ ủ

ố ỉ ổ

ậ

ỉ

là m t s ch n ộ ố

ẵ

14

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

ậ

 B c c a đ nh ỉ ủ  Đ nh lý 1.2

ị

 Trong m i đ th G = (V, E), n u s đ nh nhi u h n 1

ố ỉ

ề

ơ

ế

thì t n t

ọ ồ ị i ít nh t hai đ nh cùng b c ỉ ấ

ậ

ồ ạ

 Đ nh lý 1.3

ị

ố ỉ

ế

ề

ơ

ọ ồ ị ỉ

ậ

ỉ

 Trong m i đ th G = (V, E), n u s đ nh nhi u h n 2 và có đúng hai đ nh cùng b c thì hai đ nh này không đ ng th i b ng 0 ho c n-1

ờ ằ

ặ

ồ

15

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

 Ch ng minh và gi

ng

ứ

ả

i toán b ng ph ằ

ươ

pháp đ thồ ị

1. Xây d ng đ th mô t

đ y đ thông tin c a bài

ồ ị

ự

ả ầ

ủ

ủ

ố ượ

ng

˛ V ” các đ i t ng trong bài toán ˛ E ” m i quan h gi a hai đ i t ệ ữ

ố ượ

ố bài toán

toán  M i đ nh v ỗ ỉ  M i c nh e ỗ ạ  V đ th mô t ẽ ồ ị

1. S d ng các đ nh nghĩa, tính ch t, đ nh lý, …

ả ị

ử ụ

ị

ấ suy ra đi u c n ph i ch ng minh

ứ

ề

ầ

ả

16

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

 M t s bài toán ví d

ằ

ọ

ấ

i quen b ng nhau ằ

ạ ể

ạ

ọ

ụ ộ ố Ch ng minh r ng trong m t cu c h p tùy ý có ít ộ ộ ứ nh t 2 đ i bi u tham gia tr lên, luôn có ít nh t ấ ở ể hai đ i bi u mà h có s ng ườ ố trong các đ i bi u đ n d h p ự ọ ể

ế

ạ

17

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Các khái ni m c b n ệ

ơ ả

 M t s bài toán ví d Ch ng minh r ng s ng

i mà m i ng

ụ ườ

ườ

ố

ỗ

i đã có m t ộ l n b t tay nhau trên trái đ t là m t con s ố ộ

ằ ắ

ấ

ộ ố ứ s l ố ẻ ầ ch n.ẵ

18

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

 Đ th đ y đ ồ ị ầ

ủ Kn

|V| = n deg(v) = n – 1 " v ˛ V |E| = n(n - 1) / 2

 Đ n đ th ồ ị ơ  S đ nh: ố ỉ  B c: ậ  S c nh: ố ạ

K1

K2

K3

K4

K5

K6

19

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

 Đ th vòng ồ ị

Cn

|V| = n ‡ 3 deg(v) = 2 " v ˛ V |E| = n

 Đ n đ th ồ ị ơ  S đ nh: ố ỉ  B c: ậ  S c nh: ố ạ

20

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

 Đ th hình bánh xe

ồ ị

 N i các đ nh c a

ố

ộ ỉ

ớ u ta đ

Wn ớ

ủ Cn v i m t đ nh m i

c ượ Wn

deg(u) = n

ỉ |V| = n + 1 ‡ 3 deg(v) = 3 " v ˛ V \ {u}; |E| = 2n

 S đ nh: ố ỉ  B c: ậ  S c nh: ố ạ

21

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

ồ ị ề

 N i các đ nh c a

ộ ỉ

ớ u ta đ

ớ

ủ Cn v i m t đ nh m i

c ượ Wn

deg(u) = n

 Đ th đ u ỉ ố |V| = n + 1 ‡ 3 deg(v) = 3 " v ˛ V \ {u}; |E| = 2n

 S đ nh: ố ỉ  B c: ậ  S c nh: ố ạ

22

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

ậ

ươ

 Các kh i ố n-l p ph  N i các đ nh c a

ố

ng ớ

ộ ỉ

ớ u ta đ

ủ Cn v i m t đ nh m i

c ượ Wn

deg(u) = n

ỉ |V| = n + 1 ‡ 3 deg(v) = 3 " v ˛ V \ {u}; |E| = 2n

 S đ nh: ố ỉ  B c: ậ  S c nh: ố ạ

23

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

 Đ th bù ồ ị

 Hai đ n đ th G và G’ đ

c g i là bù nhau

ơ

ọ

ượ ồ ị  chúng có chung các đ nhỉ  C nh nào thu c G thì không thu c G’ và ng

ộ

ộ

c l i ượ ạ

ạ  Ký hi u: G’ = G ệ

24

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s đ th đ c bi ộ ố ồ ị ặ

t ệ

ng phân

 Đ th l

ọ

ồ ị ưỡ  M t đ th G đ ộ ồ ị ủ ỉ

c g i là đ th l ượ ể ỗ ạ

ồ ị ưỡ ậ ố

ế ậ ỗ ộ ậ

ợ ộ ỉ

ng phân n u t p các đ nh c a G có th phân thành 2 t p h p không r ng, r i ờ nhau sao cho m i c nh c a G n i m t đ nh thu c t p này ủ đ n m t đ nh thu c t p kia.

ộ ậ

ộ ỉ

ế

 Ký hi u: ệ Km,n

25

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

S đ ng c u gi a các đ th ồ ị

ự ẳ

ữ

ấ

ị

ầ v i ớ G’(V’, E’), (G » G’) n uế

 Đ nh nghĩa ẳ

f(u)f(v) ˛ E’

 G(V, E) đ ng c u f: V  V’  T n t i song ánh ồ ạ  B o toàn quan h li n k : ề ệ ề ả uv ˛ E (cid:219)  G đ ng c u v i G’ thì ấ

ớ

ẳ  |V| = |V’|  |E| = |E’|  deg(v) = deg(f(v))

v ˛ V

"

26

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

S đ ng c u gi a các đ th ồ ị

ự ẳ

ữ

ấ

ị

 Ch ng minh 2 đ th đ ng c u

ồ ị ẳ

ấ

 Đi u ki n c n

 Đ nh nghĩa ứ ề

ầ

 Xét s c nh, s đ nh, b c c a đ nh ố ỉ

ủ

ậ

ỉ

 Đi u ki n đ ủ

ề

 Xây d ng song ánh b o toàn quan h li n k

ệ ố ạ ệ ự

ệ ề

ả

ề

 Ví d 1ụ

v1

u1

u2

v2

v4

u4 u3 G = (V,E)

v3 H = (W,F)

27

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

S đ ng c u gi a các đ th ồ ị

ự ẳ

ữ

ấ

ị

 Ch ng minh 2 đ th đ ng c u

ồ ị ẳ

ấ

 Đ nh nghĩa ứ  Ví d 2ụ

28

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

S đ ng c u gi a các đ th ồ ị

ự ẳ

ữ

ấ

 Đ th t ị

bù n u G đ ng c u v i ph n bù c a nó

ủ

ế

ấ

ầ

ẳ

ớ

bù ồ ị ự  Đ nh nghĩa  Đ th G t ự ồ ị  Ví dụ

ị

 Hai đ th có ma tr n li n k (theo m t th t

nào đó

 Đ nh lý 1.4 ồ ị

ứ ự

ề

ậ

ề c a các đ nh) b ng nhau thì đ ng c u v i nhau ủ

ộ ấ

ằ

ẳ

ớ

ỉ

29

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ th có h

ng

ồ ị

ướ

ị

 T p đ nh V  T p c nh (cung) E = { (a, b) | a,b

V }

ỉ ạ

 Đ nh nghĩa  G = (V, E) ậ ậ  e = (a, b) ˛

ab

E  Ký hi u: e = ệ ng t  e có h ướ  a: đ nh đ u; ầ ỉ  e là khuyên (cid:219)

a đ n b ế ừ b: đ nh cu i ố ỉ a” b

˛

30

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ th có h

ng

ồ ị

ướ

ậ

ỉ

 B c c a đ nh ủ  B c vào ậ

 deg - (v) = | { u | (u, v) ˛

E } |

 B c raậ

 deg + (v) = | { u | (v, u) ˛

E } |

31

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ th có h

ng

ồ ị

ướ

ậ

ị

 T ng b c vào c a các đ nh b ng t ng b c ra và b ng

ậ

ậ

ằ

ằ

ổ

ỉ

 B c c a đ nh ỉ ủ  Đ nh lý 1.5 ủ ổ s c nh c a đ th ồ ị ố ạ

ủ v |

|

|

v

|

+

=

=

deg

v )(

deg

v )(

|

E

|

-

i

= 1

i

 Đ th cân b ng

ồ ị

= 1 ằ |

v

|

| v

|

+

(cid:229) (cid:229)

deg

)( v

deg

)( v

Vv

=(cid:229)

= 1

i

= 1

i

- ˛ " (cid:229)

32

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ th có h

ng

ồ ị

ướ

ậ

ỉ

 B c c a đ nh ủ  Ví dụ

 Có m t nhóm g m 9 đ i bóng bàn thi đ u vòng tròn

ấ

ồ

ộ

t.

ủ ấ ả

ả

ộ

ộ m t l ộ ượ ỏ ể

 H i sau khi có k t qu thi đ u c a t ế ợ b t kỳ đ i nào trong 09 đ i này

ấ ộ

ườ

th có tr ấ cũng đ u th ng 05 đ i khác trong nhóm đ ộ ề

t c các đ i có ộ c không? ượ

ng h p ắ

33

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ ng đi và chu trình

ườ

 Đ ng đi ườ ị

ế

ạ

ộ

 Đ ng đi là m t dãy các c nh liên ti p ườ  Ký hi u ệ

v0v1, v1v2, …, vn-1vn v0v1v2 … vn-1vn

ầ

ỉ

 v0: đ nh đ u; ỉ

vn: đ nh cu i ố

 Đ nh nghĩa

34

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ ng đi và chu trình

ườ

 Đ ng đi ườ ị

 Đ ng đi đ n (gi n)

 Đ nh nghĩa ườ

ả

ơ

 Đ ng đi không qua c nh nào quá m t l n

ộ ầ

ườ

ạ

 Đ ng đi s c p

ơ ấ

ườ

ườ

ộ ầ

Đ ng đi đi đ n

 Đ ng đi không qua đ nh nào quá m t l n ỉ ườ

ơ ấ (cid:222)  Đ ng s c p

ườ

ơ

35

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ ng đi và chu trình

ườ

 Chu trình ị

ng đi khép kín (

v0v1v2 … vn-1vnv0)

 đ  đ dài ít nh t là 3

 Đ nh nghĩa  Chu trình ườ ộ

ấ

 Chu trình đ n gi n

ả

ơ

 Chu trình không ch a c nh nào quá 1 l n ứ

ạ

ầ

 Chu trình s c p

ơ ấ

 Chu trình không ch a đ nh nào quá 1 l n ứ

ầ

ỉ

36

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Đ ng đi và chu trình

ườ

 Đ nh lý 1.6

 Chu trình ị

ng

ướ

ớ

ố ỉ ậ

ặ

ủ thì trong G luôn t n t

 G = (V, E) là m t đ th vô h ộ ồ ị  S đ nh l n h n ho c b ng 3 ặ ằ ơ  B c c a m i đ nh đ u l n h n ho c b ng 2 ề ớ ơ ọ ỉ ằ i m t chu trình s c p ơ ấ ộ

ồ ạ

 Đ nh lý 1.7

ị

ng

ướ

ớ

ố ỉ ậ

ặ

ủ thì trong G luôn t n t

 G = (V, E) là m t đ th vô h ộ ồ ị  S đ nh l n h n ho c b ng 4 ặ ằ ơ  B c c a m i đ nh đ u l n h n ho c b ng 3 ề ớ ơ ọ ỉ ằ i m t chu trình s c p có đ dài ch n ơ ấ ộ

ồ ạ

ẵ

ộ

37

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Tính liên thông

 Tính liên thông trong đ th ồ ị

ngướ vô h  Đ nh nghĩa ị

ng đi

ườ

 M t đ th liên thông n u ế ộ ồ ị gi a hai đ nh phân bi t b t ệ ấ ỉ ữ kỳ đ u có đ ề  Thành ph n liên thông ầ

 Đ th con G’ = (V’, E’) ồ ị  G’ liên thông

ị

 Đ th G=(V, E) là liên

ồ ị

ỉ

ấ

ầ

thông khi và ch khi G có duy nh t m t thành ph n ộ liên thông

 Đ nh lý 1.8

38

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Tính liên thông

ng

ồ ị

ướ

 Tính liên thông trong đ th vô h ầ

 Đ nh c t và c u ắ

ỉ

ố

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

ạ

ộ

ớ

ắ (cid:219)  u là m t ộ đ nh c t ỏ u và các c nh liên thu c v i nó tăng lên n u b s thành ph n liên thông tăng lên

ầ

ố

e

ỉ ế ộ ầ (cid:219)  e là m t c u n u b c nh ỏ ạ

ế

39

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Tính liên thông

 Tính liên thông trong đ th vô h

ng

ồ ị

ướ

 Đ nh lý 1.9

ị

u,v ˛ V

 G = (V , E) |V| = n ‡ 2   deg(u) + deg(v) ‡ n " thì G là đ th liên thông ồ ị  H quệ ả

 G = (V , E) |V| = n ‡

2

u,v ˛ V

  deg(v) ‡ n/2 " thì G là đ th liên thông ồ ị

40

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Tính liên thông

 Tính liên thông trong đ th có h

ng

ồ ị

ướ

c

ượ

ế

ạ

ọ

ượ

đ

ng G đ ng đi gi a hai đ nh b t kỳ c a nó ỉ

c g i là liên thông m nh n u luôn tìm đ ấ

ủ

ng G đ

ng

ồ ị

ế

ế

ướ

ứ

c g i là liên thông y u n u đ th vô h ọ ng liên thông ướ

 Liên thông m nhạ  Đ th có h ướ ồ ị ữ ườ  Liên thông y uế  Đ th có h ượ ướ ồ ị ng ng v i nó là vô h t ớ ươ

41

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

Tính liên thông

 Tính liên thông trong đ th có h

ng

ồ ị

ướ

ị

 N u đ th G có đúng 2 đ nh b c l

thì 2 đ nh này ph i

ậ ẻ

ỉ

ả

ỉ

 Đ nh lý 1.10 ồ ị ế liên thông v i nhau

ớ

ị

 Đ nh lý 1.11 ồ ị

ỉ

 Đ th G là m t đ th l ủ

ộ ồ ị ưỡ chu trình c a nó đ u có đ dài ch n ề

ng phân khi và ch khi m i ọ ộ

ẵ

42

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s phép bi n đ i đ th ổ ồ ị

ộ ố

ế

 H p c a 2 đ th ồ ị ủ

ợ

 G = (V, E)  G’ = (V’, E’)  G’’ = G ¨  V’’ = V ¨  E’’ = E ¨

G’ = (V’’, E’’) V’ E’

43

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị

M t s phép bi n đ i đ th ổ ồ ị

ộ ố

ế

ơ ấ

e = uv b i m t đ nh m i cùng v i 2 c nh

uw và vw

ế ạ ộ ỉ

ớ

ạ

ớ

 Phép phân chia s c p  Phép thay th c nh ở  Đ ng phôi

ồ

cùng

ồ

ớ

 G đ ng phôi v i G’ n u chúng có th nh n đ ế

ể

ậ

ộ

c t ượ ừ m t đ th b ng m t dãy các phép phân chia s c p ơ ấ  Hai đ th đ ng phôi ch a ch c đ ng c u v i nhau ư

ộ ồ ị ằ ồ ị ồ

ẳ

ắ

ấ

ớ

44

Ch ng 1. Đ i c ươ ạ ươ ng v đ th ề ồ ị