B GIÁO D C VÀ ÀO T O
TR
NG
I H C C N TH
KHOA S PH M
B MÔN TOÁN H C

GIÁO TRÌNH

TOÁN R I R C
(Discrete mathematics)

A Biên so n
Th.s Bùi Anh Ki t
Th.s Tr ng Qu c B o

N m 2003


L I NÓI

U

Toán r i r c là m t l nh v c c a toán h c nghiên c u v các đ i t ng r i r c. M c dù
các đ i t ng là r i r c, không có ý ngh a nh ng khi chúng ta liên k t các đ i t ng r i r c l i
v i nhau ta l i có đ c nh ng thông tin r t lý thú và mang nhi u ý ngh a. Chúng ta s s d ng
công c c a toán h c r i r c khi ph i đ m các đ i t ng, nghiên c u m i quan h gi a các t p
r i r c, khi nghiên c u các quá trình h u h n. M t trong nh ng nguyên nhân ch y u làm
t ng t m quan tr ng c a toán r i r c là vi c l u tr và x lý thông tin trên máy tính đi n t mà
b n ch t là các quá trình r i r c. Ba l nh v c có nhi u ng d ng c a toán h c r i r c là lý
thuy t t h p, hàm đ i s logic (đ i s Boole) và lý thuy t đ th . Các v n đ v lý thuy t t

h p, hàm đ i s logic (đ i s Boole) s đ c trình bày trong các giáo trình khác. Trong ph m
vi giáo trình này chúng tôi ch trình bày l nh v c có th xem là quan tr ng nh t và có nhi u
ng d ng nh t c a toán h c r i r c là Lý thuy t đ th .
Lý thuy t đ th đ c khai sinh k t công trình nghiên c u v bài toán “7 cây c u
Königsberg” c a nhà toán h c Leonhard Euler (1707 - 1783) đ c công b vào n m 1736.
T đó đ n nay, đã có nhi u nhà toán h c trên th gi i nghiên c u làm cho lý thuy t đ th
ngày càng phong phú và có nhi u ng d ng trong các l nh v c khác nhau nh m ng đi n t ,
lý thuy t mã, v n trù h c, kinh t h c,... c bi t, trong kho ng vài ch c n m tr l i đây, cùng
v i s ra đ i c a máy tính đi n t và s phát tri n nhanh chóng c a Tin h c, Lý thuy t đ th
càng đ c quan tâm nhi u h n, đ c bi t là các thu t toán và ng d ng trên đ th . Hi n nay,
môn h c này đã đ c xem là ki n th c c s c a khoa h c máy tính.
Giáo trình này đ c biên so n t bài gi ng c a các tác gi trong các n m qua
Tr ng i h c C n th và các trung tâm đào t o liên k t trong vùng
ng b ng sông C u
long, nh m đáp ng nhu c u tài li u tham kh o và h c t p b ng ti ng Vi t c a sinh viên. ây
là giáo trình dành cho sinh viên s ph m Toán Tin, Toán nên h u h t các v n đ đ c trình
bày đ u đ c ch ng minh ch t ch , rõ ràng.
ng th i, c ng kèm theo m t s thu t toán và
các ng d ng th c t c ng nh ng d ng trên máy tính. Các sinh viên chuyên ngành Lý Tin,
Tin h c và i n t c ng có th s d ng giáo trình này nh m t tài li u tham kh o h u ích.
N i dung c a giáo trình bao g m các n i dung c b n nh t c a lý thuy t đ th có kèm
các bài t p áp d ng và đ c chia làm 04 ch ng:
Ch ng 1: Trình bày các thu t ng , đ nh ngh a và khái ni m c b n c a đ th nh đ
th vô h ng, có h ng, các lo i đ th , đ ng đi, chu trình, tính liên thông, ph ng pháp
t ng quát đ gi i quy t m t bài toán b ng lý thuy t đ th ,...
đ

Ch ng 2: Trình bày các bài toán v đ ng đi Euler, Hamilton, các gi i thu t tìm
ng đi ng n nh t nh Dijkstra, Heterdetmin cùng m t s ví d ng d ng.


Ch
cùng m t s

ng 3: Trình bày các v n đ liên quan đ n đ th ph ng và bài toán tô màu đ th
ng d ng.

Ch ng 4: Kh o sát t ng quát v c u trúc cây và các v n đ liên quan, đ c bi t là cây
nh phân. M t s ng d ng c a cây trong tin h c c ng đ c trình bày nh các phép duy t cây,
cây bi u th c s h c, ký pháp ngh ch đ o Ba Lan (RPN), các thu t toán tìm cây ph t i ti u,...
Cu i m i ch ng có ph n bài t p giúp sinh viên rèn luy n và ki m tra l i nh ng ki n
th c đã đ c h c. M t s v n đ trong ph n lý thuy t c ng còn đ m xem nh ph n bài t p
t gi i c a sinh viên.
Do gi i h n v m t th i gian (giáo trình đ c gi ng d y trong 45 ti t) nên chúng tôi
ch đ c p đ n các v n đ c b n nh t c a lý thuy t đ th . Các v n đ m r ng và chuyên sâu
c a lý thuy t c a lý thuy t đ th s đ c trình bày thêm trong quá trình gi ng d y trên l p và
xem là các v n đ m cho sinh viên t h c, nghiên c u thêm khi làm ti u lu n, lu n v n t t
nghi p.


Tuy đã h t s c c g ng, song v i qu th i gian và ki n th c h n ch ch c ch n giáo
trình v n còn nh ng v n đ khi m khuy t, chúng tôi r t mong nh n đ c s đóng góp ý ki n
quý báu c a quý th y cô, b n bè đ ng nghi p và các em sinh viên đ giáo trình đ c hoàn
thi n h n.

Th.S. Bùi Anh Ki t
Th.S. Tr ng Qu c B o
C n th , tháng 12 n m 2003


Ch


ng I

IC

NG V

TH

I. Các khái ni m c b n
1.

th

th (graph) G = (V,E) là m t b g m 2 t p h p V và E, trong đó V ≠ ∅ các ph n t
c a V đ c g i là các đ nh (vertices), các ph n t c a E đ c g i là các c nh (edges), m i
c nh t ng ng v i 2 đ nh.
N u c nh e t ng ng v i 2 đ nh v, w thì ta nói v và w là 2 đ nh k (hay 2 đ nh liên
k t) (adjacent) v i nhau. Ta c ng nói c nh e t i hay liên thu c (incident) v i các đ nh v và w.
e
w (ho c e = vw; e = wv). C nh vv t ng ng v i 2 đ nh trùng
Ký hi u e = vw hay v
nhau g i là m t vòng hay khuyên (loop) t i v.
Hai c nh phân bi t cùng t ng ng v i m t c p đ nh đ c g i là 2 c nh song song
(paralleledges) hay c nh b i.
th không có c nh song song và c ng không có vòng đ c
g i là đ n đ th (simple graph). Ng c l i là đa đ th (multigraph).
th mà m i c p đ nh c a nó đ u k nhau đ c g i là đ th đ y đ . (Complete
n đ th đ y đ bao g m n đ nh đ c ký hi u: Kn.


graph).

th G' = (V',E') đ
⊂ V; E' ⊂ E.
l iđ

c g i là m t đ th con (subgraph) c a đ th G = (V,E) n u V'

th có s đ nh và s c nh h u h n đ
c g i là đ th vô h n (Infinite graph).

c g i là đ th h u h n (finite graph), ng

c

Trong giáo trình này, chúng ta ch kh o sát các đ th h u h n.
2. Bi u di n đ th
M t đ th có th đ

c bi u di n b ng hình h c, m t ma tr n hay m t b ng.

2.1. Bi u di n hình h c
Ng

i ta th

ng bi u di n hình h c c a đ th nh sau:

