Đ I H C QU C GIA HÀ N I
TRƯ NG Đ I H C KHOA H C T NHIÊN
———-

NGUY N TH MINH THƯƠNG

LÝ THUY T Đ TH
V I CÁC BÀI TOÁN PH THÔNG

LU N VĂN TH C SĨ KHOA H C

HÀ N I - 2015


Đ I H C QU C GIA HÀ N I
TRƯ NG Đ I H C KHOA H C T NHIÊN
———-

NGUY N TH MINH THƯƠNG

LÝ THUY T Đ TH
V I CÁC BÀI TOÁN PH THÔNG

Chuyên ngành: Phương pháp toán sơ c p
Mã s : 60.46.01.13

LU N VĂN TH C SĨ KHOA H C

Ngư i hư ng d n khoa h c:
GS.TS Đ ng Huy Ru n


1.8

tính ch t . . . . . . . . . . . . .
Xích, chu trình, đư ng, vòng . . . . . . . . . . .
1.4.1 Xích, chu trình . . . . . . . . . . . . . .
1.4.2 Đư ng, vòng . . . . . . . . . . . . . . . .
1.4.3 M t s tính ch t . . . . . . . . . . . . .
Đ th liên thông . . . . . . . . . . . . . . . . .
1.5.1 Đ nh nghĩa . . . . . . . . . . . . . . . .
1.5.2 Tính ch t . . . . . . . . . . . . . . . . .
S n đ nh trong, s n đ nh ngoài . . . . . . .
1.6.1 S n đ nh trong . . . . . . . . . . . . .
1.6.2 S n đ nh ngoài . . . . . . . . . . . . .
1.6.3 Các thu t toán tìm s n đ nh trong, s
ngoài. . . . . . . . . . . . . . . . . . . .
Nhân c a đ th và ng d ng vào trò chơi . . . 1.7.1
Đ nh nghĩa . . . . . . . . . . . . . . . . 1.7.2 Tính ch
t . . . . . . . . . . . . . . . . . 1.7.3 Trò chơi
Nim . . . . . . . . . . . . . . . 1.7.4 Trò chơi b c các
v t . . . . . . . . . . . Cây và b
i . . . . . . . . . . . . . . . . . . . . . 1.8.1 Đ nh nghĩa .
. . . . . . . . . . . . . . . 1.8.2 Đ c đi m c a cây và b
i.........

. ....
M t s d ng đ
. ....
B c c a đ nh
. ....
8

..... ..... 22
.....
23
24
29
29
30


1


2 M t s bài toán đ th cơ b n
2.1 Bài toán v đư ng đi . . . . . . . . . . . . . . . .
2.1.1 Đư ng đi Euler - Chu trình Euler. . . . . .
2.1.2 Đư ng đi Hamilton - Chu trình Hamilton.
2.2 Bài toán tô màu đ th . . . . . . . . . . . . . . .
2.2.1 Đ nh nghĩa . . . . . . . . . . . . . . . . .
2.2.2 M t s tính ch t . . . . . . . . . . . . . .
2.2.3 Thu t toán tô màu đ nh. . . . . . . . . . .
3

.
.
.
.
.
.
.


3.7 Bài toán liên quan đ n cây. . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

33
33
33
40
43
43
43
53
54
54
54
54
55
58
63
74
76
76
80
82

Chương 3 ng d ng lý thuy t đ th vào gi i toán ph thông.
Lu n văn đư c hoàn thành dư i s hư ng d n, giúp đ t n tình c a GS.TS
Đ ng Huy Ru n, tác gi xin bày t s kính tr ng và lòng bi t ơn sâu s c t i th
y.
Tác gi cũng xin g i l i c m ơn chân thành đ n Ban giám hi u cùng các th
y cô giáo khoa Toán - Cơ - Tin, Trư ng Đ i h c Khoa H c T Nhiên - Đ i H
c Qu c Gia Hà N i đã t o đi u ki n, d y b o và dìu d t tác gi trong nh ng
năm h c v a qua.
Xin chân thành c m ơn s giúp đ c a b n bè, ngư i thân trong th i gian h
c t p và làm lu n văn.
Do kh năng nh n th c c a b n thân tác gi , lu n văn còn nhi u h n ch ,
thi u sót. Tác gi kính mong các ý ki n ch b o c a quý th y cô cùng s
đóng góp c a các b n đ c.
Tác gi xin chân thành c m ơn!
Hà N i, tháng 6 năm 2015

