http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

CHƯƠNG IV
ð( TH) EULER VÀ ð( TH) HAMILTON
4.1. ðƯ4NG ðI EULER VÀ ð( TH) EULER.
Có th coi năm 1736 là năm khai sinh lý thuyt ñ th, vi vi c công b$ l%i gi&i
“bài toán v) các c*u + Konigsberg” c0a nhà toán h1c l2i l3c Euler (170771783). Thành
ph$ Konigsberg thu=c Ph? (nay g1i là Kaliningrad thu=c Nga) ñưCc chia thành b$n
vùng bEng các nhánh sông Pregel, các vùng này gm hai vùng bên b% sông, ñ&o
Kneiphof và m=t mi)n nEm giHa hai nhánh c0a sông Pregel. Vào th kJ 18, ngư%i ta xây
b&y chic c*u n$i các vùng này vi nhau.
G
Dân thành ph$ tOng thPc mPc: “Có th nào ñi d3o qua tSt c& b&y c*u, m2i c*u chT
m=t l*n thôi không?”. Nu ta coi m2i khu vVc A, B, C, D như m=t ñTnh và m2i c*u qua
l3i hai khu vVc là m=t c3nh n$i hai ñTnh thì ta có sơ ñ c0a Konigsberg là m=t ña ñ th
G như hình trên.
Bài toán tìm ñư%ng ñi qua tSt c& các c*u, m2i c*u chT qua m=t l*n có th ñưCc
phát biu l3i bEng mô hình này như sau: Có tn t3i chu trình ñơn trong ña ñ th G ch[a
tSt c& các c3nh?
4.1.1. ð5nh nghĩa:
Chu trình (t.ư. ñư%ng ñi) ñơn ch[a tSt c& các c3nh (ho\c cung) c0a
ñ th (vô hưng ho\c có hưng) G ñưCc g1i là chu trình (t.ư. ñư%ng ñi) Euler. 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 chu trình (t.ư. ñư%ng
ñi) Euler ñưCc g1i là ñ th Euler (t.ư. n^a Euler).
Thí d: 1:
ð th không n^a Euler
ð th n^a Euler
D
A
C
B
ð th Euler
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

ð th Euler ð th n^a Euler
ði)u ki n c*n và ñ0 ñ m=t ñ th là ñ th Euler ñưCc Euler tìm ra vào năm 1736
khi ông gi&i quyt bài toán hóc búa n?i ting th%i ñó v) b&y cái c*u + Konigsberg và ñây
là ñnh lý ñ*u tiên c0a lý thuyt ñ th.
4.1.2. ð5nh lý:
ð th (vô hưng) liên thông G là ñ th Euler khi và chT khi m1i ñTnh
c0a G ñ)u có bac chbn.
Ch=ng minh:
ðiu kin cn: Gi& s^ G là ñth Euler, t[c là tn t3i chu trình Euler P trong G. Khi ñó
c[ m2i l*n chu trình P ñi qua m=t ñTnh nào ñó c0a G thì bac c0a ñTnh ñó tăng lên 2. M\t
khác, m2i c3nh c0a ñ th xuSt hi n trong P ñúng m=t l*n. Do ñó m2i ñTnh c0a ñth
ñ)u có bac chbn.
4.1.3. B? ñ:
Nu bac c0a m2i ñTnh c0a ñ th G không nhd hơn 2 thì G ch[a chu trình
ñơn.
Ch=ng minh: Nu G có c3nh b=i ho\c có khuyên thì kheng ñnh c0a b? ñ) là hin
nhiên. Vì vay gi& s^ G là m=t ñơn ñ th. G1i v là m=t ñTnh nào ñó c0a G. Ta sf xây
dVng theo quy n3p ñư%ng ñi
trong ñó v
1
là ñTnh k) vi v, còn vi i ≥ 1, ch1n v
i+1
là ñTnh k) vi v
i
và v
i+1
≠ v
i
7
1
(có th
ch1n như vay vì deg(v
i
) ≥ 2), v
0
= v. Do tap ñTnh c0a G là hHu h3n, nên sau m=t s$ hHu
h3n bưc ta ph&i quay l3i m=t ñTnh ñã xuSt hi n trưc ñó. G1i k là s$ nguyên dương ñ*u
tiên ñ v
k
=v
i
(0≤i<k). Khi ñó, ñư%ng ñi v
i
, v
i+1
, ..., v
k
7
1
, v
k
(= v
i
) là m=t chu trình ñơn c*n
tìm.
ðiu kin ñ: Quy n3p theo s$ c3nh c0a G. Do G liên thông và bac c0a m1i ñTnh là
chbn nên m2i ñTnh có bac không nhd hơn 2. TO ñó theo B? ñ) 4.1.3, G ph&i ch[a m=t
chu trình ñơn C. Nu C ñi qua tSt c& các c3nh c0a G thì nó chính là chu trình Euler. Gi&
s^ C không ñi qua tSt c& các c3nh c0a G. Khi ñó lo3i bd khdi G các c3nh thu=c C, ta thu
ñưCc m=t ñ th mi H (không nhSt thit là liên thông). S$ c3nh trong H nhd hơn trong
G và rõ ràng m2i ñTnh c0a H vrn có bac là chbn. Theo gi& thit quy n3p, trong m2i thành
ph*n liên thông c0a H ñ)u tìm ñưCc chu trình Euler. Do G liên thông nên m2i thành
v
v1
v2