- Bi u di n m i đ nh c a đ th b ng m t đi m (vòng tròn nh , ô vuông nh ).
- M t c nh đ c bi u di n b i m t đ ng (cong hay th ng) n i 2 đ nh liên thu c v i

c nh đó.
Ví d 1:
th G có: V = {a, b, c, d, e}
E = {ab, ac, ad, bd, cd, ce}
c bi u di n hình h c nh sau:

b

c

a
Ví d 2:

th G có:

d
e
V = {u, v, x, y}
E = {uv, uv, ux, vx, xy, yy}

c bi u di n hình h c nh sau:

Trang 1


v
x
u

y


Chú ý: Khi bi u di n hình h c các đ th , giao c a các c nh ch a ch c là đ nh c a đ
th .

B
A

x

C

Ví d 3:

D

y

z

Ví d 4: Các đ n đ th đ y đ :

K1

K2

K3

K5

K4


2.2 Bi u di n đ th b ng ma tr n
Ng i ta có th bi u di n đ th b ng ma tr n. Có 2 ki u ma tr n th
bi u di n đ th :

ng đ

c dùng đ

- Ma tr n liên k t hay li n k (adjacency matrix).
- Ma tr n liên thu c (incidence matrix).
Ü Ma tr n li n k
Cho G = (V,E) có n đ nh v1, v2, ..., vn. Ma tr n li n k c a G t
đ nh v1, v2, ..., vn là m t ma tr n vuông c p n.

ng ng v i th t các

A = (aij)n trong đó:
1 n u vivj là m t c nh c a G.
0 n u vivj không là m t c nh c a G.

aij =

Ü Chú ý:
- Ma tr n li n k c a m t đ th khác nhau tùy thu c vào th t li t kê các đ nh. Do
đó, có t i n! ma tr n li n k khác nhau c a m t đ th n đ nh vì có n! cách s p x p n đ nh.
- Ma tr n li n k c a m t đ th là m t ma tr n đ i x ng vì n u vi đ c n i v i vj thì
vj c ng đ c n i vi và ng c l i n u vi không n i v i vj thì vj c ng không n i v i vi.
- M t vòng đ


c tính là m t c nh t đ nh v vào v.

B
Ví d 5:

D

th sau: A

có ma tr n li n k là:

C

E

Trang 2


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
Ví d 6: Hãy v đ th có ma tr n li n k theo th t c a các đ nh là a, b, c, d.

0
1
1
1


1
0
0
1

1
0
1
1

a

1
1
0
0

b
c

d

Ü Ma tr n liên thu c
Ng i ta còn dùng ma tr n liên thu c đ bi u di n đ th . Cho G = (V,E) là m t đ th
v i v1, v2, ..., vn là các đ nh và e1, e2, ..., em là các c nh c a G. Khi đó ma tr n liên thu c c a
G theo th t trên c a V và E là m t ma tr n M = (mij)n x m v i:

1 n u c nh ej n i v i đ nh vi.
0 n u c nh ej không n i v i đ nh vi


mij =

Ü Chú ý: Các ma tr n liên thu c c ng có th đ c dùng đ bi u di n các c nh b i và
khuyên (vòng). Các c nh b i (song song) đ c bi u di n trong ma tr n liên thu c b ng cách
dùng các c t có các ph n t gi ng h t nhau vì các c nh này đ c n i v i cùng m t c p các
đ nh. Các vòng đ c bi u di n b ng cách dùng m t c t v i đúng m t ph n t b ng 1 t ng
ng v i đ nh n i v i khuyên đó.
Ví d 7:

th
v1 e2 v2

e4

e3

e6

e1

e5

e7

e8
v4
Có ma tr n liên thu c nh sau:

v3


v5

e

1 2 3 4 5 6 7 8

v
1
v1
2
v0
3
v0
4
v0
5
0

e e e e e e e
1 1
0 0 0 0
1 0
1
0 1 1 0
0 1
0
1 0 0 0
1
0 0

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

Trang 3


2.3. Bi u di n đ th b ng b ng
Ng i ta có th bi u di n đ th không có c nh b i b ng b ng hay còn g i là danh
sách li n k . Danh sách này ch rõ các đ nh n i v i m i đ nh c a đ th .
Ví d 8: Dùng danh sách li n k đ bi u di n đ th

b
c

a
e

d

nh

nh li n k

a

b, c, e


b

a

c

a, c, d, e

d

c, e

e

a, c, d

3. B c c a đ nh trong đ th
nh ngh a: nh v c a đ th G đ c g i là có b c n n u v k v i n đ nh khác (v là
đ u mút c a n c nh). Ký hi u: deg(v) hay d(v).
- M i vòng (khuyên) t i v đ

c k là 2 c nh t i v.

-

nh có b c 0 g i là đ nh cô l p (isolated vertex).

-

nh có b c 1 g i là đ nh treo (pendant vertex).


- C nh t i đ nh treo g i là c nh treo (pendant edge).
-

th mà m i đ nh đ u là đ nh cô l p g i là đ th r ng (null graph).

Ví d 9: Cho đ th sau:

a

g

f

e

b

c

d

Ta có: deg(a) = 4; deg(b) = 5; deg(c) = 4; deg(d) = 0; deg(e) = 1; deg(f) = 4; deg(g) =
4.
Ü 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. Ngh a là ta có:
V

∑ deg(v ) = 2 E
i =1


i

Ü H qu : Trong m i đ th G = (V, E), ta có:
1. S các đ nh b c l c a m t đ th là m t s ch n.
2. T ng b c c a các đ nh b c l trong m t đ th là m t s ch n.
Ü

nh lý 1.2: Trong m i đ th G = (V, E), có V ≥ 2 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), có V > 2 có đúng hai đ nh cùng b c thì

hai đ nh này không th đ ng th i có b c 0 ho c b c n-1.
4. Ch ng minh - gi i bài toán b ng ph

ng pháp đ th

ch ng minh (gi i) bài toán b ng đ th ta th c hi n theo các b

c sau:

Trang 4


ÜB

đó:


c 1: Xây d ng đ th G = (V, E) mô t đ y đ các thông tin c a bài toán, trong

+ M i đ nh v ∈V bi u di n cho m t đ i t

ng nào đó c a bài toán.

+ M i c nh e ∈ E n i 2 đ nh vi và v j s bi u di n cho m i quan h gi a hai đ i
t

ng ng đ

ng t

c bi u di n b ng vi và v j .

+ V đ th G = (V, E) mô t bài toán (n u đ

c).

Ü B c 2: S d ng các đ nh ngh a, đ nh lý, tính ch t,... đã bi t v lý thuy t đ th đ
suy ra đi u c n gi i (ch ng minh).
Ví d 10: Ch ng minh r ng trong m t cu c h p tùy ý có ít nh t 02 đ i bi u tham gia
tr lên, luôn luôn có ít nh t hai đ i bi u mà h có s ng i quen b ng nhau trong các đ i bi u
đã đ n d h p.
Ch ng minh:
ÜB

c 1: Xây d ng đ th G = (V, E) mô t đ y đ các thông tin c a bài toán:


+ nh: L y các đi m trên m t ph ng hay trong không gian t ng ng v i các đ i
bi u đ n d h p. i t ng c a bài toán đây là đ i bi u d h p. V y, m i đ nh v ∈V bi u
di n cho m t đ i bi u trong cu c h p.
+ C nh: Trong đ th G các đ nh vi và v j đ

c n i v i nhau b ng m t c nh n u hai

đ i bi u vi và v j quen nhau. V y, m i quan h gi a 02 đ i t

ng

đây là m i quan h quen

bi t. M i c nh e ∈ E n i 2 đ nh vi và v j trong G n u hai đ i bi u vi và v j quen nhau.
ÜB

c 2: Suy lu n đ suy ra đi u c n ch ng minh:

+ V i cách xây d ng đ th G nh đã trình bày thì s đ nh c a G chính là s đ i bi u
đ n d h p V ≥ 2 và b c c a m i đ nh trong G b ng đúng s đ i bi u quen v i đ i bi u đ c
bi u di n b ng đ nh này.
+ Theo đ nh lý 1.2 ta có trong G t n t i ít nh t 02 đ nh có cùng b c ngh a là luôn luôn
có ít nh t hai đ i bi u mà h có s ng i quen b ng nhau trong các đ i bi u đã đ n d h p.
Ví d 11: Ch ng minh r ng s ng
trên trái đ t này là m t con s ch n.

i mà m i ng

i đã có m t s l l n b t tay nhau


(Xem nh bài t p - Sinh viên t ch ng minh)

II. M t s đ th đ c bi t
1.

th đ y đ

nh ngh a:
th đ y đ (Complete graph), ký hi u: Kn là m t đ n đ th bao g m
n đ nh mà m i đ nh đ u có b c n−1 (m i đ nh đ u n i v i n−1 đ nh còn l i).

K1

K2

K3

K4

K5

K6

Ü V y Kn có:
+ S đ nh: V = n
+ B c c a đ nh deg(vi ) = n − 1 ; ∀vi ∈V
Trang 5


+ S c nh: E =

2.

n(n − 1)
2

th vòng

nh ngh a:
th vòng ký hi u: Cn, n ≥ 3 là m t đ th v i n đ nh v1, v2, ..., vn và
các c nh v1v2, v2v3, ..., vnv1.

C3

C5

C4

C6

Ü V y Cn có:
+ S đ nh: V = n ≥ 3
+ B c c a đ nh deg(vi ) = 2 ; ∀vi ∈V
+ S c nh: E = n
3.

th hình bánh xe

nh ngh a: N u thêm m t đ nh vào đ th vòng Cn (n ≥ 3) và n i đ nh này v i n đ nh
c a Cn thì ta đ c đ th hình bánh xe (Wheel graph), ký hi u: Wn.


W3

W5

W4

W6

Ü V y Wn có:
+ S đ nh: V = n + 1

n≥3

+ B c c a đ nh deg(vi ) = 3 ; ∀vi ∈ V và vi ≠ đ nh đ

c thêm vào (vnew)

+ deg(v new ) = n
+ S c nh: E = 2n
4.

th đ u

nh ngh a: M t đ th đ u (Regular graph) là đ th mà m i đ nh đ u có cùng b c.
N u đ th G có các đ nh có cùng b c K thì đ c g i là K-đ u.
Ví d 12:
+

th r ng g m n đ nh là đ th đ u b c 0.


+ Cn là đ th đ u b c 2.
+ Kn là đ th đ u b c (n−1).

+

th 3-đ u 6 đ nh:

Trang 6


+

th 3-đ u 8 đ nh:

+

th đ u b c 3: đ th Petersen:

Ü V y k đ u n đ nh cóï:
+ S đ nh: V = n
+ B c c a đ nh deg(vi ) = k ; ∀vi ∈V
+ S c nh: E =
5. Các kh i n-l p ph

n*k
2

ng

Các kh i n-l p ph ng (n-cube graph), ký hi u: Qn là các đ th có 2n đ nh, m i đ nh

đ c bi u di n b ng m t dãy s nh phân v i đ dài n. Hai đ nh là li n k n u và ch n u các
dãy nh phân bi u di n chúng ch khác nhau đúng 1 bit.
10

Ví d 13:

0

11

Q1 1
00

Q2 01

110 111
101
100
010
011
000 Q 001
3

V y Qn cóï:
+ S đ nh: V = 2 n
+ B c c a đ nh deg(vi ) = n ; ∀vi ∈V
+ S c nh: E = n * 2 n −1
6.

th bù


Hai đ n đ th G và G' đ c g i là bù v i nhau n u 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 .
và

Ví d? 14

và

7.

th l

ng phân

M t đ th G đ c g i là đ th l ng phân (bipartie graph) n u t p h p các đ nh V
c a G có th phân thành 2 t p h p không r ng V1 và V2, V1 V2 = ∅ sao cho m i c nh c a G
n i m t đ nh c a V1 v i m t đ nh c a V2.

Trang 7


a v1

Ví d 15:
b

c

d


e v2

Ü M t đ th l ng phân mà m i đ nh c a V1 (có m đ nh) đ u k v i m i đ nh c a V2
(có n đ nh), đ c g i là m t đ th l ng phân đ y đ , ký hi u: Km,n.
V êduû
Û16:
K 2,3

K 1,5

K 3,3

Ü K là không ph i là đ th l ng phân vì n u ta chia các đ nh c a nó thành 2
3
ph n r i nhau thì m t trong 2 ph n này ph i ch a 2 đ nh. N u đ th là l ng phân thì các
đ nh này không th n i v i nhau b ng m t c nh. Nh ng trong K3 m i đ nh đ c n i v i đ nh
khác b ng m t c nh.

III. S đ ng c u c a các đ th
1.

nh ngh a

Các đ th G1 = (V1,E1) và G2 = (V2,E2) đ c g i là đ ng c u v i nhau n u có m t
song ánh f: V1 → V2 sao cho n u a và b là li n k trong V1 thì f(a) và f(b) li n k trong V2; ∀
a, b ∈ V1. Khi đó song ánh f đ c g i là m t đ ng c u.
Nói cách khác, n u 2 đ th là đ ng c u thì s t n t i m t song ánh gi a các đ nh c a 2
đ th b o toàn quan h li n k .
Ü Chú ý: N u 2 đ th G1 và G2 là đ ng c u thì chúng có:

+ S đ nh b ng nhau.
+ S c nh b ng nhau.
+ Hai đ nh t

ng ng có cùng b c.

ây là các đi u ki n c n đ hai đ th là đ ng c u.
Ü

ch ng minh hai đ th đ ng c u ta c n:
+ Ch ng minh đi u ki n c n th a.

+ Xây d ng m t song ánh b o toàn quan h li n k gi a hai đ th (đi u ki n
đ đ hai đ th đ ng c u).
Ví d 17: Ch ng minh r ng hai đ th sau là đ ng c u v i nhau:

u1

u2

v1

v2

u4

u3

v3


v4

G = (V,E)

H = (W,F)

Ü Xét đi u ki n c n:
+ Hai đ th G và H đ u có 4 đ nh,
+ Hai đ th G và H đ u có 4 c nh,
+ Các đ nh c a hai đ th đ u có b c 2.
Trang 8


V y đi u ki n c n th a.
Ü Xét đi u ki n đ :
Xét hàm f: V → W
u1 a v1
u2 a v4
u3 a v2
u4 a v3
⇒ f là song ánh và b o toàn quan h li n k , đi u ki n đ th a. V y hai đ th G và H
đ ng c u v i nhau.
vaì

Ví d 18:

không đ ng c u vì s c nh và đ nh khác nhau.

i u


G
G'
ki n c n không th a ⇒ G và G’ không đ ng c u.
a

V êduû19:

a'

b
e

G

c

b'

d

e'

c'

H

d'

G và H có cùng s c nh, s đ nh nh ng H có đ nh e' b c 1, trong khi đó G không có
đ nh nào b c 1. i u ki n c n không th a ⇒ G và H không đ ng c u.

2.

th t bù
th G đ

nh ngh a:

c g i là t bù (Self-complementary) n u G đ ng c u v i G .
;

Vê duû 20
:

G

H

nh lý 1.4: N u hai đ th G và H có ma tr n li n k (đ c li t kê theo m t th t
nào đó c a các đ nh) b ng nhau thì G và H là hai đ th đ ng c u v i nhau.

IV.

th có h
1.

ng (Directed graph)

nh ngh a

M t đ th có h ng G = (V,E) g m t p h p các đ nh V và t p h p các c nh E bao

g m các c p s p th t các ph n t c a V. C nh e t ng ng v i m t c p th t (a,b) c a 2
→