3


Chương 1
Đ i cương v đ th
1.1

Đ nh nghĩa đ th

T p h p X = ∅ các đ i tư ng và b E các c p s p th t và không s p th t
các ph n t c a X đư c g i là m t đ th , đ ng th i đư c ký hi u b ng G(X, E)
(ho c G = (X, E) ho c G(X)).

Hình 1.1: Ví d

đ nh chung đó là đ nh đ u hay đ nh cu i c a cung a, đ nh đ u hay đ nh cu
i c a cung b).
Ví d 1.1. Cho đ th h n h p có khuyên G(X, E) v i t p đ nh
X = {x1, x2, x3, x4, x5, x6, x7},
t p c nh và cung
E = {x1, x2; x2, x3; x4, x6; x5, x6; x3, x3; x1, x6; x5, x5}
= {a1

a2

a3

a4

a5

b1

trong đó a1, a2, a3, a4, a5 là các c nh; b1, b2 là các cung.

Hình 1.2

5

b2},


1.2

M t s d ng đ th đ c bi t

n u t p đ nh X c a nó đư c phân thành hai t p con r i nhau X1, X2
(X1 X2 = X và X1 X2 = ∅) và m i c nh đ u có m t đ u thu c X1 còn đ u
kia thu c X2.Khi đó G = (X, E) còn đư c ký hi u b ng G = (X1, X2, E).

Hình 1.5: Đ

th hai m ng

Đ th (đa đ th ) G = (X, E) đư c g i là đ th (đa đ th ) ph ng, n u nó có
ít nh t m t d ng bi u di n hình h c tr i trên m t m t ph ng nào đó, mà các
c nh c a đ th ch c t nhau đ nh.
Đ th (đa đ th ) G = (X, E) đư c g i là h u h n, n u s đ nh c a nó h u h
n, t c t p X có l c lư ng h u h n.
Đ th (đa đ th ) G = (X, E) đư c g i là vô h n, n u s đ nh c a nó là vô h
n.
Đ th (đa đ th ) v i s c nh thu c m i đ nh đ u h u h n đư c g i là đ th
(đa đ th ) h u h n đ a phương.
M t đ th hay đa đ th h u h n thì nó cũng h u h n đ a phương. Cho
Y ⊆ X, Y = ∅; H ⊆ E, F = E ∩ (Y ⋅ Y ) và V = (X ⋅ X)/E.
Đ th G1(Y, F ) đư c g i là đ th con, còn G2(X, H) là đ th b
ph n c a đ th G(X, E).
Đ th G (X, V ) đư c g i là đ th bù c a đ th G(X, E). Đ th có
hư ng G(X, E) đư c g i là đ th đ i x ng n u
∀x, y ∈ X, (x, y) ∈ E ⇒ (y, x) ∈ E
Trong đ th đ i x ng tùy ý, hai đ nh k nhau luôn luôn đư c n i
b ng hai cung ngư c chi u nhau. Đ đơn gi n, trong trư ng h p này ngư i
ta quy ư c thay hai cung nói trên b ng m t c nh n i gi a x và y.
Đ th có hư ng G(X, E) đư c g i là đ th ph n đ i x ng n u
∀x, y ∈ X, (x, y) ∈ E ⇒ (y, x) ∈ E /
7

ng E+(x).
8


Hình 1.7

Ví d 1.3. Trong hình 1.7 ta có:
m (1) = 1, m (2) = 2, m (3) = 2, m (4) = 0, m (5) = 1, m (6) = 1;
m (1) = 1, m (2) = 1, m (3) = 1, m (4) = 1, m (5) = 1, m (6) = 2;
E−(4) = {∅}, E+(4) = {g};
E−(6) = {f }, E+(6) = {e, d}.

1.3.3

M t s tính ch t

Đ nh lí 1.3.1. Trong đ th hay đa đ th tùy ý, t ng s b c c a t t c
các đ nh bao gi cũng g p đôi s c nh.
Ch ng minh.
Th t v y, khi tính b c c a các đ nh m i c nh vô hư ng h c có hư ng đ u
đư c tính m i đ u đúng m t l n, do đó t ng s b c c a t t c các đ nh bao gi
cũng g p đôi s c nh.
Đ nh lí 1.3.2. Trong đ th hay đa đ th tùy ý, s đ nh b c l luôn luôn
là s ch n.
Ch ng minh.
Gi s đ th (đa đ th ) G = (X, E) có n đ nh, m c nh
X = {x1, x2, ..., xk, xk+1, ..., xn−1, xn},
Các đ nh x1, x2, ..., xk b c l và xk+1, ..., xn−1, xn b c ch n.