http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

ph*n trong H có ít nhSt m=t ñTnh chung vi chu trình C. Vì vay, ta có th xây dVng chu
trình Euler trong G như sau:
BPt ñ*u tO m=t ñTnh nào ñó c0a chu trình C, ñi theo các c3nh c0a C chOng nào chưa g\p
ph&i ñTnh không cô lap c0a H. Nu g\p ph&i ñTnh như vay thì ta ñi theo chu trình Euler
c0a thành ph*n liên thông c0a H ch[a ñTnh ñó. Sau ñó l3i tip tsc ñi theo c3nh c0a C cho
ñn khi g\p ph&i ñTnh không cô lap c0a H thì l3i theo chu trình Euler c0a thành ph*n liên
thông tương [ng trong H, ... Quá trình sf kt thúc khi ta tr+ v) ñTnh xuSt phát, t[c là thu
ñưCc chu trình ñi qua m2i c3nh c0a ñ th ñúng m=t l*n.
4.1.4. H qu:
ð th liên thông G là n^a Euler (mà không là Euler) khi và chT khi có
ñúng hai ñTnh bac lt trong G.
Ch=ng minh: Nu G là n^a Euler thì tn t3i m=t ñư%ng ñi Euler trong G tO ñTnh u ñn
ñTnh v. G1i G’ là ñ th thu ñưCc tO G bEng cách thêm vào c3nh (u,v). Khi ñó G’ là ñ
th Euler nên m1i ñTnh trong G’ ñ)u có bac chbn (k c& u và v). Vì vay u và v là hai ñTnh
duy nhSt trong G có bac lt.
ð&o l3i, nu có ñúng hai ñTnh bac lt là u và v thì g1i G’ là ñ th thu ñưCc tO G
bEng cách thêm vào c3nh (u,v). Khi ñó m1i ñTnh c0a G’ ñ)u có bac chbn hay G’ là ñ th
Euler. Bd c3nh (u,v) ñã thêm vào ra khdi chu trình Euler trong G’ ta có ñưCc ñư%ng ñi
Euler tO u ñn v trong G hay G là n^a Euler.
4.1.5. Chú ý:
Ta có th v3ch ñưCc m=t chu trình Euler trong ñ th liên thông G có bac
c0a m1i ñTnh là chbn theo thuat toán Fleury sau ñây.
XuSt phát tO m=t ñTnh bSt kỳ c0a G và tuân theo hai quy tPc sau:
1. M2i khi ñi qua m=t c3nh nào thì xoá nó ñi; sau ñó xoá ñTnh cô lap (nu có);
2. Không bao gi% ñi qua m=t c*u, trO phi không còn cách ñi nào khác.
u
s
v
w
t
x
y
z
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