đ nh a, b ∈ V đ c g i là m t c nh có h ng t a đ n b. Ký hi u: e = ab . a đ c g i là đ nh
đ u, b đ c g i là đ nh cu i c a c nh e. nh đ u và đ nh cu i c a khuyên (vòng) là trùng
nhau.
a

b

e

d

V êduû21:
c

2. B c c a đ nh trong đ th có h

ng

2.1. B c vào
Trang 9


nh ngh a: Cho G là đ th có h
din(v)) là s c nh có đ nh cu i là v.

ng, b c vào c a đ nh v, ký hi u: deg−(v) (ho c


2.2. B c ra
nh ngh a: Cho G là đ th có h
s c nh có đ nh đ u là v.

ng, b c ra c a v, ký hi u: deg+(v) (hay dout(v)) là

Ü Chú ý: M t vòng t i m t đ nh s góp thêm m t đ n v vào b c vào và b c ra c a
đ nh này.
a

b

e

d

c

V êduû22:

+

i v i đ nh a: din(a) = 0, dout(a) = 3;

+

i v i đ nh b: din(b) = 3, dout(b) = 1;

+


i v i đ nh c: din(c) = 3; dout(c) = 2

+

i v i đ nh d: din(d) = 0; dout(d) = 3

+

i v i đ nh e: din(e) = 3; dout(e) = 0

2.3. nh lý 1.5: Cho G = (V,E) là m t đ th có h
b ng t ng b c ra và b ng s c nh c a đ th . Ngh a là ta có:
V

V

i =1

i =1

ng. T ng b c vào c a các đ nh

∑ d in (vi ) = ∑ d out (vi ) = E
Ü M t đ th có h ng đ
b c vào và b c ra b ng nhau.

c g i là cân b ng (balanced) n u m i đ nh c a nó đ u có

Ví d 23: Có m t nhóm g m 09 đ i bóng bàn thi đ u vòng tròn m t l t. H i sau khi
có k t qu thi đ u c a t t c các đ i có th có tr ng h p b t k đ i nào trong 09 đ i này

c ng đ u th ng đúng 05 đ i khác trong nhóm đ c không? (L u ý trong thi đ u bóng bàn
không có tr n hòa).

(Xem nh bài t p - Sinh viên t ch ng minh)

V. Tính liên thông c a đ th
1.

ng đi

nh ngh a:
ng đi (path) có đ dài n t vo đ n vn v i n là m t s nguyên d ng,
trong m t đ th vô h ng là m t dãy các c nh liên ti p vov1, v1v2, ... , vn−1vn. nh vo đ c
g i là đ nh đ u, đ nh vn đ c g i là đ nh cu i.
ng đi này th ng đ c vi t g n: vov1v2 ...
vn−1vn. Khi ch c n nêu ra đ nh đ u vo và đ nh cu i vn c a đ ng đi, ta vi t: đ ng đi vo −
vn.
(đ

Ü M t đ
ng đi đ n).
ÜM tđ

ng đi không qua c nh nào l n th hai đ
ng đi không qua đ nh nào l n th hai đ

Ü L u ý: M t đ ng đi s c p là m t đ
gi n có th không là đ ng đi s c p).

c g i là đ


c g i là đ

ng đi đ n gi n

ng đi s c p.

ng đi đ n gi n nh ng m t đ

ng đi đ n

2. Chu trình

Trang 10


đ

2.1. nh ngh a: M t đ ng đi khép kín (đ nh đ u ≡ đ nh cu i) và có đ dài n ≥ 3
c g i là m t chu trình (Cycle).
Ü Chu trình không đi qua c nh nào l n th hai đ

c g i là chu trình đ n gi n.

Ü Chu trình không đi qua đ nh nào l n th hai, tr đ nh đ u ≡ đ nh cu i, đ
m t chu trình s c p.
a

b


c

f

e

d

c g i là

V êduû24:

2.2.

Ü abcdbe là m t đ

ng đ n gi n.

Ü eabdc là m t đ

ng đi s c p...

nh lý 1.6: Cho G=(V,E) là m t đ th vô h

ng có V ≥ 3 và ∀v ∈V có

d (v ) ≥ 2 thì trong G luôn t n t i m t chu trình s c p.

Ch ng minh:
Vì G là m t đ th h u h n, m i đ ng s c p qua t ng đ nh không quá m t l n, nên

s đ ng s c p trong G là h u h n. Do đó, ta luôn xác đ nh đ c đ ng đi s c p có đ dài
c c đ i trong s các đ ng đi s c p có trong đ th G=(V,E).
Gi s α = v1 v 2 , L v k −1 v k là m t trong các đ ng đi s c p có đ dài c c đ i. Do b c
c a m i đ nh không nh h n 2 ( ∀v ∈V có d (v ) ≥ 2 ), nên đ nh v1 ph i k v i 1 đ nh u nào đó
và u ≠ v 2 . Xét 02 tr ng h p:
+ N u đ nh u ≡ vi (3 ≤ i ≤ k ) , khi đó trong đ th G s có m t chu trình s c p

β = v1 v 2 L vi L v k −1 v k v k −1 L vi v1 .
c l i, n u đ nh u ≠ vi (3 ≤ i ≤ k ) , khi đó trong G t n t i đ

+ Ng

α 1 = v1 v 2 , L v k −1 v k có đ dài l n h n đ

ng s c p

ng s c p α có đ dài l n nh t đã ch n (mâu

thu n). V y đ nh u ≡ vi (3 ≤ i ≤ k ) ⇒ trong đ th G có m t chu trình s c p.
2.3.

nh lý 1.7: Cho G=(V,E) là m t đ th vô h

ng có V ≥ 4 và ∀v ∈V có

d (v ) ≥ 3 thì trong G luôn t n t i m t chu trình s c p có đ dài ch n.

Ch ng minh:
Gi s α là m t đ


ng s c p có đ dài c c đ i trong đ th G=(V, E):

α = v1 v 2 v3 , L vi −1 vi vi +1 L v j −1 v j v j +1 L v k −1 v k
Vì α là đ ng s c p có đ dài c c đ i và b c c a m i đ nh không nh h n 3, nên
đ nh v1 ph i k v i 02 đ nh vi và vj khác thu c đ ng α v i 3 ≤ i ≤ k , 3 ≤ j ≤ k . Khi đó
trong G có 02 chu trình s c p:
+ α 1 = v1 v 2 v3 L vi −1 vi v1

và

+ α 2 = v1 v 2 v 3 L v i −1 v i v i +1 L v j −1 v j v1

Ta xét 2 tr

ng h p sau:

+ N u m t trong hai đ
ph i ch ng minh.

ng s c p α 1 ho c α 2 có đ dài ch n thì ta có đi u
Trang 11


đ

+ Ng
ng đi s c p:

c l i, n u c hai đ


ng s c p α 1 và α 2 đ u có đ dài l thì khi đó

α 3 = v1 v 2 v3 L vi −1 vi có đ dài ch n và đ

ng s c p:

α 4 = vi vi +1 L v j −1 v j v1 có đ dài l nên chu trình:
α 5 = v1 vi vi +1 L v j −1 v j v1 có đ dài ch n (đi u ph i ch ng minh).
3. Tính liên thông trong đ th vô h
3.1. nh ngh a: M t đ th vô h
m i c p đ nh phân bi t c a đ th .

ng

ng đ

c g i là liên thông n u có đ

ng đi gi a

V êduû25:

H

G

G: liên thông;

H: không liên thông.


Cho đ th G = (V,E) và v ∈ V. V' là t p h p các đ nh c a V liên thông v i v, E' là t p
h p các c nh n i 2 đ nh c a V'. Khi đó đ th G' = (V',E') g i là thành ph n liên thông
(connected component) c a G ch a v.
ng nhiên n u v và u liên thông trong G thì thành
ph n liên thông c a G ch a v c ng là thành ph n liên thông ch a u.
có 3 thành ph n liên thông.

