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