http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

CHƯƠNG VII
ð( TH) PH+NG VÀ TÔ MÀU ð( TH)
T xa xưa ñã lưu truyn mt bài toán c “Ba nhà, ba ging”: Có ba nhà # g$n ba
cái ging, nhưng không có ñư'ng n(i th)ng các nhà v+i nhau cũng như không có ñư'ng
n(i th)ng các ging v+i nhau.
Có l$n b.t hoà v+i nhau, h/ tìm cách làm
các ñư'ng khác ñn ging sao cho các ñư'ng này
ñôi mt không giao nhau. H/ có th3c hi4n ñư5c ý
ñ7nh ñó không?
Bài toán này có th9 ñư5c mô hình b:ng ñ; th7 phân ñôi ñ$y ñ> K
3,3
. Câu hAi ban
ñ$u có th9 diCn ñDt như sau: Có th9 vE K
3,3
trên mt mGt ph)ng sao cho không có hai
cDnh nào cHt nhau? Trong chương này chúng ta sE nghiên cKu bài toán: có th9 vE mt ñ;
th7 trên mt mGt ph)ng không có các cDnh nào cHt nhau không. ðGc bi4t chúng ta sE trM
l'i bài toán ba nhà ba ging. Thư'ng có nhiu cách bi9u diCn ñ; th7. Khi nào có th9 tìm
ñư5c ít nh.t mt cách bi9u diCn ñ; th7 không có cDnh cHt nhau?
7.1. ð( TH) PH+NG.
7.1.1. ð2nh nghĩa:
Mt ñ; th7 ñư5c g/i là ph)ng nu nó có th9 vE ñư5c trên mt mGt
ph)ng mà không có các cDnh nào cHt nhau (# mt ñi9m không phMi là ñi9m mút c>a các
cDnh). Hình vE như th g/i là mt bi9u diCn ph)ng c>a ñ; th7.
Mt ñ; th7 có th9 là ph)ng ngay cM khi nó thư'ng ñư5c vE v+i nhRng cDnh cHt
nhau, vì có th9 vE nó b:ng cách khác không có các cDnh cHt nhau.
Thí d7 1: 1) Mt cây, mt chu trình ñơn là mt ñ; th7 ph)ng.
2) K
4
là ñ; th7 ph)ng b#i vì có th9 vE lDi như hình bên không có ñư'ng cHt nhau
ð; th7 K
4
K
4
vE không có ñư'ng cHt nhau
3) Xét ñ; th7 G như trong hình a dư+i ñây. Có th9 bi9u diCn G mt cách khác như trong
hình b, trong ñó b.t kỳ hai cDnh nào cũng không cHt nhau.
N1
N2
N3
G2
G3
G1
a
d
c
b
a
b
c
d
d
b
c
a
e
e
d
b
c
a
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

