Chu
.
o
.
ng 5
B`ai to´an Euler v`a b`ai to´an Hamilton
L´y thuyˆe
´
t d¯ˆo
`
thi
.
ph´at triˆe
˙’
n bˇa
´
t nguˆo
`
n t`u
.
nh˜u
.
ng b`ai to´an cˆo
˙’
d¯iˆe
˙’
n, trong sˆo
´
d¯´o b`ai to´an Euler
v`a b`ai to´an Hamilton t`ım h`anh tr`ınh d¯i qua mˆo

.
ng du
.
ng: c´ac b`ai to´an t`ım h`anh tr`ınh tˆo
´
t
nhˆa
´
t (ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa, ngu
.
`o
.
i ch`ao h`ang), tu
.
.
d¯ˆo
.
ng ho´a thiˆe
´
t kˆe
´
bˇa

˙’
i quyˆe
´
t ch´ung l`a rˆa
´
t kh´ac nhau.
Ch´ung ta s˜e ch ´u
.
ng minh rˇa
`
ng trong d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng, tˆo
`
n ta
.
i thuˆa
.
t to´an d¯a th´u
.
c t`ım
h`anh tr`ınh Euler v`a b`ai to´an ngu
.
`o

.
t to´an n`ay s˜e d¯u
.
o
.
.
c tr`ınh
b`ay trong c´ac Phˆa
`
n 5.1 v`a 5.2.
Mˇa
.
t kh´ac, vˆa
´
n d¯ˆe
`
tˆo
`
n ta
.
i chu tr`ınh hay ma
.
ch Hamilton l`a nh˜u
.
ng b`ai to´an khˆong d¯a
th´u
.
c khˆong d¯u
.
o

ch´ınh liˆen quan d¯ˆe
´
n su
.
.
tˆo
`
n ta
.
i cu
˙’
a c´ac chu tr`ınh
hay ma
.
ch Hamilton. Khi c´o d¯iˆe
`
u kiˆe
.
n, c´ac ch´u
.
ng minh c´o t´ınh kiˆe
´
n thiˆe
´
t thuˆa
.
t to´an hoˇa
.
c
c´o thˆe

ng (d¯o
.
n hoˇa
.
c d¯a d¯ˆo
`
thi
.
). Dˆay chuyˆe
`
n
127

Euler l`a dˆay chuyˆe
`
n ch´u
.
a tˆa
´
t ca
˙’
c´ac ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
, mˆo

.
i dˆan th`anh phˆo
´
K¨onigsberg cu
˙’
a nu
.
´o
.
c Nga (sau n`ay l`a th`anh phˆo
´
Kaliningrat) d¯˜a t`u
.
ng thˇa
´
c mˇa
´
c vˆa
´
n d¯ˆe
`
nhu
.
sau: Th`anh phˆo
´
c´o sˆong Pregel cha
˙’
y qua, gi˜u
.
a sˆong c´o c`u lao Kneiphof, v`a c´o 7 chiˆe

´
u ta coi mˆo
˜
i khu vu
.
.
c a, b, c, d cu
˙’
a th`anh phˆo
´
nhu
.
mˆo
.
t d¯ı
˙’
nh, mˆo
˜
i cˆa
`
u
qua la
.
i hai khu vu
.
.
c nhu
.
mˆo
.

´
ch´ınh l`a: c´o thˆe
˙’
v˜e d¯u
.
o
.
.
c d¯ˆo
`
thi
.
bˇa
`
ng mˆo
.
t n´et b´ut liˆe
`
n hay khˆong? N´oi c´ach kh´ac: tˆo
`
n ta
.
i chu tr`ınh Euler?
Nh`a to´an ho
.
c L. Euler (1707-1783) l`a ngu
.
`o
.
i d¯ˆa

a
b
c
d
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.

.

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

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

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

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

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

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


.

.
.
.

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

.
.

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

.
(a)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

o
.
ng d¯u
.
o
.
ng.
D
-
i
.
nh l´y 5.1.3 [Euler] D
-
a d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng liˆen thˆong G = (V, E) c´o dˆay chuyˆe
`
n Euler nˆe
´
u
v`a chı
˙’
nˆe
´

.
a dˆay chuyˆe
`
n
hoˇa
.
c chu tr`ınh Euler.
Bˆay gi`o
.
ta ch´u
.
ng minh d¯iˆe
`
u kiˆe
.
n cˆa
`
n. Nˆe
´
u µ l`a dˆay chuyˆe
`
n Euler, th`ı chı
˙’
c´o hai d¯ı
˙’
nh
d¯ˆa
`
u v`a cuˆo
´