Ví d 26:
3.2. nh lý 1.8:
ph n liên thông.
3.3.

th G=(V, E) là liên thông khi và ch khi G có duy nh t m t thành

nh c t và c u:

Ü nh c t: N u vi c xóa đi m t đ nh v ∈V và t t c các c nh liên thu c v i nó s t o
ra m t đ th con m i có nhi u thành ph n liên thông h n đ th xu t phát. Các đ nh v nh
th đ c g i là đ nh c t (cut point) hay đi m kh p.

thì e đ

Ü C u: N u trong đ th G ta b đi c nh e s t o ra nhi u thành ph n liên thông h n G
c g i là c u (brìdge).

Ví d 27: Tìm các đ nh c t và c u trong đ th :

a

d


b

c

G

f

g

e

h

Ü nh c t c a G: b, c, e.
Ü C u: ab, ce.
Chú ý: Không ph i đ th nào c ng có đ nh c t và c u.
3.4.

nh lý 1.9: Trong m i đ th G=(V, E) có ít nh t n = 02 đ nh ( V = n ≥ 2 ) . N u

∀ v1 , v 2 ∈ V th a d (v1 ) + d (v 2 ) ≥ n thì G là đ th liên thông.

H qu : Trong m i đ th G=(V, E) có n đ nh, n u m i đ nh v ∈V có d (v ) ≥

là đ th liên thông.
4. Tính liên thông trong đ th có h

n

thì G
2

ng
Trang 12


4.1. Liên thông m nh (Strongly connected)
th có h
a; ∀ a, b ∈ đ th .

ng G đ

c g i là liên thông m nh n u có đ

ng đi t a đ n b và t b đ n

V êduû28:

4.2. Liên thông y u (Weakly connected)
th có h

ng G đ

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

ng G đ

c g i là đ y đ n u đ th vô h


ng t

ng ng c a nó là

liên thông.
V êduû29:

th có h

ng c a nó là đ y đ .

4.3. nh lý 1.10: N u trong đ th G=(V, E) có đúng hai đ nh b c l thì hai đ nh này
ph i liên thông v i nhau.
Ch ng minh

Gi s đ th G=(V, E) có đúng hai đ nh b c l v và w nh ng hai đ nh này l i không
liên thông v i nhau. Khi đó v và w ph i thu c vào 2 thành ph n liên thông G1, G2 khác nhau
c a G. Ch ng h n v ∈ G1 và w ∈ G 2 . Theo gi thuy t do G ch có đúng 2 đ nh b c l nên trong
m i đ th con G1 và G2 ch có đúng m t đ nh b c l . Mâu thu n v i tính ch t s đ nh b c l
trong m t đ th là m t s ch n. V y v và w ph i liên thông v i nhau.
4.4.

nh lý 1.11: ( nh lý v đi u ki n c n và đ c a m t đ th l

th G = (V, E) là m t đ th l
đ dài ch n.

ng phân)

ng phân khi và ch khi m i chu trình c a nó đ u có


Ch ng minh
Ü Gi s G = (V, E) là m t đ th l

ng phân và t p đ nh V c a G đ

c chia

thành hai t p con V1 và V2. Khi đó, d c theo chu trình b t k c a G thì các đ nh thu c t p V1
và t p V2 s l n l t n m liên ti p và xen k nhau. Do đó, khi tr v đ nh xu t phát đ u tiên,
ta ph i đi qua m t s ch n các đ nh và do đó chi u dài c a chu trình là m t s ch n.
Ü Ng c l i, gi s r ng G là m t đ th có tính ch t là t t c các chu trình c a G đ u
có đ dài ch n. Ta s ch ng minh t t c các thành ph n liên thông c a G đ u là đ th l ng
phân và do đó G c ng là m t đ th l ng phân.

Th t v y, gi s r ng G1 là m t thành ph n liên thông c a G và v0 là m t đ nh c a G1.
V i m i đ nh v ∈ G1 ta ch n m t đ ng α n i v và v0. N u đ ng α có đ dài ch n thì ta
đ a đ nh v vào t p đ nh V1. ng c l i, n u α có đ dài l thì ta đ a v vào t p đ nh V2. S
phân lo i các đ nh c a G1 không ph thu c vào cách ch n đ ng đi α . Th t v y, n u có hai
đ ng α có đ dài ch n và α ' có đ dài l n i 2 đ nh v và v0 thì đ th G1 s có chu trình v i
đ dài l , mâu thu n v i tính ch t ban đ u là G ch có chu trình đ dài ch n.
V i cách thi t l p hai t p h p đ nh V1 và V2 này, các đ nh c a đ th G1 ho c thu c
t p h p đ nh V1 ho c thu c t p h p đ nh V2. Bây gi , ta ch ng minh r ng ch có các c nh n i
các đ nh không thu c cùng m t t p h p đ nh v i nhau mà thôi. Th t v y, gi s r ng có 2
đ nh v và u k nhau trong G1 thì chúng không th thu c cùng m t t p h p đ nh V1 ho c V2,
n u không ta có th đi t đ nh v0 đ n đ nh v r i đi đ n đ nh u b ng c nh vu r i tr v đ nh v0
Trang 13


b ng m t đ ng đi có đ dài l . i u này không x y ra trong đ th G. V y G là đ th l

phân v i hai t p đ nh r i nhau là V1 và V2 b ng cách mà ta đã xây d ng trên.

ng

VI. M t s phép bi n đ i đ th
1. H p c a hai đ th

H p c a hai đ th G1 = (V1,E1) và G2 = (V2,E2) là m t đ th G= (V, E) có t p h p
các đ nh là V = V1 ∪ V2 và t p h p các c nh là E = E1 ∪ E2.
Ký hi u: G =G1 ∪ G2.
a

b

c

a

b

d

G2

c

V êduû30:
d

G1


e

a

b

c

d

e

f

f

⇒

G = G1 ∪ G2
2. Phép phân chia s c p

Cho đ th G = (V,E), n u ta b đi m t c nh e = uv c a G và thêm vào m t
đ nh m i w cùng v i 2 c nh uw và wv thì phép toán trên đ

c g i là phép phân chia s c p.

Hai đ th G1 = (V1,E1) và G2 = (V2,E2) đ c g i là đ ng phôi (homeomorphic) n u
chúng có th nh n đ c t cùng m t đ th b ng m t dãy các phép phân chia s c p.


V êduû31:
G1

G2

G2 và G3 là đ ng phôi vì cùng nh n đ

G3

c t G1. Rõ ràng G2 và G3 không đ ng c u v i

nhau.
Chú ý: Hai đ th là đ ng phôi thì ch a ch c đ ng c u v i nhau.

Trang 14


Ch

ng II

CÁC BÀI TOÁN V
I. Chu trình và đ

NG I

ng đi Euler

1. Bài toán m đ u :
Bài toán 7 cây c u Königsberg: Thành ph Königsberg thu c Ph (bây gi g i là

Kaliningrad thu c C ng hòa Liên bang Nga) đ c chia thành b n vùng b ng các nhánh sông
Pregel. Các vùng này g m 2 vùng bên b sông, đ o Kneiphof và m t mi n n m gi a 2 nhánh
c a sông Pregel. Vào th k th XVIII, ng i ta đã xây 7 cây c u n i các vùng l i v i nhau
nh s đ sau:
C

A

D