4) ð; th7 ñ$y ñ> K
5
là mt thí d] v ñ; th7 không ph)ng (xem ð7nh lý 7.2.2).
7.1.2. ð2nh nghĩa:
Cho G là mt ñ; th7 ph)ng. M_i ph$n mGt ph)ng gi+i hDn b#i mt
chu trình ñơn không chKa bên trong nó mt chu trình ñơn khác, g/i là mt min (hRu
hDn) c>a ñ; th7 G. Chu trình gi+i hDn min là biên c>a min. M_i ñ; th7 ph)ng liên
thông có mt min vô hDn duy nh.t (là ph$n mGt ph)ng bên ngoài t.t cM các min hRu
hDn). S( cDnh ít nh.t tDo thành biên g/i là ñai c>a G; trư'ng h5p nu G không có chu
trình thì ñai chính là s( cDnh c>a G.
Thí d7 2: 1) Mt cây chb có mt min, ñó là min vô hDn.
2) ð; th7 ph)ng # hình bên có 5 min, M
5
là min vô hDn, min M
1
có biên abgfa,
min M
2
có biên là bcdhgb, … Chu
trình ñơn abcdhgfa không gi+i hDn mt
min vì chKa bên trong nó chu trình ñơn
khác là abgfa.
7.1.3. ð2nh lý (Euler, 1752):
Nu mt ñ; th7 ph)ng liên thông có n ñbnh, p cDnh và d
min thì ta có h4 thKc:
n − p + d = 2.
Ch?ng minh: Cho G là ñ; th7 ph)ng liên thông có n ñbnh, p cDnh và d min.
Ta bA mt s( cDnh c>a G ñ9 ñư5c mt cây khung c>a G. M_i l$n ta bA mt cDnh
(p giMm 1) thì s( min c>a G cũng giMm 1 (d giMm 1), còn s( ñbnh c>a G không thay ñi
(n không ñi). Như vhy, giá tr7 c>a bi9u thKc n − p + d không thay ñi trong su(t quá
trình ta bA b+t cDnh c>a G ñ9 ñư5c mt cây. Cây này có n ñbnh, do ñó có n − 1 cDnh và
cây chb có mt min, vì vhy:
n − p + d = n − (n −1) + 1 = 2.
H4 thKc n − p + d = 2 thư'ng g/i là “h4 thKc Euler cho hình ña di4n”, vì ñư5c
Euler chKng minh ñ$u tiên cho hình ña di4n có n ñbnh, p cDnh và d mGt. M_i hình ña
di4n có th9 coi là mt ñ; th7 ph)ng. Ch)ng hDn hình tK di4n ABCD và hình hp
ABCDA’B’C’D’ có th9 bi9u diCn b:ng các ñ; th7 dư+i ñây.
7.1.4. H qu:
Trong mt ñ; th7 ph)ng liên thông tuỳ ý, luôn t;n tDi ít nh.t mt ñbnh
có bhc không vư5t quá 5.
c
d
b
g
h
a
f
e
M
1
M
2
M
3
M
4
M
5
A
D
B
C
B
B’
C’
C
A
A’
D
D’
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

Ch?ng minh: Trong ñ; th7 ph)ng m_i min ñư5c bao b:ng ít nh.t 3 cDnh. MGt khác,
m_i cDnh có th9 n:m trên biên c>a t(i ña hai min, nên ta có 3d ≤ 2p.
Nu trong ñ; th7 ph)ng mà t.t cM các ñbnh ñu có bhc không nhA hơn 6 thì do m_i
ñbnh c>a ñ; th7 phMi là ñ$u mút c>a ít nh.t 6 cDnh mà m_i cDnh lDi có hai ñ$u mút nên ta
có 6n ≤ 2p hay 3n ≤ p. T ñó suy ra 3d+3n ≤ 2p+p hay d+n ≤ p, trái v+i h4 thKc Euler
d+n=p+2.
7.2. ð( TH) KHÔNG PH+NG.
7.2.1. ð2nh lý:
ð; th7 phân ñôi ñ$y ñ> K
3,3
là mt ñ; th7 không ph)ng.
Ch?ng minh: GiM so K
3,3
là ñ; th7 ph)ng. Khi ñó ta có mt ñ; th7 ph)ng v+i 6 ñbnh
(n=6) và 9 cDnh (p=9), nên theo ð7nh lý Euler ñ; th7 có s( min là d=p−n+2=5.
q ñây, mõi cDnh chung cho hai min, mà m_i min có ít nh.t 4 cDnh. Do ñó
4d≤2p, tKc là 4x5≤2x9, vô lý.
Như vhy ñ7nh lý này cho ta l'i giMi c>a bài toán “Ba nhà ba ging”, nghĩa là
không th9 th3c hi4n ñư5c vi4c làm các ñư'ng khác ñn ging sao cho các ñư'ng này ñôi
mt không giao nhau.
7.2.2. ð2nh lý:
ð; th7 ñ$y ñ> K
5
là mt ñ; th7 không ph)ng.
Ch?ng minh: GiM so K
5
là ñ; th7 ph)ng. Khi ñó ta có mt ñ; th7 ph)ng v+i 5 ñbnh (n=5)
và 10 cDnh (p=10), nên theo ð7nh lý Euler ñ; th7 có s( min là d=p−n+2=7.
Trong K
5
, m_i min có ít nh.t 3cDnh, m_i cDnh chung cho hai min, vì vhy
3d≤2n, tKc là 3x7≤2x10, vô lý.
7.2.3. Chú ý:
Ta ñã th.y K
3,3
và K
5
là không ph)ng. Rõ ràng, mt ñ; th7 là không
ph)ng nu nó chKa mt trong hai ñ; th7 này như là ñ; th7 con. Hơn nRa, t.t cM các ñ; th7
không ph)ng c$n phMi chKa ñ; th7 con nhhn ñư5c t K
3,3
hoGc K
5
b:ng mt s( phép toán
cho phép nào ñó.
Cho ñ; th7 G, có cDnh (u,v). Nu ta xoá cDnh (u,v), r;i thêm ñbnh w cùng v+i hai
cDnh (u,w) và (w,v) thì ta nói r:ng ta ñã thêm ñbnh m+i w (bhc 2) ñGt trên cDnh (u,v) c>a
G.
ð; th7 G’ ñư5c g/i là ñ;ng phôi v+i ñ; th7 G nu G’ có ñư5c t G b:ng cách
thêm các ñbnh m+i (bhc 2) ñGt trên các cDnh c>a G.
Thí d7 3:
G G’
a
u
v
b
c
a
u
v
w
b
c
d
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

ð; th7 G là ñ;ng phôi v+i ñ; th7 G’.
Nhà toán h/c Ba Lan, Kuratowski, ñã thit lhp ñ7nh lý sau ñây vào năm 1930.
ð7nh lý này ñã bi9u th7 ñGc ñi9m c>a các ñ; th7 ph)ng nh' khái ni4m ñ; th7 ñ;ng phôi.
7.2.4. ð2nh lý (Kuratowski):
ð; th7 là không ph)ng khi và chb khi nó chKa mt ñ;
th7 con ñ;ng phôi v+i K
3,3
hoGc K
5
.
Thí d7 4:
Hình 1 Hình 2 Hình 3
ð; th7 trong hình 1 và 2 là ñ; th7 ph)ng. Các ñ; th7 này có 6 ñbnh, nhưng không
chKa ñ; th7 con K
3,3
ñư5c vì có ñbnh bhc 2, trong khi t.t cM các ñbnh c>a K
3,3
ñu có bhc
3; cũng không th9 chKa ñ; th7 con K
5
ñư5c vì có nhRng ñbnh bhc nhA hơn 4, trong khi
t.t cM các ñbnh c>a K
5
ñu có bhc 4.
ð; th7 trong hình 3 là ñ; th7 không ph)ng vì nu xoá ñbnh b cùng các cDnh (b,a),
(b,c), (b,f) ta ñư5c ñ; th7 con là K
5
.
7.3. TÔ MÀU ð( TH).
7.3.1. Tô màu bn ñH:
M_i bMn ñ; có th9 coi là mt ñ; th7 ph)ng. Trong mt bMn ñ;, ta coi hai min có
chung nhau mt ñư'ng biên là hai min k nhau (hai min chb có chung nhau mt ñi9m
biên không ñư5c coi là k nhau). Mt bMn ñ; thư'ng ñư5c tô màu, sao cho hai min k
nhau ñư5c tô hai màu khác nhau. Ta g/i mt cách tô màu bMn ñ; như vhy là mt cách tô
màu ñúng.
ð9 ñMm bMo chHc chHn hai min k nhau không bao gi' có màu trùng nhau,
chúng ta tô m_i min b:ng mt màu khác nhau. Tuy nhiên vi4c làm ñó nói chung là
không h5p lý. Nu bMn ñ; có nhiu min thì sE r.t khó phân bi4t nhRng màu g$n gi(ng
nhau. Do vhy ngư'i ta chb dùng mt s( màu c$n thit ñ9 tô bMn ñ;. Mt bài toán ñư5c
ñGt ra là: xác ñ7nh s( màu t(i thi9u c$n có ñ9 tô màu ñúng mt bMn ñ;.
Thí d7 5: BMn ñ; trong hình bên có 6 min,
nhưng chb c$n có 3 màu (vàng, ñA, xanh)
ñ9 tô ñúng bMn ñ; này. Ch)ng hDn, màu vàng
ñư5c tô cho M
1
và M
4
, màu ñA ñư5c tô cho M
2
và M
6
, màu xanh ñư5c tô cho M
3
và M
5
.
a
b
c
d
f
e
a
c
b
f
d
e
b
f
c
e
d
a
M
1
M
2
M
3
M
4
M
5
M
6
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

7.3.2. Tô màu ñH th2:
M_i bMn ñ; trên mGt ph)ng có th9 bi9u diCn b:ng mt ñ; th7, trong ñó m_i min
c>a bMn ñ; ñư5c bi9u diCn b:ng mt ñbnh; các cDnh n(i hai ñbnh, nu các min ñư5c
bi9u diCn b:ng hai ñbnh này là k nhau. ð; th7 nhhn ñư5c b:ng cách này g/i là ñ; th7 ñ(i
ngzu c>a bMn ñ; ñang xét. Rõ ràng m/i bMn ñ; trên mGt ph)ng ñu có ñ; th7 ñ(i ngzu
ph)ng. Bài toán tô màu các min c>a bMn ñ; là tương ñương v+i bài toán tô màu các
ñbnh c>a ñ; th7 ñ(i ngzu sao cho không có hai ñbnh lin k nhau có cùng mt màu, mà ta
g/i là tô màu ñúng các ñbnh c>a ñ; th7.
S( màu ít nh.t c$n dùng ñ9 tô màu ñúng ñ; th7 G ñư5c g/i là sHc s( c>a ñ; th7 G
và ký hi4u là χ(G).
Thí d7 6:
Ta th.y r:ng 4 ñbnh b, d, g, e ñôi mt k nhau nên phMi ñư5c tô b:ng 4 màu khác
nhau. Do ñó χ(G) ≥ 4. Ngoài ra, có th9 dùng 4 màu ñánh s( 1, 2, 3, 4 ñ9 tô màu G như
sau:
Như vhy χ(G) = 4.
7.3.3. Mnh ñ:
Nu ñ; th7 G chKa mt ñ; th7 con ñ;ng phôi v+i ñ; th7 ñ$y ñ> K
n
thì
χ(G) ≥ n.
Ch?ng minh: G/i H là ñ; th7 con c>a G ñ;ng phôi v+i K
n
thì χ(H) ≥ n. Do ñó χ(G) ≥ n.
7.3.4. Mnh ñ:
Nu ñơn ñ; th7 G không chKa chu trình ñ dài l} thì χ(G) =2.
Ch?ng minh: Không m.t tính ch.t tng quát có th9 giM so G liên thông. C( ñ7nh ñbnh u
c>a G và tô nó b:ng màu 0 trong hai màu 0 và 1. V+i m_i ñbnh v c>a G, t;n tDi mt
ñư'ng ñi t u ñn v, nu ñư'ng này có ñ dài ch•n thì tô màu 0 cho v, nu ñư'ng này có
ñ dài l} thì tô màu 1 cho v. Nu có hai ñư'ng ñi mang tính ch•n l} khác nhau cùng n(i
a
b
c
d
e
f
g
h
3
1
2
2
4
4
3
1