bˇa
`
ng quy na
.
p theo sˆo
´
ca
.
nh m cu
˙’
a G. Hiˆe
˙’
n nhiˆen
d¯i
.
nh l´y d¯´ung nˆe
´
u m = 1. Gia
˙’
su
.
˙’
d¯i
.
nh l´y d¯´ung cho mo
.
i d¯ˆo
`
thi
.

c chˇa
˜
n, cho
.
n
d¯ı
˙’
nh a bˆa
´
t k`y v`a lˆa
´
y b = a). K´y hiˆe
.
u µ l`a dˆay chuyˆe
`
n m`a ta d¯i trˆen d¯ˆo
`
thi
.
G xuˆa
´
t ph´at t`u
.
a
theo hu
.
´o
.
ng tu`y ´y, d¯i qua mˆo
˜

˙’
ca
.
nh liˆen thuˆo
.
c v´o
.
i x nˆen c´o thˆe
˙’
d¯i theo ca
.
nh kh´ac chu
.
a
d¯u
.
o
.
.
c su
.
˙’
du
.
ng. Nˆe
´
u ta khˆong thˆe
˙’
d¯i d¯u
.

.
t dˆay chuyˆe
`
n Euler v`a d¯i
.
nh l´y d¯´ung. Trong tru
.
`o
.
ng ho
.
.
p ngu
.
o
.
.
c
la
.
i, d¯ˆo
`
thi
.
con G

d¯u
.
o
.

˜
n. K´y hiˆe
.
u G

1
, G

2
, . . . , G

p
l`a c´ac th`anh phˆa
`
n liˆen thˆong cu
˙’
a G

ch´u
.
a ´ıt nhˆa
´
t mˆo
.
t ca
.
nh.
Khi d¯´o c´ac d¯ˆo
`
thi

.
G

1
, G

2
, . . . , G

p
c´ac
d¯ı
˙’
nh theo th´u
.
tu
.
.
i
1
, i
2
, . . . , i
p
. Khi d¯´o h`anh tr`ınh: xuˆa
´
t ph´at t`u
.
a d¯i trˆen µ d¯ˆe
´

2
vˆe
`
i
2
,
v`a vˆan vˆan, l`a mˆo
.
t dˆay chuyˆe
`
n Euler xuˆa
´
t ph´at t`u
.
a v`a kˆe
´
t th ´uc ta
.
i b. D
-
i
.
nh l´y d¯u
.
o
.
.
c ch ´u
.
ng

n Euler
C´ach ch´u
.
ng minh D
-
i
.
nh l´y Euler 5.1.3 cho ta mˆo
.
t thuˆa
.
t to´an xˆay du
.
.
ng dˆay chuyˆe
`
n Euler
trong mˆo
.
t d¯ˆo
`
thi
.
Euler.
1. Xˆay du
.
.
ng mˆo
.
t dˆay chuyˆe

ng th`ı d`u
.
ng v`a ta c´o µ l`a dˆay chuyˆe
`
n Euler.
Ngu
.
o
.
.
c la
.
i sang Bu
.
´o
.
c 3.
3. K´y hiˆe
.
u G
1
l`a d¯ˆo
`
thi
.
con cu
˙’
a G gˆo
`
m c´ac ca

n gia
˙’
n µ
1
trong d¯ˆo
`
thi
.
G
1
xuˆa
´
t ph´at
t`u
.
d¯ı
˙’
nh c.
4. Mo
.
˙’
rˆo
.
ng dˆay chuyˆe
`
n µ bˇa
`
ng c´ach gˇa
´
n thˆem chu tr`ınh µ

.
p la
.
i bu
.
´o
.
c 2.
V´ı du
.
5.1.4 D
-
ˆo
`
thi
.
trong H`ınh 5.2 c´o mˆo
.
t chu tr`ınh Euler
(v
1
, e
1
, v
2
, e
2
, v
3
, e

e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
e
10
e
11
e
12
e
13
e
14
e
15
e
16

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

v
5
, e
16
, v
3
, e
17
, v
7
, e
10
, v
6
, e
9
, v
8
, e
8
, v
7
, e
5
, v
1
, e
7
, v
8

nh cu
˙’
a G ch´u
.
a trong n´o. Chˇa
˙’
ng ha
.
n, ta c´o thˆe
˙’
su
.
˙’
du
.
ng mˆo
.
t cˆa
´
u tr´uc danh s´ach
liˆen kˆe
´
t
typedef struct PathNode *PathPtr;
struct PathNode
{
byte Vertex;
PathPtr Next;
};
d¯ˆe

hiˆe
.
u cu
˙’
a d¯ı
˙’
nh kˆe
`
V ertex trˆen dˆay chuyˆe
`
n.
Dˆe
˜
thˆa
´
y rˇa
`
ng, danh s´ach n`ay c´o sˆo
´
n´ut bˇa
`
ng (m + 1).
T`u
.
d¯ˆay vˆe
`
sau ta s˜e gia
˙’
thiˆe
´