B
Vào ch nh t, ng i dân đây th ng đi b d c theo các vùng trong thành ph . H t
h i “Có th xu t phát t i m t đi m nào đó trong thành ph , đi qua t t c 7 cây c u, m i cây
m t l n, r i tr v đi m xu t phát đ c không?”
Nhà toán h c Th y S Leonard Euler đã nghiên c u gi i bài toán này. L i gi i c a ông
đ c công b n m 1736. Bài toán này có th đ c coi là m t trong nh ng ng d ng đ u tiên
c a lý thuy t đ th .
Ta có th xây d ng đ th G = (V, E) mô t bài toán nh sau:
+ nh: L y các đi m trên m t ph ng hay trong không gian t ng ng v i các vùng
đ t trong s đ .
i t ng c a bài toán đây là m t vùng đ t trong s đ . V y, m i đ nh
v ∈V bi u di n cho m t vùng đ t.
th G s có 4 đ nh A, B, C, D t ng ng v i 4 vùng đ t.
+ C nh: Trong đ th G các đ nh v i và v j đ
cho m t chi c c u n i gi a hai vùng đ t.
gi a các vùng đ t trong s đ .

c n i v i nhau b ng m t c nh e đ i di n

th G s có 7 c nh t


Euler đã nghiên c u bài toán này, mô hình nó b ng
m t đa đ th , b n vùng đ c bi u di n b ng 4 đ nh, các c u
là các c nh nh đ th sau:

ng ng v i 7 chi c c u n i

C
A

D

B
Bài toán tìm đ ng đi qua t t c các c u m i c u không quá m t l n có th đ c phát
bi u l i b ng mô hình này nh sau: “T n t i hay không m t chu trình đ n trong đa đ th G=
(V, E) có ch a t t c các c nh?”
2.

nh ngh a

2.1. Chu trình Euler (
th G đ

th Euler)

Cho G = (V,E) là m t đa đ th liên thông. Chu trình đ n ch a t t c các c nh c a đ
c g i là chu trình Euler.
th có ch a m t chu trình Euler đ c g i là đ th Euler.
2.2.


ng đi Euler
Trang 17


Cho G = (V,E) là m t đa đ th liên thông.
ng đi Euler trong G là đ
ch a t t c các c nh c a đ th G.
a
b
e
có chu trình Euler: a, b, e, d, c, e, a.
Ví d 1:
th
d
c

b

a
c

th

Ví d 2:

d

Euler: a, c, d, a, b, e, d, b.
a
Ví d 3:


th

3. Chu trình và đ

e không có chu trình Euler nh ng có đ

ng đi

b
e

c

ng đi đ n

d

không có chu trình Euler và đ

ng đi Euler trong đ th vô h

ng đi Euler.

ng

Khi gi i bài toán c u Königsberg, Euler đã phát hi n ra các tiêu chu n đ kh ng đ nh
m t đa đ th có chu trình và đ ng đi Euler hay không?
3.1.


nh lý v chu trình Euler

M t đa đ th liên thông G =(V, E) có chu trình Euler khi và ch khi m i đ nh c a nó
đ u có b c ch n.
Ch ng minh
(⇒) Ta s ch ng minh n u đ th G có chu trình Euler thì m i đ nh c a G đ u có b c
ch n.
Th t v y, tr c tiên gi s G có chu trình Euler b t đ u t đ nh a và ti p t c b ng c nh
liên thu c v i a, ch ng h n ab, khi đó c nh ab góp m t vào deg (a). M i l n khi chu trình đi
qua m t đ nh, nó t ng thêm 2 đ n v cho b c c a đ nh đó. Vì chu trình đi vào m t đ nh b ng
m t c nh liên thu c và r i kh i đ nh này b ng m t c nh liên thu c khác. Cu i cùng chu trình
k t thúc đ nh mà nó xu t phát, do đó nó t ng thêm m t đ n v vào deg (a). Ngh a là deg (a)
ph i là m t s ch n. nh khác a c ng có b c ch n vì chu trình góp 2 đ n v vào b c c a nó
m i l n đi qua đ nh này. V y, m i đ nh c a G đ u có b c ch n.
(⇐) Gi s m i đ nh c a đa đ th liên thông G đ u có b c ch n. Ta s ch ng minh
t n t i m t chu trình Euler trong G.
Tr
sau:

a
f

Th t v y, ta s xây d ng m t chu trình đ n b t đ u t đ nh a tùy ý c a G. G i xo = a;
c tiên, ta ch n tùy ý c nh xox1, x1x2, ..., xn−1xn càng dài càng t t. Ví d , trong đ th G

b
c

d


Ta b t đ u t i a và ch n các c nh liên ti p ab, bc, cf, fa.
ng đi mà ta
ch n s k t thúc vì đ th có h u h n đ nh.
ng đi này b t đ u t i a v i
c nh có d ng ax và k t thúc t i a v i c nh có d ng ya.

e
i u này luôn x y ra vì m i l n đ ng đi qua m t đ nh b c ch n, nó ch dùng m t c nh đ
vào đ nh này và còn ít nh t m t đ nh đ ra kh i đ nh này.
ng đi v a nói trên có th đi qua
t t c các c nh ho c có th không. N u t t c các c nh đ c s d ng thì ta nh n đ c chu
trình Euler. N u không, ta g i H là đ th con nh n đ c t G b ng cách xóa các c nh đã
dùng và các đ nh không liên thu c v i
các c nh còn l i. Ch ng h n v i đ th trên, khi xóa đi chu trình a,
b, c, f, a kh i đ th trên, ta nh n đ c đ th con H.

c

d
e
Trang 18


Vì G là liên thông ⇒ H có ít nh t có m t đ nh chung v i chu trình v a b xóa. G i w
là đ nh đó (trong ví d trên là đ nh c). M i đ nh c a H có b c ch n vì t t c các đ nh c a G có
b c ch n và v i m i đ nh ta đã xóa đi t ng c p liên thu c đ t o ra H. L u ý r ng H có th
không liên thông. B t đ u t đ nh w ta xây d ng m t đ ng đi đ n b ng cách ch n càng
nhi u càng t t nh ta đã làm trong G.
ng này ph i k t thúc t i w. Ví d trong đ th H nêu
trên ta có chu trình con: c, d, e, c. Sau đó, ta t o m t chu trình trong G b ng cách ghép chu

trình trong H và chu trình ban đ u trong G (đi u này th c hi n đ c vì 2 chu trình có chung
đ nh w). Ti p t c quá trình này cho đ n khi t t c các đ nh đ c s d ng. Quá trình này ph i
k t thúc vì đ th có h u h n đ nh. Do đó, ta đã xây d ng đ c m t chu trình Euler.
Bây gi , tr l i bài toán 7 cây c u Königsberg: có th xu t phát t m t đ a đi m nào
đó trong thành ph , đi qua t t c các c u (m i c u đi qua đúng m t l n) và tr v đi m xu t
phát? Ta đã th y đ th bi u di n các c u Königsberg có 4 đ nh b c l . Do đó, theo đ nh lý
trên s không có chu trình Euler trong đ th này. i u này c ng có ngh a là bài toán 7 cây
c u Königsberg không có l i gi i. Hay nói cách khác, không có chu trình nào th a yêu c u
đ t ra.
3.2. Thu t toán Fleury tìm chu trình Euler
tìm m t chu trình Euler trong m t đa đ th có t t c các đ nh đ u b c ch n, ta có
th s d ng thu t toán Fleury nh sau:
Xu t phát t m t đ nh b t k c a đ th G và tuân theo hai qui t c sau:
Ü Qui t c 1: M i khi đi qua m t c nh nào thì xóa c nh đó đi, sau đó xóa đ nh cô l p
(n u có).
Ü Qui t c 2: Không bao gi đi qua m t c u, tr khi không còn cách đi nào khác đ di
chuy n.
Ví d 4: Tìm m t chu trình Euler trong đ th sau:

đ th :

A

B

C

D

H


G

F

E

Xu t phát t đ nh A, gi s ta ch n c nh AB, BC, CF. Sau đó xóa 3 c nh này, ta đ

A

B

C

D

H

G

F

E

c

n đây, ta không th ch n FG vì GF là m t c u, cho nên ta ch n FD, DC, CE, EF.
n đây, ta đ c đ th sau:


A

B

H

G

F