XuSt phát tO u, ta có th ñi theo c3nh (u,v) ho\c (u,x), gi& s^ là (u,v) (xoá (u,v)).
TO v có th ñi qua m=t trong các c3nh (v,w), (v,x), (v,t), gi& s^ (v,w) (xoá (v,w)). Tip
tsc, có th ñi theo m=t trong các c3nh (w,s), (w,y), (w,z), gi& s^ (w,s) (xoá (w,s)). ði
theo c3nh (s,y) (xoá (s,y) và s). Vì (y,x) là c*u nên có th ñi theo m=t trong hai c3nh
(y,w), (y,z), gi& s^ (y,w) (xoá (y,w)). ði theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá
(z,y) và z). Tip tsc ñi theo c3nh (y,x) (xoá (y,x) và y). Vì (x,u) là c*u nên ñi theo c3nh
(x,v) ho\c (x,t), gi& s^ (x,v) (xoá (x,v)). Tip tsc ñi theo c3nh (v,t) (xoá (v,t) và v), theo
c3nh (t,x) (xoá c3nh (t,x) và t), cu$i cung ñi theo c3nh (x,u) (xoá (x,u), x và u).
4.1.6. Bài toán ngưGi phát thư Trung Hoa:
M=t nhân viên ñi tO S+ Bưu ði n, qua m=t s$ ñư%ng ph$ ñ phát thư, ri quay v)
S+. Ngư%i Sy ph&i ñi qua các ñư%ng theo trình tV nào ñ ñư%ng ñi là ngPn nhSt?
Bài toán ñưCc nhà toán h1c Trung Hoa Guan nêu lên ñ*u tiên (1960), vì vay
thư%ng ñưCc g1i là “bài toán ngư%i phát thư Trung Hoa”. Ta xét bài toán + m=t d3ng
ñơn gi&n như sau.
Cho ñ th liên thông G. M=t chu trình qua m1i c3nh c0a G g1i là m=t hành trình
trong G. Trong các hành trình ñó, hãy tìm hành trình ngPn nhSt, t[c là qua ít c3nh nhSt.
Rõ ràng rEng nu G là ñ th Euler (m1i ñTnh ñ)u có bac chbn) thì chu trình Euler
trong G (qua m2i c3nh c0a G ñúng m=t l*n) là hành trình ngPn nhSt c*n tìm.
ChT còn ph&i xét trư%ng hCp G có m=t s$ ñTnh bac lt (s$ ñTnh bac lt là m=t s$
chbn). Khi ñó, m1i hành trình trong G ph&i ñi qua ít nhSt hai l*n m=t s$ c3nh nào ñó.
D• thSy rEng m=t hành trình qua m=t c3nh (u,v) nào ñó quá hai l*n thì không ph&i
là hành trình ngPn nhSt trong G. Vì vay, ta chT c*n xét nhHng hành trình T ñi qua hai l*n
m=t s$ c3nh nào ñó c0a G.
Ta quy ưc xem m2i hành trình T trong G là m=t hành trình trong ñ th Euler
G
T
, có ñưCc tO G bEng cách vf thêm m=t c3nh song song ñ$i vi nhHng c3nh mà T ñi
qua hai l*n. Bài toán ñ\t ra ñưCc ñưa v) bài toán sau:
Trong các ñ th Euler G
T
, tìm ñ th có s$ c3nh ít nhSt (khi ñó chu trình Euler
trong ñ th này là hành trình ngPn nhSt).
ð5nh lý (Gooodman và Hedetniemi, 1973)
. Nu G là m=t ñ th liên thông có q
c3nh thì hành trình ngPn nhSt trong G có chi)u dài
q + m(G),
trong ñó m(G) là s$ c3nh mà hành trình ñi qua hai l*n và ñưCc xác ñnh như sau:
G1i V
0
(G) là tap hCp các ñTnh bac lt (2k ñTnh) c0a G. Ta phân 2k ph*n t^ c0a G
thành k c\p, m2i tap hCp k c\p g1i là m=t phân ho3ch c\p c0a V
0
(G).
Ta g1i ñ= dài ñư%ng ñi ngPn nhSt tO u ñn v là kho&ng cách d(u,v). ð$i vi m1i
phân ho3ch c\p P
i
, ta tính kho&ng cách giHa hai ñTnh trong tOng c\p, ri tính t?ng d(P
i
).
S$ m(G) bEng cVc tiu c0a các d(P
i
):
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