˙’
nh v
i
v`a tru
.
`o
.
ng d¯ˆo
.
d`ai Length o
.
˙’
n´ut th´u
.
j (tu
.
o
.
ng ´u
.
ng d¯ı
˙’
nh v
j
) l`a sˆo
´
ca
.
nh liˆen thuˆo
.

t d¯o
.
n vi
.
o
.
˙’
n´ut th´u
.
j trong danh s´ach V out[i] d¯ˆe
˙’
d¯´anh dˆa
´
u ca
.
nh d¯˜a d¯u
.
o
.
.
c su
.
˙’
du
.
ng.
V`ı mˆo
˜
i ca
.

to´an l`a O(m).
5.2 B`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa
X´et d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng liˆen thˆong G := (V, E) c´o tro
.
ng sˆo
´
(t´u
.
c l`a mˆo
˜
i ca
.
nh e ∈ E ta g´an mˆo
.

c d¯i
.
nh hu
.
´o
.
ng) ph´at biˆe
˙’
u rˇa
`
ng t`ım mˆo
.
t
dˆay chuyˆe
`
n gi˜u
.
a hai d¯ı
˙’
nh cho tru
.
´o
.
c a, b ∈ V su
.
˙’
du
.
ng mˆo
˜

, ngu
.
`o
.
i giao s˜u
.
a, ngu
.
`o
.
i ch`ao h`ang, v.v)
c´o thˆe
˙’
ph´at biˆe
˙’
u o
.
˙’
da
.
ng n`ay. Trong tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi

d¯u
.
a vˆe
`
b`ai to´an luˆo
`
ng v´o
.
i chi ph´ı nho
˙’
nhˆa
´
t (b`ai tˆa
.
p).
T`u
.
d¯ˆay vˆe
`
sau ch´ung ta chı
˙’
x´et d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng. Khˆong mˆa

.
.
c la
.
i, ta chı
˙’
cˆa
`
n thˆem mˆo
.
t ca
.
nh (a, b) v´o
.
i d¯ˆo
.
d`ai bˇa
`
ng khˆong. V´o
.
i mˆo
˜
i chu tr`ınh
c´o d¯ˆo
.
d`ai nho
˙’
nhˆa
´
t trˆen d¯ˆo

.
i mˆo
.
t chu tr`ınh Euler d¯i qua mˆo
˜
i ca
.
nh d¯´ung mˆo
.
t lˆa
`
n
v`a v`ı vˆa
.
y l`a mˆo
.
t nghiˆe
.
m tˆo
´
i u
.
u cu
˙’
a b`ai to´an.
N´oi chung, G khˆong pha
˙’
i l`a d¯ˆo
`
thi

. Dˆe
˜
thˆa
´
y rˇa
`
ng sˆo
´
phˆa
`
n tu
.
˙’
cu
˙’
a tˆa
.
p V
1
l`a mˆo
.
t sˆo
´
chˇa
˜
n. Khi
d¯´o b`ai to´an ngu
.
`o
.

˙’
u ho´a tˆo
˙’
ng c´ac tro
.
ng lu
.
o
.
.
ng cu
˙’
a c´ac ca
.
nh d¯u
.
o
.
.
c thˆem v`ao.
Ch´ung ta khˆong thˆem mˆo
.
t ca
.
nh e

= (v
i
, v
j

) := w(e). Ca
.
nh e

go
.
i l`a ba
˙’
n sao cu
˙’
a e.
X´et mˆo
.
t l`o
.
i gia
˙’
i tˆo
´
i u
.
u cu
˙’
a b`ai to´an v`a d¯ˇa
.
t E

l`a tˆa
.
p c´ac ca

`
5.2.1 Gia
˙’
su
.
˙’
v
i
l`a mˆo
.
t d¯ı
˙’
nh bˆa
.
c le
˙’
trong G. Khi d¯´o tˆa
.
p E

ch´u
.
a mˆo
.
t dˆay chuyˆe
`
n
so
.
cˆa

nh v
k
∈ V
1
ta c´o d
G
(v
k
) ≡ 1 (mod 2) v`a d
G

(v
k
) ≡ 0 (mod 2); ngo`ai
ra, theo c´ach xˆay du
.
.
ng d
G

(v
k
) ≥ d
G
(v
k
). Do d¯´o tˆo
`
n ta
.

