¯e

1
, ¯e

2
, . . . , ¯e

q
cu
˙’
a ¯e
1
, ¯e
2
, . . . , ¯e
q
ta nhˆa
.
n d¯u
.
o
.
.
c mˆo
.
t d¯ˆo
`
thi
.
Euler m´o

.
i c´o tˆo
˙’
ng tro
.
ng lu
.
o
.
.
ng nho
˙’
ho
.
n, mˆau thuˆa
˜
n. 
Bˆay gi`o
.
x´et d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
K(V
1
) trˆen tˆa

.
p c´ac d¯ı
˙’
nh V
1
trong d¯´o c´ac ca
.
nh thˆem v`ao
(v
i
, v
j
) c´o tro
.
ng lu
.
o
.
.
ng w
ij
bˇa
`
ng d¯ˆo
.
d`ai cu
˙’
a dˆay chuyˆe
`
n nho

˙’
nhˆa
´
t trong G gi˜u
.
a hai d¯ı
˙’
nh v
i
v`a v
j
. Khi d¯´o mˆo
˜
i ca
.
nh cu
˙’
a K(V
1
) tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t dˆay chuyˆe

`
n trong G. V`ı w(e) ≥ 0 v´o
.
i
mo
.
i ca
.
nh e ∈ E nˆen w
ij
c´o thˆe
˙’
d¯u
.
o
.
.
c x´ac d¯i
.
nh bˇa
`
ng thuˆa
.
t to´an t`ım d¯u
.
`o
.
ng d¯i ngˇa
´
n nhˆa

´
t,
chˇa
˙’
ng ha
.
n Floyd (xem 3.3.2) hay Dantzig [16].
D
-
i
.
nh l´y 5.2.3 Tˆo
`
n ta
.
i tu
.
o
.
ng ´u
.
ng mˆo
.
t-mˆo
.
t gi˜u
.
a l`o
.
i gia

˙’
i tˆo
´
i u
.
u cu
˙’
a b`ai to´an ngu
.
`o
.
i d¯u
.
a
thu
.
Trung Hoa v´o
.
i mˆo
.
t cˇa
.
p gh´ep ho`an ha
˙’
o c´o tro
.
ng lu
.
o
.

.
ng nho
˙’
nhˆa
´
t trong d¯ˆo
`
thi
.
K(V
1
).
Ch´u
.
ng minh. X´et mˆo
.
t l`o
.
i gia
˙’
i tˆo
´
i u
.
u cu
˙’
a b`ai to´an ngu
.
`o
.

i d¯u
.
a thu
.
Trung Hoa v`a d¯ˇa
.
t E

l`a
tˆa
.
p c´ac ca
.
nh thˆem v`ao G. Theo Bˆo
˙’
d¯ˆe
`
5.2.1 ta c´o thˆe
˙’
thiˆe
´
t lˆa
.
p tu
.
o
.
ng ´u
.
ng v´o

.
i mˆo
˜
i d¯ı
˙’
nh
v
i
∈ V
1
v´o
.
i mˆo
.
t d¯ı
˙’
nh v
j
∈ V
1
bˇa
`
ng mˆo
.
t dˆay chuyˆe
`
n so
.
cˆa
´

p µ
ij
m`a c´ac ca
.
nh thuˆo
.
c E

. Theo
Bˆo
˙’
d¯ˆe
`
5.2.2, µ
ij
c´o d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t. Trong d¯ˆo
`
thi
.
K(V
1
) c´ac dˆay chuyˆe
`
n µ

ij
tu
.
o
.
ng ´u
.
ng ca
.
nh
(v
i
, v
j
). Do d¯´o tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh cu
˙’
a V
1
d¯u
.
o
.
.
c kˆe

´
t ho
.
.
p, hai v´o
.
i hai, v`a c´ac ca
.
nh (v
i
, v
j
) tu
.
o
.
ng
´u
.
ng dˆay chuyˆe
`
n µ
ij
cu
˙’
a G

, ta
.
o th`anh mˆo