m(G)=min d(P
i
).
Thí d: 2: Gi&i bài toán ngư%i phát thư Trung Hoa cho trong ñ th sau:
G G
T
Tap hCp các ñTnh bac lt V
O
(G)={B, G, H, K} và tap hCp các phân ho3ch c\p là
P={P
1
, P
2
, P
3
}, trong ñó
P
1
= {(B, G), (H, K)} → d(P
1
) = d(B, G)+d(H, K) = 4+1 = 5,
P
2
= {(B, H), (G, K)} → d(P
2
) = d(B, H)+d(G, K) = 2+1 = 3,
P
3
= {(B, K), (G, H)} → d(P
3
) = d(B, K)+d(G, H) = 3+2 = 5.
m(G) = min(d(P
1
), d(P
2
), d(P
3
)) = 3.
Do ñó G
T
có ñưCc tO G bEng cách thêm vào 3 c3nh: (B, I), (I, H), (G, K) và G
T
là
ñ th Euler. Vay hành trình ngPn nhSt c*n tìm là ñi theo chu trình Euler trong G
T
:
A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A.
4.1.7. ð5nh lý:
ð th có hưng liên thông yu G là ñth Euler khi và chT khi m1i
ñTnh c0a G ñ)u có bac vào bEng bac ra.
Ch=ng minh: Ch[ng minh tương tV như ch[ng minh c0a ðnh lý 4.1.2 và ñi)u ki n ñ0
cũng c*n có b? ñ) dưi ñây tương tV như + B? ñ) 4.1.3.
4.1.8. B? ñ:
Nu bac vào và bac ra c0a m2i ñTnh c0a ñ th có hưng G không nhd
hơn 1 thì G ch[a chu trình ñơn.
4.1.9. H qu:
ð th có hưng liên thông yu G là n^a Euler (mà không là Euler) khi
và chT khi tn t3i hai ñTnh x và y sao cho:
deg
o
(x) = deg
t
(x)+1, deg
t
(y) = deg
o
(y)+1, deg
t
(v) = deg
o
(v), ∀v∈V, v ≠ x, v ≠ y.
Ch=ng minh: Ch[ng minh tương tV như + H qu& 4.1.4.
4.2. ðƯ4NG ðI HAMILTON VÀ ð( TH) HAMILTON.
Năm 1857, nhà toán h1c ngư%i Ailen là Hamilton(180571865) ñưa ra trò chơi “ñi
vòng quanh th gii” như sau.
Cho m=t hình thap nh di n ñ)u (ña di n ñ)u có 12 m\t, 20 ñTnh và 30 c3nh), m2i
ñTnh c0a hình mang tên m=t thành ph$ n?i ting, m2i c3nh c0a hình (n$i hai ñTnh) là
ñư%ng ñi l3i giHa hai thành ph$ tương [ng. XuSt phát tO m=t thành ph$, hãy tìm ñư%ng
ñi thăm tSt c& các thành ph$ khác, m2i thành ph$ chT m=t l*n, ri tr+ v) ch2 cũ.
D
C
E
F
B
K
J
A
I
H
G