9

b c n − 1. Lo i x, y và t t c các c nh thu c chúng kh i đ th
G, ta đư c đ th con G1 có n − 2 đ nh. Theo đ nh lý 1.3 trong G1 có
hai đ nh cùng b c, ch ng h n u,v.
1) N u x, y cùng b c 0, thì u,v trong G không k v i x,y nên u,v trong G
đ ng th i là hai đ nh cùng b c. Như v y, đ th G ph i có ít nh t hai c p đ nh
cùng b c.

10


2) N u x, y đ u b c n − 1. Khi đó, m i đ nh u, v đ u k đ ng th i v i
x, y nên trong đ th G các đ nh u, v cũng cùng b c. Như v y, đ th G ph i
có ít nh t hai c p đ nh cùng b c.
C hai trư ng h p có th đ u d n t i mâu thu n v i tính ch t: Đ th G có
duy nh t m t c p đ nh cùng b c, nên x, y không th cùng b c 0 h c cùng
b cn−1.
Kh ng đ nh đư c ch ng minh.
Đ nh lí 1.3.5. S đ nh b c n − 1 trong đ th G v i n đ nh (n ≥ 4), mà
b n đ nh tùy ý có ít nh t m t đ nh k v i ba đ nh còn l i, không nh hơn n −
3.
Ch ng minh.
1) N u G là đ th đ y đ , thì kh ng đ nh là hi n nhiên.
2) N u G có c p đ nh duy nh t không k nhau. Khi đó, trong G có
n − 2 đ nh b c n − 1
3) N u G có hai c p đ nh không k nhau, thì chúng ph i có đ nh chung.
Th t v y, gi i s A, B; I, D là hai c p đ nh không k nhau. N u hai c p đ
nh này không có đ nh chung, thì trong 4 đ nh A, B, I, D không có đ nh
nào k v i ba đ nh còn l i.
Như v y, mâu thu n v i gi thi t, nên hai c p đ nh A, B; I, D ph i có hai
đ nh trùng nhau, ch ng h n B ≡ I.

Kh ng đ nh đư c ch ng minh.
Đ nh lí 1.3.7. Trong đ th G = (X, E) v i ít nh t kn + 1 đ nh, m i
đ nh có b c không nh hơn (k − 1)n + 1 luôn t n t i đ th con đ y đ g m k + 1 đ
nh.
Ch ng minh.
Ta s ch ng minh đ nh lý b ng phương pháp quy n p theo k. 1)
V i k = 1 kh ng đ nh hi n nhiên đúng.
2) V i k = 2 có th làm ch t ch hơn gi thi t. N u đ th 2n + 1
đ nh mà m i đ nh có b c không nh hơn n, thì nó có đ th con 3 đ nh đ
yđ .
Th t v y, xét đ nh x tùy ý, còn y là m t trong các đ nh k v i x. T ng s đ
nh k v i x và y không nh hơn 2n, nhưng s đ nh khác x và y ch là 2n − 1.
B i v y, ph i có ít nh t m t đ nh z đư c tính hai l n. Khi đó, x, y, z t o thành m t đ
th con đ y đ ba đ nh.
3) Gi s kh ng đ nh trên đúng v i k. C n suy ra tính đúng đ n c a kh ng
đ nh đ i v i k + 1.
Theo gi thi t, thông đ th G g m (k + 1)n + 1 đ nh, s đ nh k v i đ nh x
tùy ý không nh hơn kn + 1, nên s đ nh không k v i x s không vư t quá
n. B i v y, m i đ nh y k v i x thì nó k v i nhi u nh t n đ nh không k v i đ
nh x. Do đó, đ nh y ph i k v i ít nh t
kn + 1 − n = (k − 1)n + 1 đ nh k v i đ nh x. Xét đ th con G1 g m các
đ nh k v i x. Đ th con G1 có ít nh t kn + 1 đ nh và m i đ nh c a nó k v i ít
nh t (k − 1)n + 1 đ nh thu c G1, nên theo gi thi t quy n p,
12