Ta không còn cách ch n nào khác, nên ph i ch n FG, GH, HB, BG, GA.
Nh v y, ta có chu trình Euler sau: A, B, C, F, D, C, E, F, G, H, B, G, A.
Ví d 5: Tìm m t chu trình Euler c a đ th sau:

B

C
D

A
F

E
Trang 19


D th y m t chu trình Euler: A, B, C, D, E, C, F, B, E, F, A.
3.3.

nh lý v đ


ng đi Euler

a đ th liên thông G =(V, E) có đ
và ch khi nó có đúng hai đ nh b c l .

ng đi Euler nh ng không có chu trình Euler khi

Ch ng minh:
(⇒) Gi s đa đ th G có đ
ch ng minh G có đúng 2 đ nh b c l .

ng đi Euler nh ng không có chu trình Euler. Ta s

Th t v y, gi s G có đ ng đi Euler t a đ n b, nh ng không có chu trình Euler.
C nh đ u tiên c a đ ng đi góp m t đ n v vào deg (a). Sau đó m i l n đ ng đi qua a l i
góp thêm 2 đ n v vào deg (a).
Ch c ch n đ ng đi không th k t thúc t i a, cho nên deg(a) là s l . C nh cu i cùng
c a đ ng đi góp m t đ n v vào deg(a) và m i l n đi qua b, nó c ng góp 2 đ n v vào
deg(b). Do đó, deg(b) là s l . Các đ nh trung gian đ u có b c ch n vì m i l n đ ng đi t i r i
l i đi nên t ng hai đ n v cho b c c a đ nh đó. V y, đ th đã cho có đúng 2 đ nh b c l .
đ

(⇐) Gi s đa đ th liên thông G có đúng 2 đ nh b c l . Ta s ch ng minh G có
ng đi Euler.

Th t v y, gi s G có đúng 2 đ nh b c l là a và b. Khi đó trong đ th m i G' = G ∪
ab, t t c các đ nh đ u có b c ch n. Do đó, theo đ nh lý Euler, t n t i m t chu trình Euler
trong G'. Trong chu trình này b c nh ab, ta đ c đ ng đi Euler trong G.
Nh v y, trong m t đa đ th liên thông có 2 đ nh b c l thì đ

th đó s nh n 2 đ nh b c l làm các đi m đ u mút.

ng đi Euler trong đ

Ví d 6: Xét đ th sau:

a

b

c

d

g

f

e

G

Trong G có 2 đ nh b c l là g và e. Do đó, m t đ ng đi Euler trong G s nh n g và e
làm 2 đ nh đ u mút. Ch ng h n: g, a, b, g, f, b, c, f, e, c, d, e.
Ví d 7: Ch ng minh r ng ta có th x p t t c các con c c a b c
m t vòng khép kín.

ôminô thành

(Xem nh bài t p - Sinh viên t ch ng minh).

4. Chu trình và đ

ng đi Euler đ i v i đ th có h

ng

4.1. nh lý v chu trình Euler:
th có h ng G = (V, E) có ch a m t chu trình
Euler khi và ch khi G là liên thông y u, đ ng th i b c vào và b c ra c a m i đ nh là b ng
nhau.
Ch ng minh: T ng t đ nh lý Euler đ i v i đ th vô h
Sinh viên t ch ng minh).

a
Ví d 7:

ng (Xem nh bài

t p-

b
có chu trình Euler: a, b, c, a, d, c, a.

th

d

c
a


Ví d 8:

th

c

b

không có chu trình Euler.
Trang 20


4.2. nh lý v đ ng đi Euler: Cho G =(V,E) là m t đa đ th có h ng. G có
đ ng đi Euler nh ng không có chu trình Euler ⇔ G là liên thông y u, đ ng th i b c vào và
b c ra c a các đ nh là b ng nhau, tr 2 đ nh, m t đ nh có b c vào l n h n b c ra m t đ n v ,
còn đ nh kia có b c vào nh h n b c ra m t đ n v .
Ch ng minh: T ng t đ nh lý Euler đ i v i đ th vô h
Sinh viên t ch ng minh).

a
Ví d 9:

th

t p-

b

d


II. Chu trình và đ