.
t cˇa
.
p gh´ep ho`an ha
˙’
o K cu
˙’
a d¯ˆo
`
thi
.
K(V
1
). (Trong
d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
v´o
.
i sˆo
´
chˇa
˜
n d¯ı
˙’

nh luˆon luˆon tˆo
`
n ta
.
i mˆo
.
t cˇa
.
p gh´ep ho`an ha
˙’
o; xem Phˆa
`
n 7.5).
V`ı tro
.
ng lu
.
o
.
.
ng cu
˙’
a cˇa
.
p gh´ep ho`an ha
˙’
o K bˇa
`
ng tˆo
˙’

ng c´ac tro
.
ng lu
.
o
.
.
ng cu
˙’
a c´ac ca
.
nh cu
˙’
a E

nˆen l`o
.
i gia
˙’
i cu
˙’
a b`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa l`a tˆo

´
i u
.
u nˆe
´
u v`a chı
˙’
nˆe
´
u K l`a mˆo
.
t cˇa
.
p
gh´ep ho`an ha
˙’
o v´o
.
i tro
.
ng lu
.
o
.
.
ng nho
˙’
nhˆa
´
t. Ta c´o d¯iˆe

`
u pha
˙’
i ch´u
.
ng minh. 
Do d¯´o nghiˆe
.
m cu
˙’
a b`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa d¯u
.
a vˆe
`
b`ai to´an t`ım mˆo
.
t cˇa
.
p
gh´ep ho`an ha
˙’
o c´o tro

.
ng lu
.
o
.
.
ng nho
˙’
nhˆa
´
t cu
˙’
a d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
K
n
. Viˆe
.
c x´ac d¯i
.
nh nghiˆe
.
m cu
˙’

a
b`ai to´an sau l`a mˆo
.
t thuˆa
.
t to´an kh´a ph´u
.
c ta
.
p v`a do d¯´o s˜e khˆong d¯u
.
o
.
.
c tr`ınh b`ay o
.
˙’
d¯ˆay. Ba
.
n
d¯o
.
c quan tˆam c´o thˆe
˙’
tham kha
˙’
o c´ac t`ai liˆe
.
u [14], [30].
Nhˆa

.
n x´et 5.2.4 Nˆe
´
u tˆo
`
n ta
.
i ca
.
nh e trong G sao cho w(e) < 0 th`ı b`ai to´an khˆong c´o nghiˆe
.
m
tˆo
´
i u
.
u: Thˆa
.
t vˆa
.
y, bˇa
`
ng c´ach thˆem mˆo
.
t tˆa
.
p E

h˜u
.

u ha
.
n c´ac ba
˙’
n sao cu
˙’
a c´ac ca
.
nh cu
˙’
a G ta
c´o thˆe
˙’
thˆem ca
.
nh e mˆo
.
t sˆo
´
chˇa
˜
n lˆa
`
n d¯u
˙’
l´o
.
n, v`a do d¯´o nhˆa
.
n d¯u

.
o
.
.
c mˆo
.
t d¯ˆo
`
thi
.
Euler v´o
.
i d¯ˆo
.
d`ai nho
˙’
tu`y ´y. Vˆa
.
y gia
˙’
thiˆe
´
t c´ac ca
.
nh c´o tro
.
ng lu
.
o
.

.
ng khˆong ˆam l`a khˆong mˆa
´
t t´ınh tˆo
˙’
ng
qu´at d¯ˆe
˙’
loa
.
i tr`u
.
tru
.
`o
.
ng ho
.
.
p tˆa
`
m thu
.
`o
.
ng n`ay.
V´ı du
.
5.2.5 X´et d¯ˆo
`

thi
.
trong H`ınh 5.3 v´o
.
i c´ac sˆo
´
trˆen c´ac ca
.
nh l`a tro
.
ng lu
.
o
.
.
ng ca
.
nh. Ta
cˆa
`
n t`ım mˆo
.
t chu tr`ınh qua mˆo
˜
i ca
.
nh ´ıt nhˆa
´
t mˆo
.

t lˆa
`
n v`a c´o d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t.
Tˆo
˙’
ng c´ac tro
.
ng lu
.
o
.
.
ng c´ac ca
.
nh cu
˙’
a G bˇa
`
ng 31. V`ı G khˆong l`a d¯ˆo
`
thi
.
Euler nˆen d¯ˆo
.

d`ai
cu
˙’
a chu tr`ınh cˆa
`
n t`ım s˜e l´o
.
n ho
.
n 31.
133
7

3

3

2

3
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
♠
5
♠
1
♠
6
♠
4
♠
7
♠
2
♠
3
H`ınh 5.3:
Tˆa
.
p c´ac d¯ı
˙’
nh bˆa
.
c le
˙’
l`a V
1
= {1, 2, 3, 4}. Theo thuˆa
.

t to´an t`ım d¯u
.
`o
.
ng d¯i ngˇa
´
n nhˆa
´
t (xem
Chu
.
o
.
ng 3), ta t`ım tˆa
´
t ca
˙’
c´ac dˆay chuyˆe
`
n c´o d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t gi˜u
.
a c´ac cˇa
.
p d¯ı

˙’
nh cu
˙’
a V
1
trong
G. Ta nhˆa
.
n d¯u
.
o
.
.
c m`a trˆa
.
n d¯ˆo
.
d`ai d¯u
.
`o
.
ng d¯i ngˇa
´
n nhˆa
´
t:






1 2 3 4
1 0 4 5 7
2 4 0 2 5
3 5 2 0 3
4 7 5 3 0





.
Tiˆe
´
p d¯ˆe
´
n ta xˆay du
.
.
ng d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
K(V
1
) trong d¯´o tro

.
ng lu
.
o
.
.
ng ca
.
nh (v
i
, v
j
) l`a d¯ˆo
.
d`ai cu
˙’
a dˆay chuyˆe
`
n ngˇa
´
n nhˆa
´
t gi˜u
.
a v
i
v`a v
j
(xem H`ınh 5.4).
3


4

7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
♠
4
♠
1
♠

3
♠
2
H`ınh 5.4: D
-
ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
K(V
1
).
Cˇa
.
p gh´ep ho`an ha
˙’
o v´o
.
i tro
.
ng lu
.
o
.
.
ng nho

˙’
nhˆa
´
t trˆen K(V
1
) gˆo
`
m c´ac ca
.
nh (1, 2) v`a (3, 4)
(tro
.
ng lu
.
o
.
.
ng bˇa
`
ng 4 + 3 = 7). C´ac dˆay chuyˆe
`
n tu
.
o
.
ng ´u
.
ng l`a {1, 7, 2} v`a {3, 4}.
Nghiˆe
.

m tˆo
´
i u
.
u cu
˙’
a b`ai to´an nhˆa
.
n d¯u
.
o
.
.
c bˇa
`
ng c´ach thˆem v`ao d¯ˆo
`
thi
.
ban d¯ˆa
`
u c´ac ca
.
nh
(1, 7), (7, 2) v`a (3, 4). D
-
ˆo
`
thi
.

G

nhˆa
.
n d¯u
.
o
.
.
c l`a d¯ˆo
`
thi
.
Euler (H`ınh 5.5).
134




.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
♠
5
♠

1
♠
6
♠
4
♠
7
♠
2
♠
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.



.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
H`ınh 5.5: D
-
ˆo
`
thi
.
Euler G

nhˆa
.
n d¯u
.
o
.
.
c t`u
.
G bˇa
`
ng c´ach thˆem c´ac ca
.
nh tu
.
o
.
ng ´u
.
ng c´ac dˆay
chuyˆe

`
n nho
˙’
nhˆa
´
t gi˜u
.
a 1 v`a 2 v`a gi˜u
.
a 3 v`a 4.
Cuˆo
´
i c`ung ta chı
˙’
cˆa
`
n t`ım mˆo
.
t chu tr`ınh Euler trong G

, chˇa
˙’
ng ha
.
n
{6, 2, 3, 7, 2, 7, 1, 7, 4, 5, 1, 6}
l`a chu tr`ınh c´o d¯ˆo
.
d`ai 31 + 7 = 38 l`a nghiˆe
.

m tˆo
´
i u
.
u cˆa
`
n t`ım.
5.3 B`ai to´an Hamilton
Gia
˙’
su
.
˙’
G := (V, E) l`a d¯ˆo
`
thi
.
liˆen thˆong (hay liˆen thˆong ma
.
nh trong tru
.
`o
.
ng ho
.
.
p c´o hu
.
´o
.

ng)
c´o n d¯ı
˙’
nh.
D
-
i
.
nh ngh˜ıa 5.3.1 Dˆay chuyˆe
`
n (hay d¯u
.
`o
.
ng d¯i) d¯i qua tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
G, mˆo
˜
i
d¯ı

˙’
nh mˆo
.
t lˆa
`
n, go
.
i l`a dˆay chuyˆe
`
n Hamilton (hay d¯u
.
`o
.
ng d¯i Hamilton).
Theo d¯i
.
nh ngh˜ıa, dˆay chuyˆe
`
n (hay d¯u
.
`o
.
ng d¯i Hamilton) l`a so
.
cˆa
´
p, v`a c´o d¯ˆo
.
d`ai (n − 1).
Chu tr`ınh (hay ma

.
ch) Hamilton l`a mˆo
.
t chu tr`ınh (hay ma
.
ch) d¯i qua tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh
cu
˙’
a d¯ˆo
`
thi
.
G, mˆo
˜
i d¯ı
˙’
nh d¯´ung mˆo
.
t lˆa
`
n. Dˆe
˜
thˆa
´

y rˇa
`
ng, chu tr`ınh Hamilton l`a chu tr`ınh so
.
cˆa
´
p
c´o d¯ˆo
.
d`ai n. Ta n´oi rˇa
`
ng, G l`a d¯ˆo
`
thi
.
Hamilton nˆe
´
u n´o ch´u
.
a mˆo
.
t chu tr`ınh Hamilton (trong
tru
.
`o
.
ng ho
.
.
p vˆo hu

.
´o
.
ng) hoˇa
.
c mˆo
.
t ma
.
ch Hamilton (trong tru
.
`o
.
ng ho
.
.
p c´o hu
.
´o
.
ng).
V´ı du
.
5.3.2 Nˇam 1859, nh`a to´an ho
.
c Hamilton (1805-1865) ngu
.
`o
.
i Ailen d¯˜a cho b´an mˆo

.
t
d¯ˆo
`
cho
.
i d¯ˆo
.
c d¯´ao, phˆa
`
n ch´ınh l`a mˆo
.
t khˆo
´
i nhi
.
diˆe
.
n d¯ˆe
`
u (khˆo
´
i d¯a diˆe
.
n c´o 12 mˇa
.
t ng˜u gi´ac d¯ˆe
`
u
v`a 20 d¯ı

˙’
nh, mˆo
˜
i d¯ı
˙’
nh c´o 3 ca
.
nh) l`am bˇa
`
ng gˆo
˜
. O
.
˙’
mˆo
˜
i d¯ı
˙’
nh c´o ghi tˆen mˆo
.
t th`anh phˆo
´
l´o
.
n:
Beruych, Qua
˙’
ng chˆau, Deli, Frangfua, v.v C´ach cho
.
i l`a t`ım mˆo

.
t d¯u
.
`o
.
ng d¯i do
.
c theo c´ac
135
ca
.
nh cu
˙’
a thˆa
.
p nhi
.
diˆe
.
n d¯ˆe
`
u v`a qua mˆo
˜
i d¯ı
˙’
nh (th`anh phˆo
´
) v`u
.
a d¯´ung mˆo

.
t lˆa
`
n. Muˆo
´
n tr`o cho
.
i
d¯u
.
o
.
.
c hˆa
´
p dˆa
˜
n ho
.
n c´o thˆe
˙’
quy d¯i
.
nh tru
.
´o
.
c tr`ınh tu
.
.

qua mˆo
.
t v`ai th`anh phˆo
´
d¯ˆa
`
u tiˆen, v`a d¯ˆe
˙’
gi´up nh´o
.
dˆe
˜
d`ang c´ac th`anh phˆo
´
d¯˜a d¯i qua, o
.
˙’
mˆo
˜
i d¯ı
˙’
nh cu
˙’
a khˆo
´
i thˆa
.
p nhi
.
diˆe

.
n d¯ˆe
`
u c´o d¯´ong
mˆo
.
t chiˆe
´
c d¯inh m˜u to, quanh d¯´o c´o thˆe
˙’
quˆa
´
n so
.
.
i dˆay nho
˙’
d¯ˆe
˙’
chı
˙’
d¯oa
.
n d¯u
.
`o
.
ng d¯˜a d¯i qua. Vˆe
`
sau d¯ˆe

˙’
d¯o
.
n gia
˙’
n, Hamilton d¯˜a thay khˆo
´
i thˆa
.
p nhi
.
diˆe
.
n d¯ˆe
`
u bˇa
`
ng mˆo
.
t h`ınh phˇa
˙’
ng. B`ai to´an
d¯u
.
o
.
.
c ph´at biˆe
˙’
u du

.
´o
.
i da
.
ng d¯ˆo
`
thi
.
nhu
.
sau. Ta biˆe
´
t rˇa
`
ng h`ınh thˆa
.
p nhi
.
diˆe
.
n d¯ˆe
`
u c´o 12 mˇa
.
t,
30 ca
.
nh, 20 d¯ı
˙’

nh; mˆo
˜
i mˇa
.
t l`a mˆo
.
t ng˜u gi´ac d¯ˆe
`
u, mˆo
˜
i d¯ı
˙’
nh l`a d¯ˆa
`
u m´ut cu
˙’
a 3 ca
.
nh. C´ac d¯ı
˙’
nh
v`a c´ac ca
.
nh cu
˙’
a h`ınh thˆa
.
p nhi
.
diˆe

.
n d¯ˆe
`
u lˆa
.
p th`anh mˆo
.
t d¯ˆo
`
thi
.
nhu
.
H`ınh 5.6. B`ai to´an d¯ˇa
.
t
ra l`a h˜ay t`ım mˆo
.
t chu tr`ınh Hamilton cu
˙’
a d¯ˆo
`
thi
.
G.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
•
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

•
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
•
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
•
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
••
•
•
• •

•
•
•
•
•
•
•
•
•
H`ınh 5.6: H`anh tr`ınh xung quanh thˆe
´
gi´o
.
i (khˆo
´
i thˆa
.
p nhi
.
diˆe
.
n d¯ˆe
`
u) cu
˙’
a Hamilton.
V´ı du
.
5.3.3 (B`ai to´an ngu
.

`o
.
i ch`ao h`ang). Mˆo
.
t ngu
.
`o
.
i ch`ao h`ang viˆe
´
ng thˇam n kh´ach h`ang
v
1
, v
2
, . . . , v
n
, xuˆa
´
t ph´at t`u
.
th`anh phˆo
´
v
0
v`a sau d¯´o tro
.
˙’
vˆe
`

vi
.
tr´ı xuˆa
´
t ph´at. Anh ta biˆe
´
t
khoa
˙’
ng c´ach d
0j
t`u
.
v
0
d¯ˆe
´
n tˆa
´
t ca
˙’
c´ac kh´ach h`ang v
j
v`a khoa
˙’
ng c´ach d
ij
gi˜u
.
a hai kh´ach h`ang

v
i
v`a v
j
(d¯ˇa
.
t d
ij
= d
ji
).
Ngu
.
`o
.
i ch`ao h`ang cˆa
`
n d¯i d¯ˆe
´
n c´ac kh´ach h`ang cu
˙’
a m`ınh theo th´u
.
tu
.
.
n`ao d¯ˆe
˙’
tˆo
˙’

ng qu˜ang
d¯u
.
`o
.
ng d¯i l`a nho
˙’
nhˆa
´
t? N´oi c´ach kh´ac cˆa
`
n t`ım mˆo
.
t chu tr`ınh Hamilton v´o
.
i d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t
trˆen d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’

c´o tro
.
ng sˆo
´
d¯u
.
o
.
.
c xˆay du
.
.
ng t`u
.
tˆa
.
p c´ac d¯ı
˙’
nh v
0
, v
1
, v
2
, . . . , v
n
, v`a tro
.
ng
lu

.
o
.
.
ng ca
.
nh (v
i
, v
j
) l`a d
ij
. Vˆe
`
c´ac thuˆa
.
t to´an gia
˙’
i b`ai to´an n`ay c´o thˆe
˙’
xem, chˇa
˙’
ng ha
.
n [30].
Trong tru
.
`o
.
ng ho

.
.
p d¯ı
˙’
nh cuˆo
´
i v
n+1
kh´ac d¯ı
˙’
nh xuˆa
´
t ph´at v
0
, b`ai to´an d¯u
.
a vˆe
`
t`ım dˆay
chuyˆe
`
n Hamilton t`u
.
v
0
d¯ˆe
´
n v
n+1
c´o tˆo

˙’
ng d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t. Bˇa
`
ng c´ach biˆe
´
n d¯ˆo
˙’
i mˆo
.
t c´ach
th´ıch ho
.
.
p trˆen d¯ˆo
`
thi
.
, ta c´o thˆe
˙’
d¯u
.
a vˆe
`
b`ai to´an t`ım chu tr`ınh Hamilton c´o tˆo

˙’
ng d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t.
136
V´ı du
.
5.3.4 (B`ai to´an lˆa
.
p li
.
ch). Trong mˆo
.
t sˆo
´
b`ai to´an lˆa
.
p li
.
ch, ta cˆa
`
n t`ım mˆo
.
t th´u
.
tu

.
.
thu
.
.
c hiˆe
.
n n tiˆe
´
n tr`ınh cho tru
.
´o
.
c (hai tiˆe
´
n tr`ınh khˆong d¯u
.
o
.
.
c thu
.
.
c hiˆe
.
n c`ung mˆo
.
t l´uc) v`a thoa
˙’
m˜an nh˜u

.
ng r`ang buˆo
.
c nhˆa
´
t d¯i
.
nh; bˇa
`
ng c´ach xˆay du
.
.
ng d¯ˆo
`
thi
.
G trong d¯´o tˆa
.
p c´ac d¯ı
˙’
nh cu
˙’
a
G tu
.
o
.
ng ´u
.
ng v´o

.
i tˆa
.
p c´ac tiˆe
´
n tr`ınh v`a mˆo
.
t cung liˆen thuˆo
.
c hai d¯ı
˙’
nh v
i
v`a v
j
nˆe
´
u tiˆe
´
n tr`ınh
i d¯u
.
o
.
.
c thu
.
.
c hiˆe
.

n tru
.
´o
.
c tiˆe
´
n tr`ınh j, b`ai to´an d¯u
.
a vˆe
`
t`ım mˆo
.
t d¯u
.
`o
.
ng d¯i Hamilton trong G.
V´ı du
.
5.3.5 (Lˆa
.
p li
.
ch v`a b`ai to´an ngu
.
`o
.
i ch`ao h`ang trˆen d¯ˆo
`
thi

.
c´o hu
.
´o
.
ng). Trong thu
.
.
c tˆe
´
ta thu
.
`o
.
ng lˆa
.
p kˆe
´
hoa
.
ch m`a mˆo
˜
i cung (v
i
, v
j
), biˆe
˙’
u diˆe
˜

n mˆo
.
t r`ang buˆo
.
c n`ao d¯´o, gˇa
´
n v´o
.
i mˆo
.
t
sˆo
´
thu
.
.
c t
ij
l`a khoa
˙’
ng th`o
.
i gian ´ıt nhˆa
´
t c´o thˆe
˙’
bˇa
´
t d¯ˆa
`

u thu
.
.
c hiˆe
.
n cˆong viˆe
.
c th´u
.
j khi cˆong
viˆe
.
c th´u
.
i d¯˜a tiˆe
´
n h`anh.
Th`o
.
i gian nho
˙’
nhˆa
´
t d¯ˆe
˙’
thu
.
.
c hiˆe
.

n tˆa
´
t ca
˙’
c´ac tiˆe
´
n tr`ınh d¯u
.
o
.
.
c x´ac d¯i
.
nh bˇa
`
ng c´ach t`ım
mˆo
.
t d¯u
.
`o
.
ng d¯i Hamilton c´o d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t trˆen d¯ˆo
`

thi
.
c´o hu
.
´o
.
ng. D
-
ˆay ch´ınh l`a b`ai to´an
ngu
.
`o
.
i ch`ao h`ang trˆen d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng. Vˆe
`
thuˆa
.
t to´an gia
˙’
i b`ai to´an n`ay c´o thˆe
˙’
xem, chˇa

˙’
ng
ha
.
n [30].
B`ai to´an ngu
.
`o
.
i ch`ao h`ang trˆen d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng hoˇa
.
c c´o hu
.
´o
.
ng thu
.
`o
.
ng gˇa
.
p trong cuˆo

.
c
sˆo
´
ng v`a c´o nhiˆe
`
u ´u
.
ng du
.
ng: lˆa
.
p th`o
.
i kho´a biˆe
˙’
u, lˆa
.
p li
.
ch, lˇa
´
p d¯ˇa
.
t hˆe
.
thˆo
´
ng d¯iˆe
.

n, tˆo
˙’
ng ho
.
.
p
c´ac ma
.
ch logic tuˆa
`
n tu
.
.
, v.v.
Ngo`ai ra, nhiˆe
`
u b`ai to´an c´o thˆe
˙’
d¯u
.
a vˆe
`
b`ai to´an ngu
.
`o
.
i ch`ao h`ang: b`ai to´an nhiˆe
`
u ngu
.

`o
.
i
ch`ao h`ang, mˆo
.
t v`ai b`ai to´an t`ım d¯u
.
`o
.
ng d¯i ngˇa
´
n nhˆa
´
t v´o
.
i d¯iˆe
`
u kiˆe
.
n qua tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh (hay
cung) cu
˙’
a mˆo
.

t tˆa
.
p cho tru
.
´o
.
c chı
˙’
mˆo
.
t lˆa
`
n, c´ac chu tr`ınh (hay ma
.
ch) Euler c´o chi ph´ı nho
˙’
nhˆa
´
t.
Cuˆo
´
i c`ung, ta c´o thˆe
˙’
chı
˙’
ra rˇa
`
ng, b`ai to´an ngu
.
`o

.
i ch`ao h`ang trˆen d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng c´o
thˆe
˙’
d¯u
.
a vˆe
`
tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.
vˆo hu
.
´o

.
ng.
Tr´ai v´o
.
i b`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa, ngoa
.
i tr`u
.
nh˜u
.
ng tru
.
`o
.
ng ho
.
.
p d¯ˇa
.
c biˆe
.
t,

ngu
.
`o
.
i ta chu
.
a t`ım d¯u
.
o
.
.
c mˆo
.
t thuˆa
.
t to´an d¯a th´u
.
c d¯ˆe
˙’
gia
˙’
i b`ai to´an ngu
.
`o
.
i ch`ao h`ang. C´ac
thuˆa
.
t to´an hiˆe
.

u qua
˙’
nhˆa
´
t su
.
˙’
du
.
ng c´ac phu
.
o
.
ng ph´ap nh´anh v`a cˆa
.
n [30].
D
-
i
.
nh ngh˜ıa 5.3.6 Mˆo
.
t chu tr`ınh (tu
.
o
.
ng ´u
.
ng, ma
.

ch) d¯i qua tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh, mˆo
˜
i d¯ı
˙’
nh ´ıt
nhˆa
´
t mˆo
.
t lˆa
`
n, go
.
i l`a chu tr`ınh (tu
.
o
.
ng ´u
.
ng, ma
.
ch) tiˆe
`
n Hamilton. D

-
ˆo
`
thi
.
G ch´u
.
a mˆo
.
t chu
tr`ınh hay ma
.
ch nhu
.
vˆa
.
y go
.
i l`a d¯ˆo
`
thi
.
tiˆe
`
n Hamilton. Dˆe
˜
thˆa
´
y rˇa
`

ng, d¯iˆe
`
u kiˆe
.
n cˆa
`
n v`a d¯u
˙’
d¯ˆe
˙’
G l`a d¯ˆo
`
thi
.
tiˆe
`
n Hamilton l`a G liˆen thˆong (liˆen thˆong ma
.
nh).
T`ım kiˆe
´
m mˆo
.
t chu tr`ınh (hay ma
.
ch) Hamilton c´o d¯ˆo
.
d`ai nho
˙’
nhˆa

´
t trˆen d¯ˆo
`
thi
.
c´o tro
.
ng
sˆo
´
d¯u
.
a vˆe
`
b`ai to´an x´ac d¯i
.
nh chu tr`ınh (hay ma
.
ch) trong d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
G

nhˆa
.

n d¯u
.
o
.
.
c tˆa
.
p
137
c´ac d¯ı
˙’
nh cu
˙’
a G v`a tro
.
ng lu
.
o
.
.
ng trˆen ca
.
nh (cung) (v
i
, v
j
) cu
˙’
a G


bˇa
`
ng d¯ˆo
.
d`ai cu
˙’
a dˆay chuyˆe
`
n
(d¯u
.
`o
.
ng d¯i) ngˇa
´
n nhˆa
´
t t`u
.
v
i
d¯ˆe
´
n v
j
trong G.
Nhiˆe
`
u da
.

ng b`ai to´an ngu
.
`o
.
i ch`ao h`ang ch´ınh l`a c´ac b`ai to´an tiˆe
`
n Hamilton, v`a d¯ˆe
˙’
gia
˙’
i
ch´ung tru
.
´o
.
c hˆe
´
t ta cˆa
`
n t`ım ma trˆa
.
n tu
.
o
.
ng ´u
.
ng c´ac dˆay chuyˆe
`
n (d¯u

.
`o
.
ng d¯i) ngˇa
´
n nhˆa
´
t.
Cuˆo
´
i c`ung nhˆa
.
n x´et rˇa
`
ng, tˆo
`
n ta
.
i mˆo
.
t tru
.
`o
.
ng ho
.
.
p m`a b`ai to´an chu tr`ınh tiˆe
`
n Hamilton

c´o d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t c´o thˆe
˙’
d¯u
.
a vˆe
`
b`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa; d¯iˆe
`
u n`ay xa
˙’
y ra khi
G l`a d¯ˆo
`
thi
.
d¯ˆo

´
i ngˆa
˜
u
1
cu
˙’
a d¯o
.
n d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng G
∗
n`ao d¯´o v`a khi d¯ˆo
.
d`ai cu
˙’
a c´ac ca
.
nh (v
i
, v
j
)

c´o da
.
ng a
i
+ a
j
. Trong tru
.
`o
.
ng ho
.
.
p n`ay, b`ai to´an t`ım chu tr`ınh tiˆe
`
n Hamilton trong G ch´ınh
l`a b`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa trong G
∗
v´o
.
i d¯ˆo
.

d`ai ca
.
nh e
∗
i
cu
˙’
a G
∗
l`a a
i
.
Nhˆa
.
n x´et tu
.
o
.
ng tu
.
.
cho b`ai to´an t`ım ma
.
ch tiˆe
`
n Hamilton c´o d¯ˆo
.
d`ai nho
˙’
nhˆa

´
t trong
tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng G l`a d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa
˜
u cu
˙’
a d¯a d¯ˆo
`
thi

.
c´o hu
.
´o
.
ng n`ao d¯´o.
5.3.1 C´ac d¯iˆe
`
u kiˆe
.
n cˆa
`
n d¯ˆe
˙’
tˆo
`
n ta
.
i chu tr`ınh Hamilton
Hiˆe
˙’
n nhiˆen rˇa
`
ng, mˆo
.
t d¯iˆe
`
u kiˆe
.
n cˆa

`
n d¯ˆe
˙’
tˆo
`
n ta
.
i chu tr`ınh Hamilton l`a G 2-liˆen thˆong. Tuy
nhiˆen, d¯ˆay khˆong pha
˙’
i d¯iˆe
`
u kiˆe
.
n d¯u
˙’
.
H`ınh 5.7 l`a mˆo
.
t v´ı du
.
d¯ˆo
`
thi
.
2-liˆen thˆong khˆong ch´u
.
a chu tr`ınh Hamilton (ho
.
n n˜u

.
a,
c´o thˆe
˙’
chı
˙’
ra rˇa
`
ng, d¯´o l`a d¯ˆo
`
thi
.
c´o sˆo
´
d¯ı
˙’
nh ´ıt nhˆa
´
t thoa
˙’
m˜an t´ınh chˆa
´
t n`ay).
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

•
•

•
•
•
H`ınh 5.7: D
-
ˆo
`
thi
.
2-liˆen thˆong c´o sˆo
´
d¯ı
˙’
nh ´ıt nhˆa
´
t khˆong c´o chu tr`ınh Hamilton.
D
-
ˆo
`
thi
.
vˆo hu
.
´o
.
ng Petersen (H`ınh 5.8) l`a v´ı du
.
kh´ac khˆong c´o chu tr`ınh Hamilton. D
-

ˆay
l`a d¯ˆo
`
thi
.
ch´ınh quy 3-liˆen thˆong nho
˙’
nhˆa
´
t c´o tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh bˆa
.
c ba. Nhiˆe
`
u pha
˙’
n v´ı du
.
vˆe
`
b`ai to´an Hamilton d¯u
.
o
.
.

c xˆay du
.
.
ng t`u
.
d¯ˆo
`
thi
.
Petersen.
1
D
-
ˆo
`
thi
.
vˆo hu
.
´o
.
ng G
∗
l`a d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa

˜
u cu
˙’
a G = (V, E) nˆe
´
u mˆo
˜
i d¯ı
˙’
nh cu
˙’
a G
∗
tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t ca
.
nh
e ∈ E v`a hai d¯ı
˙’
nh trong G
∗

kˆe
`
nhau nˆe
´
u hai ca
.
nh tu
.
o
.
ng ´u
.
ng kˆe
`
nhau. D
-
ˆo
`
thi
.
c´o hu
.
´o
.
ng G
∗
l`a d¯ˆo
`
thi
.

d¯ˆo
´
i
ngˆa
˜
u cu
˙’
a G = (V, E) nˆe
´
u mˆo
˜
i d¯ı
˙’
nh e
∗
cu
˙’
a G
∗
tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t cung e ∈ E v`a tˆo

`
n ta
.
i cung (e
∗
1
, e
∗
2
) trong
G
∗
nˆe
´
u d¯ı
˙’
nh ngo
.
n cu
˙’
a cung e
1
l`a d¯ı
˙’
nh gˆo
´
c cu
˙’
a cung e
2

.
138
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•

•
•
••
•
•
•
•
•
H`ınh 5.8: D
-
ˆo
`
thi
.
Petersen.
C´o nhiˆe
`
u d¯iˆe
`
u kiˆe
.
n cˆa
`
n kh´ac (xem [30], [14]) nhu
.
ng khˆong c´o mˆo
.
t d¯iˆe
`
u kiˆe

.
n cˆa
`
n v`a d¯u
˙’
vˆe
`
su
.
.
tˆo
`
n ta
.
i chu tr`ınh (ma
.
ch) Hamiton.
Do d¯´o ch´ung ta s˜e tˆa
.
p trung mˆo
.
t sˆo
´
d¯iˆe
`
u kiˆe
.
n d¯u
˙’
dˆa

˜
n d¯ˆe
´
n c´ac phu
.
o
.
ng ph´ap c´o t´ınh
xˆay du
.
.
ng chu tr`ınh Hamilton.
5.3.2 C´ac d¯iˆe
`
u kiˆe
.
n d¯u
˙’
vˆe
`
su
.
.
tˆo
`
n ta
.
i chu tr`ınh Hamilton
Mˆe
.

nh d¯ˆe
`
5.3.7 K
n
l`a d¯ˆo
`
thi
.
Hamilton.
Ch´u
.
ng minh. Hiˆe
˙’
n nhiˆen. 
X´et d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng n d¯ı
˙’
nh G := (V, E). Gia
˙’
su
.
˙’
s v`a t l`a hai d¯ı

˙’
nh khˆong kˆe
`
nhau sao
cho
d
G
(s) + d
G
(t) ≥ n.
K´y hiˆe
.
u G + (s, t) l`a d¯ˆo
`
thi
.
nhˆa
.
n d¯u
.
o
.
.
c t`u
.
G bˇa
`
ng c´ach thˆem ca
.
nh (s, t). Khi d¯´o

Mˆe
.
nh d¯ˆe
`
5.3.8 Nˆe
´
u G + (s, t) l`a d¯ˆo
`
thi
.
Hamilton th`ı G l`a d¯ˆo
`
thi
.
Hamilton. Ta n´oi t´ınh
chˆa
´
t n`ay l`a ˆo
˙’
n d¯i
.
nh Hamilton qua ph´ep biˆe
´
n d¯ˆo
˙’
i G → G + (s, t).
Ch´u
.
ng minh. Gia
˙’

su
.
˙’
G + (s, t ) ch´u
.
a chu tr`ınh Hamilton µ := (v
1
, v
2
, . . . , v
n
). Nˆe
´
u µ khˆong
d¯i qua ca
.
nh (s, t) th`ı G l`a Hamilton. Ngu
.
o
.
.
c la
.
i, G ch´u
.
a mˆo
.
t dˆay chuyˆe
`
n Hamilton µ \ (s, t)

nˆo
´
i s v`a t. (Khˆong mˆa
´
t t´ınh tˆo
˙’
ng qu´at, c´o thˆe
˙’
gia
˙’
thiˆe
´
t s = v
1
, t = v
n
).
139
Ta ch´u
.
ng minh rˇa
`
ng tˆo
`
n ta
.
i ´ıt nhˆa
´
t mˆo
.

t chı
˙’
sˆo
´
i, 3 ≤ i ≤ n, sao cho s kˆe
`
v´o
.
i v
i
v`a t kˆe
`
v´o
.
i v
i−1
.
Thˆa
.
t vˆa
.
y, x´et c´ac tˆa
.
p con cu
˙’
a tˆa
.
p Y := {v
3
, v

4
, . . . , v
n−1
} :
A = {v
i
| (s, v
i
) ∈ E v`a 3 ≤ i ≤ n − 1},
B
=
{
v
i
|
(
t, v
i−1
)
∈
E
v`a 3
≤
i
≤
n
−
1
}
.

V`ı s v`a t khˆong kˆe
`
nhau trong G nˆen
#A + #B = d
G
(s) + d
G
(t) − 2 ≥ n − 2
v`a nhˆa
.
n x´et rˇa
`
ng #Y = n − 3 suy ra tˆo
`
n ta
.
i
v
i
∈ A ∩ B (3 ≤ i ≤ n − 1).
Do d¯´o, thˆem c´ac ca
.
nh (s, v
i
) v`a (t, v
i−1
) v`a xo´a ca
.
nh (v
i

, v
i−1
) ta d¯u
.
o
.
.
c mˆo
.
t chu tr`ınh Hamilton
trong G (xem H`ınh 5.9), v`a mˆe
.
nh d¯ˆe
`
d¯u
.
o
.
.
c ch´u
.
ng minh. 
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
t = v
n
• •
v
i
•
v
i−1
•
•
v
3
•
v
2

•
s = v
1
−→
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

•
v
i
•
v
1
•
v
2
•
v
3
•
•
v
i−1
•
t = v
n
•

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
H`ınh 5.9:
Gia
˙’
su
.
˙’
G l`a d¯o
.
n d¯ˆo
`
thi
.
n d¯ı
˙’
nh v`a k l`a sˆo
´
nguyˆen thoa
˙’
1 ≤ k ≤ n. X´et thu
˙’
tu
.
c d¯ˆe

.
quy sau: Xuˆa
´
t ph´at t`u
.
G, thˆem c´ac ca
.
nh nˆo
´
i c´ac d¯ı
˙’
nh khˆong kˆe
`
nhau m`a tˆo
˙’
ng c´ac bˆa
.
c cu
˙’
a
ch´ung l´o
.
n ho
.
n hoˇa
.
c bˇa
`
ng k. (Sˆo
´

ph´ep to´an d¯`oi ho
˙’
i trong thu
˙’
tu
.
c n`ay tı
˙’
lˆe
.
v´o
.
i n
4
). V`ı c´ac
bˆa
.
c khˆong gia
˙’
m, d¯ˆo
`
thi
.
nhˆa
.
n d¯u
.
o
.
.

c khˆong phu
.
thuˆo
.
c v`ao th´u
.
tu
.
.
c´ac ca
.
nh d¯u
.
o
.
.
c thˆem. D
-
ˆo
`
thi
.
n`ay (ch´u
.
a G) go
.
i l`a k−bao d¯´ong cu
˙’
a G v`a k´y hiˆe
.

u l`a [G]
k
. V´o
.
i k = n, t`u
.
Mˆe
.
nh d¯ˆe
`
5.3.8
suy ra
D
-
i
.
nh l´y 5.3.9 [8] G l`a d¯ˆo
`
thi
.
Hamilton nˆe
´
u v`a chı
˙’
nˆe
´
u [G]
n
l`a d¯ˆo
`

thi
.
Hamilton.
Trong tru
.
`o
.
ng ho
.
.
p tˆo
˙’
ng qu´at, t`ım chu tr`ınh Hamilton trong [G]
n
khˆong pha
˙’
i l´uc n`ao
c˜ung dˆe
˜
ho
.
n trong G. Tuy nhiˆen, v´o
.
i nh˜u
.
ng tru
.
`o
.
ng ho

.
.
p d¯ˇa
.
c biˆe
.
t, chˇa
˙’
ng ha
.
n khi [G]
n
l`a d¯ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
K
n
ta c´o thˆe
˙’
dˆe
˜
d`ang xˆay du
.
.
ng chu tr`ınh Hamilton trong [G]

n
:
140
D
-
i
.
nh l´y 5.3.10 D
-
iˆe
`
u kiˆe
.
n d¯u
˙’
d¯ˆe
˙’
G l`a d¯ˆo
`
thi
.
Hamilton l`a [G]
n
= K
n
.
C´o thˆe
˙’
chı
˙’

ra rˇa
`
ng hˆa
`
u hˆe
´
t c´ac d¯iˆe
`
u kiˆe
.
n d¯u
˙’
d¯˜a biˆe
´
t (d¯u
.
o
.
.
c liˆe
.
t kˆe du
.
´o
.
i d¯ˆay) liˆen quan
d¯ˆe
´
n bˆa
.

c cu
˙’
a G suy ra [G]
n
= K
n
v`a do d¯´o l`a c´ac hˆe
.
qua
˙’
cu
˙’
a D
-
i
.
nh l´y 5.3.10.
Gia
˙’
su
.
˙’
G l`a d¯o
.
n d¯ˆo
`
thi
.
liˆen thˆong n d¯ı
˙’

nh.
Hˆe
.
qua
˙’
5.3.11 [Ore] [47] Nˆe
´
u d
G
(v
i
) + d
G
(v
j
) ≥ n v´o
.
i mo
.
i (v
i
, v
j
) /∈ E th`ı G l`a d¯ˆo
`
thi
.
Hamilton.
Hˆe
.

qua
˙’
5.3.12 [Dirac] [17] Nˆe
´
u d
G
(v
i
) ≥
n
2
v´o
.
i mo
.
i d¯ı
˙’
nh v
i
∈ V th`ı G l`a d¯ˆo
`
thi
.
Hamilton.
Hˆe
.
qua
˙’
5.3.13 [P´osa] [51] Nˆe
´

u c´ac d¯ı
˙’
nh cu
˙’
a G d¯u
.
o
.
.
c d¯´anh sˆo
´
thu
.
.
tu
.
.
sao cho
d
G
(v
1
) ≤ d
G
(v
2
) ≤ · · · ≤ d
G
(v
n

)
v`a nˆe
´
u
∀k : 1 ≤ k <
n
2
⇒ d
G
(v
k
) > k,
th`ı G l`a d¯ˆo
`
thi
.
Hamilton.
Hˆe
.
qua
˙’
5.3.14 [Bondy] [7] Gia
˙’
su
.
˙’
c´ac d¯ı
˙’
nh cu
˙’

a G d¯u
.
o
.
.
c d¯´anh sˆo
´
thu
.
.
tu
.
.
sao cho
d
G
(v
1
) ≤ d
G
(v
2
) ≤ · · · ≤ d
G
(v
n
).
Nˆe
´
u d¯iˆe

`
u kiˆe
.
n sau d¯´ung:
p < q, d
G
(v
p
) ≤ p, d
G
(v
q
) ≤ q − 1 ⇒ d
G
(v
p
) + d
G
(v
q
) ≥ n,
th`ı G l`a d¯ˆo
`
thi
.
Hamilton.
Hˆe
.
qua
˙’

5.3.15 [Chv´atal] [13] Nˆe
´
u c´ac d¯ı
˙’
nh cu
˙’
a G d¯u
.
o
.
.
c d¯´anh sˆo
´
thu
.
.
tu
.
.
sao cho
d
G
(v
1
) ≤ d
G
(v
2
) ≤ · · · ≤ d
G

(v
n
)
v`a nˆe
´
u
d
G
(v
k
) ≤ k <
n
2
⇒ d
G
(v
n−k
) ≥ n − k
th`ı G l`a d¯ˆo
`
thi
.
Hamilton.
141
Hˆe
.
qua
˙’
5.3.16 [Las Vergnas] [42] [30] Nˆe
´

u c´ac d¯ı
˙’
nh cu
˙’
a G d¯u
.
o
.
.
c d¯´anh sˆo
´
thu
.
.
tu
.
.
v
1
, v
2
, . . . , v
n
sao cho
j < k, k ≥ n − j
(v
j
, v
k
) /∈ E

d
G
(v
j
) ≤ j, d
G
(v
k
) ≤ k − 1





⇒ d
G
(v
j
) + d
G
(v
k
) ≥ n
th`ı G l`a d¯ˆo
`
thi
.
Hamilton.
C´ac ch´u
.

ng minh. Ch´u
.
ng minh cu
˙’
a Hˆe
.
qua
˙’
5.3.11 suy tru
.
.
c tiˆe
´
p t`u
.
c´ach xˆay du
.
.
ng [G]
n
: tˆa
´
t
ca
˙’
c´ac ca
.
nh (v
i
, v

j
) /∈ E c´o thˆe
˙’
d¯u
.
o
.
.
c thˆem v`a do d¯´o ta c´o [G]
n
= K
n
. Hˆe
.
qua
˙’
5.3.12 suy tru
.
.
c
tiˆe
´
p t`u
.
Hˆe
.
qua
˙’
5.3.11.
Ho

.
n n˜u
.
a, dˆe
˜
d`ang thˆa
´
y rˇa
`
ng, d¯ˆo
`
thi
.
thoa
˙’
m˜an c´ac d¯iˆe
`
u kiˆe
.
n cu
˙’
a Hˆe
.
qua
˙’
5.3.13, 5.3.14
hay 5.3.15 c˜ung thoa
˙’
m˜an c´ac gia
˙’

thiˆe
´
t cu
˙’
a Hˆe
.
qua
˙’
5.3.16.
D
-
ˆe
˙’
ch´u
.
ng minh Hˆe
.
qua
˙’
5.3.16, ta s˜e su
.
˙’
du
.
ng kˆe
´
t qua
˙’
sau cho d¯iˆe
`

u kiˆe
.
n d¯u
˙’
d¯ˆe
˙’
[G]
n
= K
n
.
D
-
i
.
nh l´y 5.3.17 [8] Nˆe
´
u c´ac d¯ı
˙’
nh cu
˙’
a G d¯u
.
o
.
.
c d¯´anh sˆo
´
thu
.

.
tu
.
.
v
1
, v
2
, . . . , v
n
sao cho
i < j
(v
i
, v
j
) /∈ E
d
G
(v
i
) ≤ i + k − n
d
G
(v
j
) ≤ j + k − n − 1
i + j ≥ 2n − k
















⇒ d
G
(v
i
) + d
G
(v
j
) ≥ k
th`ı k−bao d¯´ong cu
˙’
a G l`a d¯ˆo
`
thi
.
d¯ˆa
`

y d¯u
˙’
K
n
.
Ch´u
.
ng minh. 
Hˆe
.
qua
˙’
5.3.16 suy tru
.
.
c tiˆe
´
p t`u
.
D
-
i
.
nh l´y 5.3.17 v´o
.
i k = n. Hˆe
.
qua
˙’
5.3.16 l`a tˆo

˙’
ng qu´at
nhˆa
´
t cu
˙’
a tˆa
´
t ca
˙’
c´ac d¯iˆe
`
u kiˆe
.
n d¯˜a biˆe
´
t c´o liˆen quan d¯ˆe
´
n bˆa
.
c cu
˙’
a d¯ˆo
`
thi
.
. Tuy nhiˆen, d¯iˆe
`
u kiˆe
.

n
d¯u
˙’
cu
˙’
a D
-
i
.
nh l ´y 5.3.10 l`a tˆo
˙’
ng qu´at ho
.
n: d¯ˆo
`
thi
.
trong H`ınh 5.10 c´o [G]
6
= K
6
nhu
.
ng khˆong
tˆo
`
n ta
.
i c´ach d¯´anh sˆo
´

c´ac d¯ı
˙’
nh cu
˙’
a G thoa
˙’
c´ac d¯iˆe
`
u kiˆe
.
n cu
˙’
a Hˆe
.
qua
˙’
5.3.16.
5.3.3 C´ac d¯iˆe
`
u kiˆe
.
n d¯u
˙’
vˆe
`
su
.
.
tˆo
`

n ta
.
i ma
.
ch Hamilton
Trong tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng, c´o mˆo
.
t sˆo
´
c´ac d¯iˆe
`
u kiˆe
.
n d¯u
˙’

ba
˙’
o d¯a
˙’
m su
.
.
tˆo
`
n ta
.
i cu
˙’
a ma
.
ch
Hamilton. Kˆe
´
t qua
˙’
tˆo
˙’
ng qu´at nhˆa
´
t l`a:
142
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
•
•
•
•
H`ınh 5.10: V´o
.
i d¯ˆo
`
thi
.
n`ay, [G]
6
= K
6
nhu

.
ng khˆong thˆe
˙’
´ap du
.
ng Hˆe
.
qua
˙’
5.3.16.
D
-
i
.
nh l´y 5.3.18 [Meyniel, 1973] Gia
˙’
su
.
˙’
G = (V, E) l`a d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng n d¯ı
˙’
nh liˆen thˆong

ma
.
nh khˆong khuyˆen sao cho
(v
i
, v
j
) /∈ E v`a (v
j
, v
i
) /∈ E ⇒ d
G
(v
i
) + d
G
(v
j
) ≥ 2n − 1.
Khi d¯´o G ch´u
.
a mˆo
.
t ma
.
ch Hamilton.
Ch´ung ta s˜e d¯u
.
a ra ch´u

.
ng minh c´o t´ınh kiˆe
´
n thiˆe
´
t d¯i
.
nh l´y n`ay (theo Minoux, 1977)
v`a mˆo
.
t thuˆa
.
t to´an c´o d¯ˆo
.
ph´u
.
c ta
.
p O(n
4
) d¯ˆe
˙’
t`ım ma
.
ch Hamilton. Ch´u
.
ng minh du
.
.
a trˆen

phu
.
o
.
ng ph´ap (khˆong kiˆe
´
n thiˆe
´
t) cu
˙’
a Bondy v`a Thmassen (1977). Tru
.
´o
.
c hˆe
´
t, ch´ung ta cˆa
`
n
mˆo
.
t sˆo
´
kh´ai niˆe
.
m.
Gia
˙’
su
.

˙’
S ⊂ V. V´o
.
i mˆo
˜
i v
i
∈ V (c´o thˆe
˙’
v
i
∈ S), k´y hiˆe
.
u δ
S
(i) l`a sˆo
´
c´ac cung nˆo
´
i (theo
hu
.
´o
.
ng bˆa
´
t k`y) d¯ı
˙’
nh v
i

v´o
.
i tˆa
.
p con S. V`ı G khˆong c´o khuyˆen nˆen ta luˆon luˆon c´o
v
i
∈ S ⇒ δ
S
(i) ≤ 2#S − 2.
V´o
.
i S l`a tˆa
.
p con thu
.
.
c su
.
.
cu
˙’
a V ta go
.
i S−bˆo
.
h`anh l`a mˆo
.
t d¯u
.

`o
.
ng d¯i m`a c´ac d¯ı
˙’
nh d¯ˆa
`
u v`a
cuˆo
´
i (khˆong nhˆa
´
t thiˆe
´
t phˆan biˆe
.
t) thuˆo
.
c S v`a c´ac d¯ı
˙’
nh trung gian l`a phˆan biˆe
.
t v`a ta
.
o th`anh
mˆo
.
t tˆa
.
p con kh´ac trˆo
´

ng cu
˙’
a tˆa
.
p V \ S. Mˆo
.
t S−d¯u
.
`o
.
ng d¯i l`a mˆo
.
t S−bˆo
.
h`anh m`a c´ac d¯iˆe
˙’
m
d¯ˆa
`
u v`a cuˆo
´
i kh´ac nhau.
Ta c´o bˆo
˙’
d¯ˆe
`
sau:
Bˆo
˙’
d¯ˆe

`
5.3.19 Gia
˙’
su
.
˙’
µ = (v
0
, v
1
, . . . , v
p
) l`a d¯u
.
`o
.
ng d¯i so
.
cˆa
´
p cu
˙’
a G, S l`a tˆa
.
p c´ac d¯ı
˙’
nh cu
˙’
a
n´o v`a d¯ˇa

.
t v ∈ V \ S. Nˆe
´
u khˆong tˆo
`
n ta
.
i hai d¯ı
˙’
nh liˆen tiˆe
´
p v
k
v`a v
k+1
(0 ≤ k ≤ p − 1) cu
˙’
a µ
sao cho (v
k
, v) ∈ E v`a (v, v
k+1
) ∈ E th`ı
δ
S
(v) ≤ #S + 1.
143
Ch´u
.
ng minh. X´et c´ac tˆa

.
p con cu
˙’
a S \ {v
p
} :
A := {v
i
∈ S \ {v
p
} | (v
i
, v) ∈ E}
v`a
A := {v
i
∈ S \ {v
p
} | (v, v
i+1
) ∈ E}.
Theo gia
˙’
thiˆe
´
t, A ∩ B = ∅ v`a #(A ∪ B) ≤ #S − 1 (do v
p
/∈ A, v
p
/∈ B). Vˆa

.
y
δ
S
(v) ≤ #A + #B + 2 = #(A ∪ B) − #(A ∩ B) + 2 ≤ #S + 1,
d¯iˆe
`
u pha
˙’
i ch´u
.
ng minh. 
Bˆay gi`o
.
ch´ung ta ch´u
.
ng minh D
-
i
.
nh l´y 5.3.18.
Ch´u
.
ng minh cu
˙’
a D
-
i
.
nh l´y 5.3.18. X´et d¯ˆo

`
thi
.
G thoa
˙’
m˜an c´ac d¯iˆe
`
u kiˆe
.
n cu
˙’
a d¯i
.
nh l´y.
(1) V`ı G liˆen thˆong ma
.
nh nˆen tˆo
`
n ta
.
i mˆo
.
t ma
.
ch d¯ˆo
.
d`ai ´ıt nhˆa
´
t hai.
Ta n´oi ma

.
ch µ trong G l`a tu
.
.
a cu
.
.
c d¯a
.
i nˆe
´
u v´o
.
i mo
.
i d¯ı
˙’
nh v /∈ µ khˆong tˆo
`
n ta
.
i hai d¯ı
˙’
nh
v
k
v`a v
k+1
liˆen tiˆe
´

p trˆen ma
.
ch µ sao cho
(v
k
, v) ∈ U v`a (v
k+1
, v) ∈ U.
Hiˆe
˙’
n nhiˆen rˇa
`
ng d¯ˆe
˙’
kiˆe
˙’
m tra mˆo
.
t ma
.
ch c´o pha
˙’
i tu
.
.
a cu
.
.
c d¯a
.

i hay khˆong, hoˇa
.
c d¯ˆe
˙’
ph´at
hiˆe
.
n mˆo
.
t ma
.
ch d¯ˆo
.
d`ai l´o
.
n ho
.
n 1 ta cˆa
`
n thu
.
.
c hiˆe
.
n O(n
2
) ph´ep to´an so
.
cˆa
´

p.
Do d¯´o, thuˆa
.
t to´an xˆay du
.
.
ng mˆo
.
t ma
.
ch tu
.
.
a cu
.
.
c d¯a
.
i trong G bˇa
´
t d¯ˆa
`
u t`u
.
mˆo
.
t ma
.
ch tu`y
´y d¯`oi ho

˙’
i O(n
3
) ph´ep to´an so
.
cˆa
´
p.
Gia
˙’
su
.
˙’
µ l`a ma
.
ch tu
.
.
a cu
.
.
c d¯a
.
i, v`a k ´y hiˆe
.
u S l`a tˆa
.
p c´ac d¯ı
˙’
nh cu

˙’
a n´o. Nˆe
´
u S = V ta
d`u
.
ng: µ l`a ma
.
ch Hamilton. Ngu
.
o
.
.
c la
.
i, ta s˜e chı
˙’
ra rˇa
`
ng c´o thˆe
˙’
mo
.
˙’
rˆo
.
ng ma
.
ch µ d¯ˆe
˙’

nhˆa
.
n
d¯u
.
o
.
.
c mˆo
.
t ma
.
ch µ

c´o d¯ˆo
.
d`ai l´o
.
n ho
.
n, v`a do d¯´o, theo quy na
.
p, ta s˜e c´o mˆo
.
t ma
.
ch Hamilton.
(2) Ch´ung ta ch´u
.
ng minh tˆo

`
n ta
.
i mˆo
.
t S−d¯u
.
`o
.
ng d¯i trong G.
Bˇa
`
ng pha
˙’
n ch´u
.
ng, gia
˙’
su
.
˙’
khˆong tˆo
`
n ta
.
i S−d¯u
.
`o
.
ng d¯i. V`ı G liˆen thˆong ma

.
nh, tˆo
`
n ta
.
i
´ıt nhˆa
´
t mˆo
.
t S−bˆo
.
h`anh P m`a c´ac d¯ı
˙’
nh d¯ˆa
`
u cuˆo
´
i cu
˙’
a n´o l`a v ∈ S.
D
-
ˇa
.
t R l`a tˆa
.
p c´ac d¯ı
˙’
nh thuˆo

.
c P v`a kh´ac v; d¯ˇa
.
t T l`a tˆa
.
p c´ac d¯ı
˙’
nh cu
˙’
a G khˆong thuˆo
.
c
S ∪ R.
Theo gia
˙’
thiˆe
´
t khˆong tˆo
`
n ta
.
i S−d¯u
.
`o
.
ng d¯i nˆen khˆong tˆo
`
n ta
.
i d¯ı

˙’
nh thuˆo
.
c R v`a kˆe
`
v´o
.
i
mˆo
.
t d¯ı
˙’
nh trong S \ {v}.
144
Do d¯´o v´o
.
i mˆo
˜
i d¯ı
˙’
nh v
i
∈ R v`a d¯ı
˙’
nh v
j
∈ S \ {v} ta c´o
δ
R
(v

i
) ≤ 2#R − 2, δ
R
(v
j
) = 0,
δ
S
(v
i
) ≤ 2, δ
S
(v
j
) ≤ 2#S − 2.
Ho
.
n n˜u
.
a ta cˆa
`
n c´o
δ
T
(v
i
) + δ
T
(v
j

) ≤ 2#T.
(Nˆe
´
u khˆong, tˆo
`
n ta
.
i ´ıt nhˆa
´
t mˆo
.
t d¯u
.
`o
.
ng d¯i d¯ˆo
.
d`ai 2 hoˇa
.
c gi˜u
.
a v
i
v`a v
j
, hoˇa
.
c gi˜u
.
a v

j
v`a v
i
;
d¯u
.
`o
.
ng d¯i n`ay (c´o mˆo
.
t phˆa
`
n nˇa
`
m trˆen P ) ta
.
o th`anh mˆo
.
t S−d¯u
.
`o
.
ng d¯i).
C´o thˆe
˙’
ch´u
.
ng minh rˇa
`
ng c´ac d¯ı

˙’
nh v
i
v`a v
j
l`a hai d¯ı
˙’
nh khˆong kˆe
`
nhau sao cho
δ(v
i
) + δ(v
j
) = δ
S
(v
i
) + δ
R
(v
i
) + δ
T
(v
i
) + δ
S
(v
j

) + δ
R
(v
j
) + δ
T
(v
j
)
≤ 2(#R + #S + #T ) − 2 = 2 n − 2,
mˆau thuˆa
˜
n v´o
.
i gia
˙’
thiˆe
´
t.
(3) V`ı tˆo
`
n ta
.
i ´ıt nhˆa
´
t mˆo
.
t S−d¯u
.
`o

.
ng d¯i, ta s˜e t`ım mˆo
.
t S−d¯u
.
`o
.
ng d¯i P xuˆa
´
t ph´at t`u
.
x v`a kˆe
´
t
th´uc ta
.
i y sao cho d¯ˆo
.
d`ai cu
˙’
a d¯u
.
`o
.
ng d¯i con µ(x, y) t`u
.
x d¯ˆe
´
n y trˆen µ l`a nho
˙’

nhˆa
´
t (theo sˆo
´
c´ac cung).
V´o
.
i mˆo
.
t d¯ı
˙’
nh x ∈ S cho tru
.
´o
.
c, ch´ung ta c´o thˆe
˙’
su
.
˙’
du
.
ng thuˆa
.
t to´an t`ım kiˆe
´
m theo
chiˆe
`
u rˆo

.
ng trˆen d¯ˆo
`
thi
.
G nhu
.
d¯˜a tr`ınh b`ay trong Chu
.
o
.
ng 3. Phu
.
o
.
ng ph´ap n`ay d¯`oi ho
˙’
i O(m)
ph´ep to´an so
.
cˆa
´
p. Do d¯´o thuˆa
.
t to´an t`ım mˆo
.
t S−d¯u
.
`o
.

ng d¯i P v´o
.
i t´ınh chˆa
´
t d¯`oi ho
˙’
i cˆa
`
n nhiˆe
`
u
nhˆa
´
t O(mn) ph´ep to´an so
.
cˆa
´
p.
K´y hiˆe
.
u R l`a tˆa
.
p c´ac d¯ı
˙’
nh trung gian cu
˙’
a P, v`a S
1
l`a tˆa
.

p c´ac d¯ı
˙’
nh trung gian trˆen
d¯u
.
`o
.
ng d¯i µ(x, y) cu
˙’
a µ.
Nˆe
´
u S
1
= ∅ th`ı thay cung (x, y) bo
.
˙’
i S−d¯u
.
`o
.
ng d¯i P v`a ch´ung ta nhˆa
.
n d¯u
.
o
.
.
c mˆo
.

t ma
.
ch
µ

c´o d¯ˆo
.
d`ai l´o
.
n ho
.
n hoˇa
.
c bˇa
`
ng (#S + 1).
(4) Kˆe
´
tiˆe
´
p ta gia
˙’
su
.
˙’
S
1
= ∅, v`a d¯ˇa
.
t S

2
:= S \ S
1
v`a T l`a tˆa
.
p c´ac d¯ı
˙’
nh cu
˙’
a G khˆong thuˆo
.
c
R v`a S.
Ch´ung ta xˆay du
.
.
ng mˆo
.
t d¯u
.
`o
.
ng d¯i so
.
cˆa
´
p tu
.
.
a cu

.
.
c d¯a
.
i Q gi˜u
.
a y v`a x m`a tˆa
.
p c´ac d¯ı
˙’
nh
cu
˙’
a n´o l`a S

thoa
˙’
m˜an S

⊂ S v`a S
2
⊂ S

bˇa
`
ng phu
.
o
.
ng ph´ap lˇa

.
p nhu
.
sau:
1. Kho
.
˙’
i ta
.
o v´o
.
i Q := µ(x, y), S

:= S
2
, S

:= S
1
.
2. T`ım d¯ı
˙’
nh s ∈ S

sao cho (k, s) ∈ U v`a (s, l) ∈ U v´o
.
i hai d¯ı
˙’
nh k v`a l liˆen tiˆe
´

p trˆen Q.
(Nhˆa
.
n x´et rˇa
`
ng, d¯iˆe
`
u n`ay d¯`oi ho
˙’
i nhiˆe
`
u nhˆa
´
t O(n) ph´ep to´an so
.
cˆa
´
p). Nˆe
´
u khˆong tˆo
`
n
ta
.
i d¯ı
˙’
nh s nhu
.
vˆa
.

y (hoˇa
.
c l`a S

= ∅) th`ı d`u
.
ng: d¯u
.
`o
.
ng d¯i Q l`a tu
.
.
a cu
.
.
c d¯a
.
i (hoˇa
.
c cu
.
.
c
d¯a
.
i).
145
3. Gia
˙’

su
.
˙’
tˆo
`
n ta
.
i d¯ı
˙’
nh s th`ı ch`en n´o v`ao gi˜u
.
a hai d¯ı
˙’
nh k v`a l d¯ˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c mˆo
.
t d¯u
.
`o
.
ng
d¯i m´o

.
i Q

c´o d¯ˆo
.
d`ai l´o
.
n ho
.
n d¯u
.
`o
.
ng d¯i tru
.
´o
.
c d¯´o mˆo
.
t. Thay S

bo
.
˙’
i S

∪ {s}, S

bo
.

˙’
i
S

\ {s}, Q bo
.
˙’
i Q

v`a lˇa
.
p la
.
i Bu
.
´o
.
c 2.
Ch´u ´y rˇa
`
ng, sˆo
´
ph´ep to´an cˆa
`
n thu
.
.
c hiˆe
.
n trong thuˆa

.
t to´an n`ay khˆong vu
.
o
.
.
t qu´a O(n
3
).
Ta s˜e chı
˙’
ra rˇa
`
ng, kˆe
´
t th´uc thuˆa
.
t to´an th`ı S

= ∅.
Thˆa
.
t vˆa
.
y, gia
˙’
su
.
˙’
ngu

.
o
.
.
c la
.
i S

= ∅.
Theo c´ach xˆay du
.
.
ng cu
˙’
a P, c´ac d¯ı
˙’
nh cu
˙’
a R khˆong kˆe
`
v´o
.
i mˆo
.
t d¯ı
˙’
nh cu
˙’
a S
1

(v`ı nˆe
´
u
ngu
.
o
.
.
c la
.
i, ta c´o thˆe
˙’
t`ım mˆo
.
t S−d¯u
.
`o
.
ng d¯i m`a c´ac d¯ı
˙’
nh d¯ˆa
`
u cuˆo
´
i cu
˙’
a n´o gˆa
`
n µ ho
.

n P ). Do
d¯´o, v´o
.
i mo
.
i d¯ı
˙’
nh v
i
∈ R v`a mo
.
i d¯ı
˙’
nh v
j
∈ S
1
ta c´o
δ
R
(v
j
) = δ
S
1
(v
i
) = 0.
Mˇa
.

t kh´ac, v`ı µ l`a ma
.
ch tu
.
.
a cu
.
.
c d¯a
.
i, d¯ı
˙’
nh v
i
thoa
˙’
m˜an c´ac gia
˙’
thiˆe
´
t cu
˙’
a Bˆo
˙’
d¯ˆe
`
5.3.19 v´o
.
i
d¯u

.
`o
.
ng d¯i con µ(x, y) sao cho
δ
S
2
(v
i
) ≤ #S
2
+ 1.
Cho
.
n v
j
∈ S

⊂ S
1
. Theo c´ach xˆay du
.
.
ng cu
˙’
a Q, ´ap du
.
ng la
.
i Bˆo

˙’
d¯ˆe
`
5.3.19 v´o
.
i d¯ı
˙’
nh v
j
v`a
d¯u
.
`o
.
ng d¯i Q, ta d¯u
.
o
.
.
c
δ
S

(v
j
) ≤ #S

+ 1.
Mˇa
.

t kh´ac, ta cˆa
`
n c´o (nhu
.
d¯˜a ch´u
.
ng minh trong Phˆa
`
n (2))
δ
T
(v
i
) + δ
T
(v
j
) ≤ 2#T
(ngu
.
o
.
.
c la
.
i, ta c´o thˆe
˙’
t`ım mˆo
.
t S−d¯u

.
`o
.
ng d¯i m`a c´ac d¯ı
˙’
nh d¯ˆa
`
u cuˆo
´
i cu
˙’
a n´o gˆa
`
n µ ho
.
n P ).
Cuˆo
´
i c`ung, ta luˆon luˆon c´o
δ
S

(v
j
) ≤ 2#S

− 2, v`a δ
R
(v
i

) ≤ 2#R − 2.
Suy ra
δ(v
i
) + δ(v
j
) ≤ 2#R + #S
2
+ 2#S

+ #S

− 2
v`a
#S
2
≤ #S

⇒ δ(v
i
) + δ(v
j
) ≤ 2n − 2
v´o
.
i hai d¯ı
˙’
nh khˆong kˆe
`
nhau v

i
v`a v
j
, mˆau thuˆa
˜
n v´o
.
i gia
˙’
thiˆe
´
t.
Vˆa
.
y S

= ∅ v`a t`u
.
d¯u
.
`o
.
ng d¯i Q v´o
.
i S−d¯u
.
`o
.
ng d¯i P ta c´o thˆe
˙’

xˆay du
.
.
ng mˆo
.
t ma
.
ch µ

c´o
d¯ˆo
.
d`ai ≥ #S + 1.
(5) Trong tˆa
´
t ca
˙’
c´ac tru
.
`o
.
ng ho
.
.
p (tham kha
˙’
o c´ac Phˆa
`
n (3) v`a (4) trˆen) khi #S < n ta c´o
thˆe

˙’
t`ım (nhiˆe
`
u nhˆa
´
t O(mn + n
3
) ph´ep to´an so
.
cˆa
´
p) mˆo
.
t ma
.
ch µ

c´o d¯ˆo
.
d`ai l´o
.
n ho
.
n ma
.
ch
146
c˜u 1. Tru
.
´o

.
c khi lˇa
.
p la
.
i thuˆa
.
t to´an, ta cˆa
`
n kiˆe
˙’
m tra µ

c´o pha
˙’
i l`a ma
.
ch tu
.
.
a cu
.
.
c d¯a
.
i. (Nˆe
´
u
khˆong pha
˙’

i, xˆay du
.
.
ng mˆo
.
t ma
.
ch tu
.
.
a cu
.
.
c d¯a
.
i µ

t`u
.
µ

-d¯`oi ho
˙’
i nhiˆe
`
u nhˆa
´
t O(n
3
) ph´ep to´an

so
.
cˆa
´
p).
Sau nhiˆe
`
u nhˆa
´
t (n − 1) lˆa
`
n lˇa
.
p mo
.
˙’
rˆo
.
ng ma
.
ch, thuˆa
.
t to´an cho ch´ung ta mˆo
.
t ma
.
ch
Hamilton cu
˙’
a d¯ˆo

`
thi
.
G. D
-
i
.
nh l´y 5.3.18 d¯u
.
o
.
.
c ch´u
.
ng minh bˇa
`
ng thuˆa
.
t to´an kiˆe
´
n thiˆe
´
t c´ach
xˆay du
.
.
ng ma
.
ch Hamilton v´o
.

i d¯ˆo
.
ph´u
.
c ta
.
p thuˆa
.
t to´an l`a O ( n
4
). 
147
148
Chu
.
o
.
ng 6
D
-
ˆo
`
thi
.
phˇa
˙’
ng
Ch´ung ta d¯˜a nghiˆen c´u
.
u c´ac t´ınh chˆa

´
t cu
˙’
a c´ac d¯ˆo
`
thi
.
con, chˇa
˙’
ng ha
.
n, c´ac dˆay chuyˆe
`
n, chu
tr`ınh v`a c´ac cˆay bao tr`um trong mˆo
.
t d¯ˆo
`
thi
.
d¯˜a cho. Trong chu
.
o
.
ng n`ay, ch´ung ta s˜e nghiˆen
c´u
.
u to`an bˆo
.
d¯ˆo

`
thi
.
G v´o
.
i cˆau ho
˙’
i sau: khi n`ao G l`a phˇa
˙’
ng?
Chu
.
o
.
ng n`ay bˇa
´
t d¯ˆa
`
u v´o
.
i hai v´ı du
.
vˆe
`
d¯ˆo
`
thi
.
Kuratowski d¯´ong vai tr`o trung tˆam trong
viˆe

.
c kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
. Kˆe
´
tiˆe
´
p l`a c´ac t´ınh chˆa
´
t cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng, chˇa
˙’
ng ha
.
n

d¯i
.
nh l´y Euler v`a gia
˙’
thuyˆe
´
t bˆo
´
n m`au nˆo
˙’
i tiˆe
´
ng “mo
.
i d¯ˆo
`
thi
.
phˇa
˙’
ng l`a 4−sˇa
´
c” (ph´at biˆe
˙’
u nˇam
1850 v`a d¯u
.
o
.
.

c ch´u
.
ng minh nˇam 1976). Ch´ung ta c˜ung t`ım hiˆe
˙’
u tiˆeu chuˆa
˙’
n cˆa
`
n v`a d¯u
˙’
d¯ˆe
˙’
d¯ˆo
`
thi
.
l`a phˇa
˙’
ng-D
-
i
.
nh l´y Kuratowski. Cuˆo
´
i c`ung l`a d¯ˆo
´
i ngˆa
˜
u h`ınh ho
.

c cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng.
6.1 D
-
i
.
nh ngh˜ıa v`a c´ac v´ı du
.
Nhˇa
´
c la
.
i rˇa
`
ng d¯ˆo
`
thi
.
G d¯u
.
o
.
.

c go
.
i l`a phˇa
˙’
ng nˆe
´
u tˆo
`
n ta
.
i mˆo
.
t ph´ep biˆe
˙’
u diˆe
˜
n G lˆen mˆo
.
t mˇa
.
t
phˇa
˙’
ng sao cho hai ca
.
nh bˆa
´
t k`y cu
˙’
a d¯ˆo

`
thi
.
khˆong cˇa
´
t nhau ngoa
.
i tr`u
.
ta
.
i d¯ı
˙’
nh cu
˙’
a ch´ung. C´ac
d¯ˆo
`
thi
.
m`a c´o thˆe
˙’
biˆe
´
n d¯ˆo
˙’
i cho tr`ung nhau bˇa
`
ng ph´ep biˆe
´

n da
.
ng co d˜an liˆen tu
.
c trˆen mˇa
.
t
phˇa
˙’
ng th`ı khˆong coi l`a nh˜u
.
ng d¯ˆo
`
thi
.
phˇa
˙’
ng kh´ac nhau. Theo d¯i
.
nh ngh˜ıa, d¯ˆo
`
thi
.
trong H`ınh
6.1 l`a phˇa
˙’
ng.
V´ı du
.
6.1.1 (B`ai to´an ba biˆe

.
t thu
.
.
v`a ba nh`a m´ay). C´o ba biˆe
.
t thu
.
.
a, b, c v`a ba nh`a m´ay:
mˆo
.
t nh`a m´ay nu
.
´o
.
c d, mˆo
.
t nh`a m´ay ho
.
i d¯ˆo
´
t e v`a mˆo
.
t nh`a m´ay d¯iˆe
.
n f. Mˆo
˜
i biˆe
.

t thu
.
.
nˆo
´
i v´o
.
i
c´ac nh`a m´ay bˇa
`
ng nh˜u
.
ng ˆo
´
ng dˆa
˜
n nu
.
´o
.
c, ˆo
´
ng dˆa
˜
n ho
.
i v`a d¯u
.
`o
.

ng dˆay d¯iˆe
.
n. Vˆa
.
y c´o thˆe
˙’
v˜e
trˆen mˇa
.
t phˇa
˙’
ng ba biˆe
.
t thu
.
.
v`a ba nh`a m´ay v`a tˆa
´
t ca
˙’
c´ac d¯u
.
`o
.
ng vˆa
.
n chuyˆe
˙’
n sao cho khˆong
c´o hai d¯u

.
`o
.
ng n`ao cˇa
´
t nhau o
.
˙’
mˆo
.
t d¯iˆe
˙’
m kh´ac c´ac d¯ˆa
`
u m´ut cu
˙’
a ch´ung hay khˆong? Ta c´o mˆo
h`ınh ho´a bo
.
˙’
i d¯ˆo
`
thi
.
hai phˆa
`
n K
3,3
: C´ac d¯ı
˙’

nh cu
˙’
a d¯ˆo
`
thi
.
tu
.
o
.
ng ´u
.
ng c´ac nh`a v`a c´ac nh`a m´ay
149

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
d
•
c
•
e
•
b
•
a
•

H`ınh 6.1: V´ı du
.
vˆe
`
d¯ˆo
`
thi
.
phˇa
˙’
ng.
(xem H`ınh 6.2); mˆo
.
t ca
.
nh liˆen thuˆo
.
c hai d¯ı
˙’
nh tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t nh`a v`a mˆo

.
t nh`a m´ay. B`ai
to´an d¯u
.
a vˆe
`
kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
Kuratowski K
3,3
. Bˇa
`
ng thu
.
.
c nghiˆe
.
m c´o thˆe
˙’
chı
˙’
ra rˇa

`
ng d¯ˆo
`
thi
.
n`ay khˆong phˇa
˙’
ng.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
•
b
•
c
•
d
•
e
•
f
•

H`ınh 6.2: D
-
ˆo
`
thi
.
Kuratowski K
3,3
.
V´ı du
.
6.1.2 C˜ung bˇa
`
ng thu
.
.
c nghiˆe
.
m, c´o thˆe
˙’
ch´u
.
ng to
˙’
d¯ˆo
`
thi
.
d¯ˆa
`

y d¯u
˙’
K
5
(xem H`ınh 6.3)
l`a khˆong phˇa
˙’
ng.
Vˆe
`
t´ınh khˆong phˇa
˙’
ng cu
˙’
a c´ac d¯ˆo
`
thi
.
K
3,3
v`a K
5
s˜e d¯u
.
o
.
.
c gia
˙’
i th´ıch trong nh˜u

.
ng phˆa
`
n
sau. Ch´u ´y rˇa
`
ng c´ac d¯ˆo
`
thi
.
K
5
v`a K
3,3
c´o nh˜u
.
ng t´ınh chˆa
´
t:
1. Ca
˙’
hai l`a khˆong phˇa
˙’
ng;
2. Nˆe
´
u xo´a mˆo
.
t ca
.

nh hoˇa
.
c mˆo
.
t d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
th`ı s˜e nhˆa
.
n d¯u
.
o
.
.
c mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng.
150
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
•
b
•
c
•
d
•
e
•
H`ınh 6.3: D
-

ˆo
`
thi
.
Kuratowski K
5
.
3. K
5
l`a d¯ˆo
`
thi
.
khˆong phˇa
˙’
ng c´o sˆo
´
d¯ı
˙’
nh ´ıt nhˆa
´
t; K
3,3
l`a d¯ˆo
`
thi
.
khˆong phˇa
˙’
ng c´o sˆo

´
ca
.
nh ´ıt
nhˆa
´
t.
6.2 C´ac biˆe
˙’
u diˆe
˜
n kh´ac nhau cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng
Tru
.
´o
.
c hˆe
´
t ta c´o kˆe
´

t qua
˙’
sau.
D
-
i
.
nh l´y 6.2.1 [Fary] Mo
.
i d¯o
.
n d¯ˆo
`
thi
.
phˇa
˙’
ng c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n trˆen mˆo
.
t mˇa
.
t phˇa
˙’
ng sao cho

c´ac ca
.
nh l`a c´ac d¯oa
.
n thˇa
˙’
ng v`a ch´ung chı
˙’
cˇa
´
t nhau ta
.
i c´ac d¯ı
˙’
nh chung.
Ch´u
.
nh minh. Ch´u
.
ng minh cu
˙’
a d¯i
.
nh l´y n`ay kh´a ph´u
.
c ta
.
p v`a khˆong d¯´ong g´op nhiˆe
`
u trong

viˆe
.
c hiˆe
˙’
u t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
. Ba
.
n d¯o
.
c quan tˆam c´o thˆe
˙’
xem [24]. Chˇa
˙’
ng ha
.
n, d¯ˆo
`
thi
.
trong H`ınh 6.1 c´o thˆe
˙’
v˜e la
.

i chı
˙’
su
.
˙’
du
.
ng c´ac d¯oa
.
n thˇa
˙’
ng nhu
.
trong H`ınh 6.4. Trong d¯i
.
nh
l´y n`ay, d¯ˆo
`
thi
.
cˆa
`
n pha
˙’
i d¯o
.
n v`ı c´ac khuyˆen hoˇa
.
c mˆo
.

t trong hai ca
.
nh song song khˆong thˆe
˙’
v˜e
bo
.
˙’
i c´ac d¯oa
.
n thˇa
˙’
ng. 
Diˆe
.
n
K´y hiˆe
.
u R(G) l`a d¯ˆo
`
thi
.
phˇa
˙’
ng G d¯u
.
o
.
.
c biˆe

˙’
u diˆe
˜
n trˆen mˇa
.
t phˇa
˙’
ng. C´ac v`ung liˆen thˆong (theo
tˆo pˆo cu
˙’
a mˇa
.
t phˇa
˙’
ng R
2
) cu
˙’
a tˆa
.
p R
2
\ R(G) go
.
i l`a c´ac diˆe
.
n. Mˆo
.
t diˆe
.

n l`a mˆo
.
t v`ung cu
˙’
a mˇa
.
t
phˇa
˙’
ng d¯u
.
o
.
.
c gi´o
.
i ha
.
n bo
.
˙’
i c´ac ca
.
nh go
.
i l`a biˆen; hai diˆe
.
n go
.
i l`a kˆe

`
nhau nˆe
´
u c´ac d¯u
.
`o
.
ng biˆen
cu
˙’
a ch´ung c´o ´ıt nhˆa
´
t mˆo
.
t ca
.
nh chung.
151
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
d
•
c
•
e
•
b
•
a
•
H`ınh 6.4:
N´oi chung, biˆen cu
˙’
a diˆe
.

n gˆo
`
m c´ac chu tr`ınh d¯o
.
n gia
˙’
n v´o
.
i c´ac ca
.
nh r`o
.
i nhau, c´ac ca
.
nh
treo (ca
.
nh c´o mˆo
.
t d¯ı
˙’
nh bˆa
.
c mˆo
.
t), hoˇa
.
c c´ac ca
.
nh nˆo

´
i hai chu tr`ınh. Diˆe
.
n ph´ıa ngo`ai, go
.
i
l`a diˆe
.
n vˆo ha
.
n, luˆon luˆon tˆo
`
n ta
.
i mˆo
.
t chu tr`ınh l`a d¯u
.
`o
.
ng biˆen ch´u
.
a bˆen trong n´o c´ac ca
.
nh
kh´ac; d¯´o l`a chu tuyˆe
´
n cu
˙’
a diˆe

.
n vˆo ha
.
n.
V´ı du
.
6.2.2 Ba
˙’
n d¯ˆo
`
d¯i
.
a l´y l`a d¯ˆo
`
thi
.
tˆo pˆo phˇa
˙’
ng khˆong c´o cˆa
`
u; d¯ˆo
`
thi
.
d¯´o c´o t´ınh chˆa
´
t d¯ˇa
.
c
biˆe

.
t l`a: bˆa
.
c cu
˙’
a mˆo
˜
i d¯ı
˙’
nh ≥ 3. Mˆo
.
t diˆe
.
n c´o thˆe
˙’
kˆe
`
v´o
.
i diˆe
.
n kh´ac o
.
˙’
nhiˆe
`
u ca
.
nh. Trˆen H`ınh
6.5 ta ch ´u ´y rˇa

`
ng c´ac diˆe
.
n d v`a g khˆong kˆe
`
nhau mˇa
.
c d`u ch´ung c´o mˆo
.
t d¯ı
˙’
nh chung; a l`a diˆe
.
n
vˆo ha
.
n.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.



.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
a
b
c
d
e
g
f
h
H`ınh 6.5:
152
Biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t cˆa
`

u
D
-
ˆe
˙’
tr´anh phˆan biˆe
.
t gi˜u
.
a c´ac diˆe
.
n h˜u
.
u ha
.
n v`a diˆe
.
n vˆo ha
.
n, ch´ung ta thu
.
`o
.
ng biˆe
˙’
u diˆe
˜
n c´ac
d¯ˆo
`

thi
.
phˇa
˙’
ng trˆen mˇa
.
t cˆa
`
u S
2
⊂ R
3
du
.
.
a v`ao ph´ep chiˆe
´
u nˆo
˙’
i t`u
.
S
2
lˆen R
2
. K´y hiˆe
.
u S l`a
d¯iˆe
˙’

m tiˆe
´
p x´uc cu
˙’
a mˇa
.
t cˆa
`
u v´o
.
i mˇa
.
t phˇa
˙’
ng, v`a N l`a d¯iˆe
˙’
m thuˆo
.
c mˇa
.
t cˆa
`
u sao cho NS vuˆong
g´oc v´o
.
i mˇa
.
t phˇa
˙’
ng. V´o

.
i mˆo
˜
i d¯iˆe
˙’
m P ∈ S
2
, P = N, d¯u
.
`o
.
ng thˇa
˙’
ng NP cˇa
´
t mˇa
.
t phˇa
˙’
ng R
2
ta
.
i
d¯´ung mˆo
.
t d¯iˆe
˙’
m Q. Nhu
.

vˆa
.
y ta c´o tu
.
o
.
ng ´u
.
ng mˆo
.
t-mˆo
.
t t`u
.
mˇa
.
t cˆa
`
u (bo
˙’
d¯i d¯iˆe
˙’
m N) lˆen mˇa
.
t
phˇa
˙’
ng.
Theo c´ach xˆay du
.

.
ng n`ay, hiˆe
˙’
n nhiˆen rˇa
`
ng d¯ˆo
`
thi
.
l`a phˇa
˙’
ng nˆe
´
u v`a chı
˙’
nˆe
´
u c´o thˆe
˙’
biˆe
˙’
u
diˆe
˜
n n´o trˆen mˆo
.
t mˇa
.
t cˆa
`

u sao cho c´ac ca
.
nh cu
˙’
a n´o khˆong cˇa
´
t nhau ngo`ai c´ac d¯ı
˙’
nh chung.
Do d¯´o, theo D
-
i
.
nh l´y 6.2.1 ta c´o
D
-
i
.
nh l´y 6.2.3 Mˆo
.
t d¯ˆo
`
thi
.
c´o thˆe
˙’
biˆe
˙’
u diˆe
˜

n trˆen mˇa
.
t cˆa
`
u sao cho c´ac ca
.
nh khˆong tu
.
.
cˇa
´
t
nˆe
´
u v`a chı
˙’
nˆe
´
u n´o c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n phˇa
˙’
ng trˆen mˇa
.
t phˇa
˙’

ng.
Mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t cˆa
`
u s˜e phˆan chia mˇa
.
t cˆa
`
u th`anh nhiˆe
`
u v`ung
kh´ac nhau. Mˆo

˜
i v`ung trˆen mˇa
.
t cˆa
`
u l`a miˆe
`
n gi´o
.
i nˆo
.
i, diˆe
.
n vˆo ha
.
n trˆen mˇa
.
t phˇa
˙’
ng d¯u
.
o
.
.
c ´anh
xa
.
th`anh v`ung trˆen mˇa
.
t cˆa

`
u ch´u
.
a d¯iˆe
˙’
m cu
.
.
c bˇa
´
c N. Hiˆe
˙’
n nhiˆen rˇa
`
ng, bˇa
`
ng ph´ep quay th´ıch
ho
.
.
p qua
˙’
cˆa
`
u ch´ung ta c´o thˆe
˙’
´anh xa
.
mˆo
.

t v`ung bˆa
´
t k`y th`anh diˆe
.
n vˆo ha
.
n trˆen mˇa
.
t phˇa
˙’
ng.
T`u
.
d¯´o ta nhˆa
.
n d¯u
.
o
.
.
c:
D
-
i
.
nh l´y 6.2.4 Mˆo
.
t d¯ˆo
`
thi

.
phˇa
˙’
ng c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n trˆen mˆo
.
t mˇa
.
t phˇa
˙’
ng sao cho diˆe
.
n bˆa
´
t k`y
cho tru
.
´o
.
c l`a diˆe
.
n vˆo ha
.
n.
Mˆo

´
i liˆen quan c´ac v`ung trˆen mˇa
.
t cˆa
`
u cho ph´ep ch´ung ta thˆa
´
y rˇa
`
ng khˆong c´o su
.
.
phˆan
biˆe
.
t thu
.
.
c su
.
.
gi˜u
.
a diˆe
.
n vˆo ha
.
n v`a c´ac diˆe
.
n h˜u

.
u ha
.
n trˆen mˇa
.
t phˇa
˙’
ng. Do d¯´o, khi n´oi vˆe
`
c´ac
v`ung trong mˆo
.
t biˆe
˙’
u diˆe
˜
n cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng trˆen mˇa
.
t phˇa
˙’
ng, ch´ung ta x´et ca
˙’

diˆe
.
n vˆo ha
.
n.
Ngo`ai ra, do khˆong c´o su
.
.
kh´ac nhau cˆo
´
t yˆe
´
u gi˜u
.
a c´ac ph´ep biˆe
˙’
u diˆe
˜
n d¯ˆo
`
thi
.
trˆen mˆo
.
t mˇa
.
t
phˇa
˙’
ng hay mˇa

.
t cˆa
`
u (mˇa
.
t phˇa
˙’
ng c´o thˆe
˙’
xem l`a mˇa
.
t cˆa
`
u bo
˙’
d¯i mˆo
.
t d¯iˆe
˙’
m), thuˆa
.
t ng˜u
.
“biˆe
˙’
u
diˆe
˜
n phˇa
˙’

ng” cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
thu
.
`o
.
ng d¯u
.
o
.
.
c su
.
˙’
du
.
ng d¯ˆe
˙’
bao h`am c´ac ph´ep biˆe
˙’
u diˆe
˜
n trˆen mˇa
.

t
cˆa
`
u c˜ung nhu
.
trˆen mˇa
.
t phˇa
˙’
ng.
Biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t phˇa
˙’
ng v`a t´ınh liˆen thˆong
Trong mˆo
.
t d¯ˆo
`
thi
.
khˆong liˆen thˆong, viˆe
.
c biˆe
˙’
u diˆe

˜
n mˆo
˜
i th`anh phˆa
`
n trˆen mˇa
.
t phˇa
˙’
ng c´o thˆe
˙’
d¯u
.
o
.
.
c kha
˙’
o s´at mˆo
.
t c´ach d¯ˆo
.
c lˆa
.
p. Do d¯´o, d¯ˆo
`
thi
.
l`a phˇa
˙’

ng nˆe
´
u v`a chı
˙’
nˆe
´
u c´ac th`anh phˆa
`
n
liˆen thˆong cu
˙’
a n´o l`a phˇa
˙’
ng. Tu
.
o
.
ng tu
.
.
, trong mˆo
.
t d¯ˆo
`
thi
.
t´ach d¯u
.
o
.

.
c (t´u
.
c 1−liˆen thˆong) viˆe
.
c
153
biˆe
˙’
u diˆe
˜
n mˆo
˜
i khˆo
´
i (t´u
.
c l`a d¯ˆo
`
thi
.
con khˆong t´ach d¯u
.
o
.
.
c cu
.
.
c d¯a

.
i) trˆen mˇa
.
t phˇa
˙’
ng c´o thˆe
˙’
d¯u
.
o
.
.
c
kha
˙’
o s´at d¯ˆo
.
c lˆa
.
p. Do d¯´o mˆo
.
t d¯ˆo
`
thi
.
t´ach d¯u
.
o
.
.

c l`a phˇa
˙’
ng nˆe
´
u v`a chı
˙’
nˆe
´
u mˆo
˜
i khˆo
´
i l`a phˇa
˙’
ng.
Vˆa
.
y, kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
chı
˙’
cˆa

`
n x´et d¯ˆo
´
i v´o
.
i d¯ˆo
`
thi
.
khˆong t´ach d¯u
.
o
.
.
c.
Mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng khˆong t´ach d¯u
.
o
.
.
c c´o thˆe
˙’

biˆe
˙’
u diˆe
˜
n duy nhˆa
´
t lˆen mˆo
.
t mˇa
.
t cˆa
`
u khˆong?
Tru
.
´o
.
c khi tra
˙’
l`o
.
i cˆau ho
˙’
i n`ay, ch´ung ta cˆa
`
n gia
˙’
i th´ıch ´y ngh˜ıa cu
˙’
a t`u

.
“biˆe
˙’
u diˆe
˜
n duy nhˆa
´
t”.
Hai biˆe
˙’
u diˆe
˜
n cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng l`a giˆo
´
ng nhau nˆe
´
u ch´ung c´o thˆe
˙’
l`am tr`ung nhau bˇa
`

ng
ph´ep quay mˇa
.
t cˆa
`
u n`ay th`anh mˇa
.
t cˆa
`
u kia v`a c´o thˆe
˙’
biˆe
´
n da
.
ng c´ac v`ung (khˆong di chuyˆe
˙’
n
d¯ı
˙’
nh bˇang qua ca
.
nh). Nˆe
´
u tˆa
´
t ca
˙’
c´ac ph´ep biˆe
˙’

u diˆe
˜
n lˆen mˆo
.
t mˇa
.
t cˆa
`
u l`a tr`ung nhau th`ı ta
n´oi d¯ˆo
`
thi
.
c´o duy nhˆa
´
t mˆo
.
t ph´ep biˆe
˙’
u diˆe
˜
n. D
-
i
.
nh l´y du
.
´o
.
i d¯ˆay, cho ch´ung ta ch´ınh x´ac cˆau

tra
˙’
l`o
.
i khi n`ao th`ı mˆo
.
t d¯ˆo
`
thi
.
d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n duy nhˆa
´
t trˆen mˆo
.
t mˇa
.
t cˆa
`
u.
D
-

i
.
nh l´y 6.2.5 [Whitney] Ph´ep biˆe
˙’
u diˆe
˜
n lˆen mˇa
.
t cˆa
`
u cu
˙’
a mˆo
˜
i d¯ˆo
`
thi
.
phˇa
˙’
ng 3−liˆen thˆong
l`a duy nhˆa
´
t.
Ch´u
.
ng minh. Xem [54]. 
D
-
i

.
nh l´y n`ay d¯´ong mˆo
.
t vai tr`o quan tro
.
ng trong viˆe
.
c x´ac d¯i
.
nh xem mˆo
.
t d¯ˆo
`
thi
.
c´o phˇa
˙’
ng
hay khˆong: V´o
.
i c´ac d¯ˆo
`
thi
.
3−liˆen thˆong, nˆe
´
u c´o thˆe
˙’
biˆe
˙’

u diˆe
˜
n trˆen mˆo
.
t mˇa
.
t cˆa
`
u th`ı ph´ep
biˆe
˙’
u diˆe
˜
n n`ay l`a duy nhˆa
´
t.
6.3 C´ac t´ınh chˆa
´
t cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng
Phˆa
`
n n`ay liˆe

.
t kˆe nghiˆen c´u
.
u mˆo
.
t sˆo
´
t´ınh chˆa
´
t co
.
ba
˙’
n cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng. Tru
.
´o
.
c hˆe
´
t ta c´o
D
-

i
.
nh l´y 6.3.1 [Berge] Trong mˆo
.
t d¯ˆo
`
thi
.
tˆo pˆo phˇa
˙’
ng, c´ac chu tuyˆe
´
n cu
˙’
a diˆe
.
n h˜u
.
u ha
.
n ta
.
o
th`anh mˆo
.
t hˆe
.
co
.
so

.
˙’
c´ac chu tr`ınh d¯ˆo
.
c lˆa
.
p.
Ch´u
.
ng minh. Ch´ung ta s˜e ch´u
.
ng minh bˇa
`
ng quy na
.
p theo sˆo
´
diˆe
.
n f cu
˙’
a d¯ˆo
`
thi
.
G.
Hiˆe
˙’
n nhiˆen d¯i
.

nh l´y d¯´ung khi G c´o mˆo
.
t hoˇa
.
c hai diˆe
.
n h˜u
.
u ha
.
n. Gia
˙’
su
.
˙’
d¯i
.
nh l´y d¯´ung
cho mo
.
i d¯ˆo
`
thi
.
phˇa
˙’
ng c´o sˆo
´
diˆe
.

n h˜u
.
u ha
.
n l`a (f − 1); ta ch´u
.
ng minh d¯i
.
nh l´y d¯ ´ung cho mo
.
i
d¯ˆo
`
thi
.
phˇa
˙’
ng c´o f diˆe
.
n h˜u
.
u ha
.
n.
Thˆa
.
t vˆa
.
y, gia
˙’

su
.
˙’
khˆong pha
˙’
i tˆa
´
t ca
˙’
c´ac chu tuyˆe
´
n d¯ˆe
`
u l`a c´ac chu tr`ınh khˆong giao nhau
(theo ngh˜ıa l`a c´o ca
.
nh chung) v`ı v´o
.
i tru
.
`o
.
ng ho
.
.
p d¯´o th`ı d¯i
.
nh l´y l`a hiˆe
˙’
n nhiˆen. Khi d¯´o ta c´o

thˆe
˙’
bo
˙’
b´o
.
t mˆo
.
t ca
.
nh e n`ao d¯´o cu
˙’
a G v`a d¯u
.
o
.
.
c d¯ˆo
`
thi
.
G

c´o (f − 1) diˆe
.
n h˜u
.
u ha
.
n m`a c´ac chu

154