trong G1 có đ th con đ y đ G2 g m k + 1 đ nh. Vì đ nh x k v i t ng
đ nh thu c G2, nên đ nh x k t h p v i các đ nh thu c G2 l p thành m t
đ th con đ y đ g m k + 2 đ nh thong đ th G.
Kh ng đ nh đư c ch ng minh.

α5

= [5, 1, 4, 2, 1] là m t dây chuy n không sơ c p.
= [1, 2, 3, 4] là m t dây chuy n sơ c p.
= [1, 5, 1] và α4 = [1, 2, 3, 4, 1] là các chu trình đơn và sơ c p.
= [1, 2, 4, 3, 2, 1] là chu trình đơn nhưng không sơ c p.

1.4.2

Đư ng, vòng

Gi s G(X, E) là m t đ th hay đa đ th có hư ng. Dãy đ nh β
c a G(X, E) :

β = [x1, x2, ..., xi, xi+1, ..., xm−1, xm]
đư c g i là m t đư ng hay m t đư ng đi n u ∀i(1 ≤ i ≤ m − 1), đ nh
xi là đ nh đ u, còn đ nh xi+1 là đ nh cu i c a m t cung nào đó.
T ng s v trí c a t t c các cung xu t hi n trong β đư c g i là đ
dài c a đư ng β, ký hi u: |β|.
Đ nh x1 đư c g i là đ nh đ u còn xm là đ nh cu i c a đư ng β. Ngư i
ta còn nói r ng, đư ng β xu t phát t đ nh x1 và đi t i xm. Đư ng β còn đư c ký
hi u b ng β[x1, xm].
M t đư ng có đ nh đ u và đ nh cu i trùng nhau đư c g i là m t vòng.
Đư ng (vòng) β đư c g i là đư ng (vòng) đơn (sơ c p hay cơ b n),
n u nó đi qua m i c nh (m i đ nh) không quá m t l n.
Ví d 1.5. Cho đ th có hư ng (hình 1.9):
β1 = [1, 2, 4, 3, 5, 1] là m t vòng đơn và sơ c p.
β2 = [1, 4, 3, 5] là m t đư ng đơn và sơ c p. β3 = [1,
4, 2, 5] không ph i là đư ng.
β4 = [1, 2, 4, 3, 2, 5] là m t đư ng đơn nhưng không sơ c p.

15


Ch ng minh.
Gi s α là m t trong nh ng xích sơ c p có đ dài c c đ i

α = [x1, x2, ..., xi−1, xi, xi+1, ..., xj−1, xj, xj+1, ..., xk−1, xk]
Vì α có đ dài c c đ i, mà b c c a x1 không nh hơn 3, nên x1 ph i
k v i hai đ nh khác thu c α: xi, (3 ≤ i ≤ k), xj, (3 ≤ j ≤ k). Khi đó có
hai chu trình sơ c p:

α1 = [x1, x2, ..., xi−1, xi, x1]
α2 = [x1, x2, ..., xi−1, xi, xi+1, ..., xj−1, xj, x1]
1) N u m t trong hai chu trình α1, α2 có đ dài ch n thì kh ng đ nh
đư c ch ng minh.
2) N u ngư c l i, c hai chu trình α1, α2 đ có đ dài l .
Khi đó xích: α3 = [x1, x2, ..., xi−1, xi] có đ dài ch n,
còn xích α4 = [xi, xi+1, ..., xj−1, xj, x1] có đ dài l ,
nên chu trình α5 = [x1, xi, xi+1, ..., xj−1, xj, x1] có đ dài ch n.
Kh ng đ nh đư c ch ng minh.

1.5
1.5.1

Đ th liên thông
Đ nh nghĩa

Hai đ nh x, y c a đ th G = (X, E) đư c g i là c p đ nh liên thông
n u ho c gi a x và y có ít nh t m t xích n i v i nhau , ho c t n t i ít nh t m
t đư ng đi t x sang y ho c t y sang x.

a, b c a đ th ta đ u có:
m(a) + m(b) ≥ n

(1)

Nhưng a, b không liên thông. Khi đó trong đ th G t n t i hai thành
ph n liên thông:
G1 ch a a và có n1 đ nh, còn G2 ch a b và có n2 đ nh.

17


đó

Vì G1, G2 là các thành ph n liên thông c a G nên n1 + n2 ≤ n Khi

m(a) + m(b) ≤ (n1 − 1) + (n2 − 1) = n1 + n2 − 2 ≤ n − 2 < n

(2)