ng (Xem nh bài

c

có đ

ng đi Euler: a, b, c, a, d, c.

ng đi Hamilton

1. Chu trình Hamilton

1.1.

nh ngh a

M t chu trình s c p đi qua t t c các đ nh c a đ th G =(V,E) (đi qua m i đ nh đúng
m t l n) đ c g i là chu trình Hamilton.
th G=(V,E) có ch a chu trình Hamilton đ c
g i là đ th Hamilton.
c
b
d
có chu trình Hamilton là: a, b, c, d, e, a.
Ví d 11:
th
a
e


a

b

th

không có chu trình Hamilton vì m i chu trình ch a m i
c
d
đ nh c a đ th đ u ph i đi qua c nh ab 2 l n.
Ví d 12:

1.2. i u ki n đ đ t n t i chu trình Hamilton
nh lý Ore (1960): Cho G = (V,E) là m t đ n đ th liên thông v i n đ nh
(n ≥ 3)
và n u: deg(v) + deg(w) ≥ n v i m i c p đ nh không li n k v, w trong G. Khi đó G có chu
trình Hamilton.
Ch ng minh: S d ng ph

ng pháp ch ng minh ph n ch ng.

Gi s G th a deg(v) + deg(w) ≥ n; ∀v,w không li n k trong G nh ng G không có
chu trình Hamilton. Khi đó ta có th ghép thêm vào G nh ng c nh cho đ n khi nh n đ c m t
đ th con H c a Kn sao cho H không có chu trình Hamilton, nh ng v i m i c nh e ∈ Kn
nh ng e ∉ H, ta có (H + e) có chu trình Hamilton. Vi c ghép thêm c nh vào G là hoàn toàn
th c hi n đ c và không nh h ng gì đ n đi u ki n c a gi thi t.
Do H ≠ Kn nên t n t i a, b ∈ V sao cho ab ∉ H nh ng H + ab có chu trình Hamilton
C. B n thân H không có chu trình Hamilton mà H + ab có chu trình Hamilton ⇒ ab ∈ C. Gi
s ta li t kê các đ nh c a H trong chu trình C nh sau:

a(=v1) → b(=v2) → v3 → v4 → ... → vn-1 → vn; 3 ≤ i ≤ n.
Khi đó, n u c nh bvi ∈ H, ta có th k t lu n avi-1 ∉ H vì n u c hai bvi và avi-1 cùng
n m trong H, ta có chu trình:

Trang 21


b → vi → vi+1 → ... → vn-1 → vn → a → vi-1 → vi-2 → ... → v3
Chu trình này n m trong H, đi u này mâu thu n vì H không có chu trình Hamilton. Vì
v y, ∀ vi (3 ≤ i ≤ n) ch có m t trong 2 c nh: bvi ho c avi-1 n m trong H.
Do đó:
V i

degH(a) + degH(b) < n.
degH(a): b c c a a trong H.

Ta có ∀ v ∈ V: degH(v) ≥ degG(v) = deg(v) (vì G là đ th con c a H)
⇒ v i c p đ nh không li n k trong G: a, b ta có: deg(a) + deg(b) < n.
i u này mâu thu n v i gi thi t: deg(v) + deg(w) ≥ n; ∀ v, w không li n k .
V y, G có ch a chu trình Hamilton.
Ü H qu : (

nh lý Dirac, 1952)

N u đ n đ th G = (V,E) có n đ nh (n ≥ 3) và deg(v) >

n
; ∀ v ∈ V thì G có chu trình
2


Hamilton.
1.3.

nh lý Pósa v chu trình Hamilton
n −1
ta có
2
ng h p n là s l ta có không quá

G = (V, E) là m t đ n đ th có V = n ≥ 3 . Gi s r ng v i m i s 1 ≤ k <

không quá k - 1 đ nh có b c không l n h n k, và trong tr
n −1
n −1
đ nh có b c không v t quá
. Khi đó đ th G có m t chu trình Hamilton.
2
2
Ch ng minh
Chúng ta s ch ng minh đ nh lý này b ng ph

ng pháp ph n ch ng.

Gi s G không có chu trình Hamilton, ta có th gi s r ng n u thêm m t c nh b t k
n i 2 đ nh không k nhau c a G thì đ th thu đ c s có m t chu trình Hamilton.
th G
nh v y đ c g i là có tính ch t c c đ i.
N u G không th a tính ch t c c đ i, ta có thêm vào G các c nh m i b ng cách n i các
c p đ nh không k nhau, lúc đó ta s thu đ c m t đ th không có chu trình Hamilton có tính
ch t c c đ i nh đã mô t

trên và v n không nh h ng gì đ n gi thuy t c a bài toán ban
đ u.
Do tính ch t c c đ i c a đ th nên gi a hai đ nh tu ý không k nhau c a đ th luôn
t n t i m t đ ng Hamilton n i hai đ nh này. Có th đó là đ ng Hamilton thu đ c t chu
trình Hamilton xu t hi n khi thêm vào m t c nh n i hai đ nh không k nhau này.
Ký hi u (v1 , v 2 , L , v n ) là m t đ ng Hamilton (không khép kín) trong G. Cho
k = 2, 3, L , n − 1 . Ta có n u vk đ c n i v i v1 b i m t c nh thì vk-1 không đ c n i v i vn
b i c nh nào c , n u không thì:

(v1 , v 2 , L , v k −1 , v n , v n −1 , L , v k +1 , v k , v1 )
là m t chu trình Hamilton. T đó ta có:
d (v1 ) + d (v n ) ≤ n − 1

Trang 22


n −1
k v i t t c các đ nh b c không nh h n
2
n
n
. Th t v y, gi s có đ nh b c không nh h n , không m t tính t ng quát gi s đ nh v1
2
2
n −1
n
không k v i đ nh vn có b c d (v n ) ≥ . Gi s (v1 , v 2 , L , v n ) là m t đ ng
v i d (v1 ) ≥
2
2

Hamilton n i v1 v i vn. Ký hi u các đ nh lân c n c a v1 là v i1 , v i2 , L , v iS v i s = d (v1 ) . Khi

Trong đ th G m i đ nh b c không nh h n

đó vn không k v i v i1 −1 , v i2 −1 , L , v iS −1 , và ta có
n
≤ d (v n ) ≤ (n − 1 − s ) = (n − 1 − d (v1 ))
2

Suy ra:

n
n −1
≤ d (v n ) ≤ (n − 1 − s ) = (n − 1 − d (v1 )) ≤
2
2

(!)

n −1
, n u không G có chu trình Hamilton theo
2
n
đ nh lý Dirac. Ký hi u ∆ là b c cao nh t trong các đ nh c a G có b c nh h n . và p là s
2
n
n −1
. Ta s
các đ nh có b c nh h n . Khi đó theo gi thuy t c a đ nh lý ta có p ≤ ∆ ≤
2

2
n −1
ch ng minh r ng p < ∆ <
.
2

Trong G t n t i nh ng đ nh có b c ≤

Ký hi u q là s các đ nh có b c l n h n ∆ , ta có:
q=n− p≥n−∆>n−

n n
= > ∆.
2 2

Gi s u1 là m t đ nh có b c là ∆ , trong s n − ∆ > ∆ đ nh có b c l n h n

n
t n t i ít
2

n −1
đ
2
n −1
không thì u1 ph i k v i un nh trên đã ch ng minh. Do đó, ta có: d (u1 ) = ∆ <
.
2

nh t m t đ nh g i là un không k v i u1. Khi đó b c c a u1 không th là


Theo gi thuy t c a đ nh lý, s đ nh có b c không v
n −1
. Ta có p < ∆ .
∆<
2
Xét đ

c, n u

t quá ∆ s nh h n ∆ , do đó

ng Hamilton (u1 , u 2 , L , u n ) n i u1 v i un. Ký hi u các đ nh lân c n c a

u1 là u i1 , u i2 , L , u iS v i s = ∆ = d (u1 ) . Khi đó có m t trong các đ nh u i1 −1 , u i2 −1 , L , u iS −1 g i là
n −1
. ph n trên ta đã ch ng minh đ c khi đó u i 0−1 ph i k v i
2
c chu trình Hamilton: u1u 2 L u i0 −1u n u n −1 L u i0 là đi u vô lý. Mâu thu n này đã

u i0 −1 có b c là d (u i 0 −1 ) ≥

un. Ta đ

(

)

k t thúc ph n ch ng minh c a ta.
2. Ph


ng pháp tìm chu trình Hamilton

Cho m t đ th G =(V,E).
theo 4 qui t c sau:

tìm m t chu trình Hamilton trong đ th G, ta th c hi n

Ü Qui t c 1: N u t n t i m t đ nh v c a G có d (v ) ≤ 1 thì đ th G không có chu trình
Hamilton.
Trang 23


Ü Qui t c 2: N u đ nh v có b c là 2 (d (v ) = 2) thì c 2 c nh t i v đ u ph i thu c chu
trình Hamilton.
Ü Qui t c 3: Chu trình Hamilton không ch a b t k chu trình con th c s nào.
Ü Qui t c 4: Trong quá trình xây d ng chu trình Hamilton, sau khi đã l y 2 c nh t i
m t đ nh v đ t vào chu trình Hamilton r i thì không th l y thêm c nh nào t i v n a, do đó có
th xóa m i c nh còn l i t i v.
Ví d 13: Tìm m t chu trình Hamilton c a đ th :
Xu t phát t đ nh a. Ta có deg(a) = 3, cho nên ta ch gi
l i 2 c nh liên thu c v i a: ta ch n ab và ad, do đó ta b

a
d
g

c nh ae (theo quy t c 4). T
đó ta có đ th :


a

c

d

b
e

g

h

i

F

J

i

h

ng t t i b, ta b c nh be t i c ta b c nh ce (theo quy t c 4). Khi

a

B

f


T i đ nh f, ta b c nh fe. T i đ nh i ta b c nh ie, t i đ nh h ta b
c nh hg (theo quy t c 4) t i đ nh e, ta b t bu c đi theo eg, gd
(theo quy t c 2). T i đ nh a ta ph i ch n c nh da (theo quy t c
2). V y, ta có chu trình Hamilton: a, b, c, f, i, h, e, g, d, a.

f

Ví d 14:

c

b
e

th

b
c

d

e

f

không có chu trình Hamilton vì: deg(f) = 1.

Ví d 15: Ch ng minh r ng đ th sau không có chu trình Hamilton:
A

+ Gi s đ th có m t chu trình Hamilton H.
D
C
+ Vì d ( A) = d (G ) = 2 nên H ph i ch a các c nh
AB, AC, GE và GI (theo qui t c 2).
E
H
+ Xét đ nh I: Do tính ch t đ i x ng c a hình v ta
G
có th gi s c nh IK ∈ H , xóa c nh IJ (theo
qui t c 4).
I
K
+ Xét đ nh J: Bây gi d (J ) = 2 nên hai c nh JF và JK ph i thu c vào H.

+ Xét đ nh K: ta đã ch n 2 c nh KI và KJ nên xóa KH (theo qui t c 4) và xóa c nh EF
(do quy t c 3).
th bây gi tr thành:
D dàng th y các c nh FB, HE, HC ph i
Thu c chu trình Hamilton H. Ta nh n đ
A
B

C
D
E

H

c


M t chu trình con th t s trong H (Vô lý).
Theo qui t c 2 ta có các
c nh FB, HE, HC ph i thu c chu
trình Hamilton H. Khi đó, ta có
m t chu trình conA th t s trong
H. V y đ th không có chu trình
B
Hamilton.
C

F

D

G

Trang 24

I

E
F

H