1
liˆen thuˆo
.
c. Nˆe
´
u d
G
(v
i
1
) ≡ 1 (mod 2) th`ı bˆo
˙’
d¯ˆe
`
d¯u
.
o
.
.
c ch´u
.
ng minh v´o
.
i v
j
= v
i
1
. Ngu
.

nh e
2
∈ E

, e
2
= e
1
, liˆen thuˆo
.
c d¯ı
˙’
nh v
i
1
. K´y hiˆe
.
u v
i
2
l`a d¯ı
˙’
nh kh´ac v
i
1
m`a ca
.
nh
e
2

.
.
c la
.
i,
tˆo
`
n ta
.
i ca
.
nh e
3
∈ E

, e
3
= e
2
, liˆen thuˆo
.
c d¯ı
˙’
nh v
i
2
, v`a vˆan vˆan.
Do d¯´o ta xˆay du
.
.

p
, v
i
p
).
Nˆe
´
u d
G
(v
i
p
) ≡ 1 (mod 2) th`ı bˆo
˙’
d¯ˆe
`
d¯u
.
o
.
.
c ch´u
.
ng minh v´o
.
i v
j
= v
i
p

i
p+1
. Trong tru
.
`o
.
ng ho
.
.
p n`ay, tˆo
`
n ta
.
i chı
˙’
sˆo
´
q, 1 ≤ q ≤ p, sao cho v
i
q
≡ v
i
p+1
v`a ta c´o mˆo
.
t chu tr`ınh xuˆa
´
t hiˆe
.
n. Loa

`
thi
.
Euler v`a
ho
.
n n˜u
.
a
d
G

(v
k
) ≥ d
G
(v
k
),
v´o
.
i mo
.
i d¯ı
˙’
nh v
k
∈ V.
Lˇa
.

.
Do sˆo
´
c´ac ca
.
nh trong E

l`a h˜u
.
u ha
.
n, nˆen sau mˆo
.
t sˆo
´
h˜u
.
u ha
.
n bu
.
´o
.
c ta d¯u
.
o
.
.
c mˆo
.

Bˆo
˙’
d¯ˆe
`
5.2.2 Gia
˙’
su
.
˙’
v
i
v`a v
j
l`a hai d¯ı
˙’
nh thoa
˙’
m˜an c´ac d¯iˆe
`
u kiˆe
.
n cu
˙’
a Bˆo
˙’
d¯ˆe
`
5.2.1 v`a k´y
hiˆe
.

1
, e

2
, . . . , e

p
l`a c´ac ba
˙’
n sao cu
˙’
a c´ac ca
.
nh
e
1
, e
2
, . . . , e
p
trong G v`a x´et dˆay chuyˆe
`
n µ := {e
1
, e
2
, . . . , e
p
} trong G. Khi d¯´o µ l`a dˆay
chuyˆe

`
n ta
.
i mˆo
.
t dˆay chuyˆe
`
n ¯µ = {¯e
1
, ¯e
2
, . . . , ¯e
q
} nˆo
´
i d¯ı
˙’
nh v
i
v´o
.
i d¯ı
˙’
nh v
j
trong
G c´o d¯ˆo
.
d`ai nho
˙’


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
˙’

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
´

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

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
˙’

.
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
˜

.
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
.

.
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
.

.
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

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
˙’

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
.

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

.
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
´

.
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

a chu tr`ınh cˆa
`
n t`ım s˜e l´o
.
n ho
.
n 31.
133

7

3

3

2

3
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
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
.

˙’
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

.
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

´
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
´

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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¯ı
˙’

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

´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
.

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 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
.
.

.
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

.
´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¯ı
˙’

.
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
.

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

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
˙’

.
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

˙’
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

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
˙’

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

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

`
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

`
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
˙’

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

.
`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

`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
.

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

.
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
`

`
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
˙’

.
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
˙’

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 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

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
.

˙’
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

.
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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.

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

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

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

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

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

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

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

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

•
•
•
•
•
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
.

.
.
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

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
`

.
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
˙’

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

.
.
.
.
.

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

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

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

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

.
.
.

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

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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
.

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

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

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
.

.
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

) 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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.
.
.
.

•
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

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

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
´

.
`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
˜

.
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
.

`
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
`

.
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

˙’
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

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

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

`
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

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

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

(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
˙’

.
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
`

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

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
´

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

.
.
.

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
•
•
•
•
H`ınh 5.10: V´o
.
i d¯ˆo
`

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

.
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
´

.
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

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

.
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`ı

˙’
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

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¯ı

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
.
.

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

.
˙’
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
.

`
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

.
`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

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
.

.
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

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

.
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 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
.

˙’
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

⊂ 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¯ı

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 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

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

= ∅.

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¯ı
˙’

(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
´

. 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

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
δ

) + δ(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
.

.
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

.
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
.

.
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