Như v y, (1) và (2) mâu thu n nhau, nên đ th G ph i liên thông.
Kh ng đ nh đư c ch ng minh.
T đ nh lý trên suy ra h qu sau:
H qu 1.5.1. Đ th , mà b c c a m i đ nh không nh hơn n a s đ nh,
là đ th liên thông.
Đ nh lí 1.5.2. N u đ th có đúng hai đ nh b c l , thì hai đ nh này ph i
liên thông.
Ch ng minh.
Gi s đ th G(X, E) có đúng hai đ nh b c l và hai đ nh đó là a và b.
Gi s a, b không liên thông v i nhau.



3. S n đ nh trong
S ph n t c a m t trong nh ng t p n đ nh trong có l c lư ng l n
nh t đư c g i là s n đ nh trong c a đ th G, đ ng th i đư c ký hi u b ng
α(G).
1.6.2

S

n đ nh ngoài

1. T p n đ nh ngoài
Gi s có đ th G(X, E). T p con B ⊆ X các đ nh c a đ th G
đư c g i là t p n đ nh ngoài, n u v i m i đ nh x thu c t p X∴B đ u t n t i đ
nh y ∈ B, đ ho c t x sang y có cung ho c c p đ nh x, y đư c n i b ng m t c nh.
2. Tính ch t
N u B là t p n đ nh ngoài, thì m i t p ch a B đ u n đ nh ngoài.
3. S n đ nh ngoài
S ph n t c a m t trong nh ng t p n đ nh ngoài có l c lư ng bé
nh t đư c g i là s n đ nh ngoài c a đ th G, đ ng th i đư c ký hi u b ng
β(G).
Ví d 1.7. Cho đ th G như hình 1.12. Hãy tìm t t c các t p n đ nh
trong,s n đ nh trong và s n đ nh ngoài c a đ th G.
Các t p n đ nh trong

Hình 1.12

19



n đ nh ngoài.

n đ nh trong.

- Bư c 1: Tìm các t p n đ nh trong có 2 ph n t b ng cách xét t t
c t h p ch p 2 c a n ph n t (n s các đ nh), ki m tra nh ng t p nào
mà ph n t tương ng không k nhau thì t p đó là n đ nh trong;
- Bư c 2: Duy t t ng t p có 2 ph n t và b sung thêm ph n t th
3 và ki m tra t ng c p như bư c 1, t p nào th a mãn ta đư c t p n đ nh
trong 3 ph n t .
.........
- Bư c k: Gi s ta đã tìm đư c m t p con n đ nh trong có k+1
ph n t
+ Duy t t ng t p và b sung vào các t p đó thêm 1 ph n t . + N u
không có t p nào b sung đư c n a thì d ng.

20


1.6.3.2. Thu t toán tìm s

n đ nh ngoài.

Xét G(X, E) v i X = {x1, x2, ..., xn}
- Bư c 1: Xác đ nh các t p ∆(xi), i = 1, 2, ..., n
v i ∆(xi) = {xi và các đ nh k v i xi}
- Bư c 2: T các t p ∆(x1), ∆(x2), ..., ∆(xn) ta tìm t p B = {xk1, xk2, ..., xkm} sao cho
∆(xk1) ∪ ∆(xk2) ∪ ... ∪ ∆(xkm) = X.
Khi đó B là t p n đ nh ngoài c c ti u.


Đ nh lí 1.7.1. N u đ th G(X, U ) có s
đ nh ngoài thì nó không có nhân.

n đ nh trong nh hơn s

n

Ch ng minh.
Gi s trong đ th G(X, U ),

α(G) < β(G)

(1)

nhưng l i có nhân và S là m t trong nh ng nhân c a đ th G. Khi đó,
theo đ nh nghĩa:

α(G) = max{|A|A ∈ H(G)} ≥ |S| ≥ min{|B|B ∈ K(G)} = β(G)

(2)

trong đó, H(G) là t p g m các t p n đ nh trong, còn K(G) là t p g m
các t p n đ nh ngoài c a đ th G.
So sánh (1) và (2) đi t i mâu thu n, nên G không th có nhân. Đ
nh lý đư c ch ng minh.
Đ nh lí 1.7.2. N u S là nhân c a đ th G(X, U ), thì nó cũng là t p n
đ nh trong c c đ i.
Ch ng minh.
Gi s S là nhân c a đ th G(X, U ) và x là đ nh tùy ý không thu c