http://www.ebook.edu.vn
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
˜i ca
.nh d¯´ung mˆo
.t lˆa
`n v`a qua mˆo
˜i d¯ı
˙’nh d¯´ung
mˆo
.t lˆa
`n tu
.o.ng ´u
.ng d¯´ong vai tr`o quan tro
.ng.
Hai b`ai to´an n`ay c´o liˆen quan d¯ˆe
´n nh˜u
.ng ´u
.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
`ng m´ay t´ınh,
lˆa
.p li
.ch, vˆan vˆan.
Mˇa
.c d`u hai b`ai to´an n`ay d¯u
.o
.
.c ph´at biˆe
˙’u rˆa
´t giˆo
´ng nhau, nhu
.ng m´u
.c d¯ˆo
.kh´o trong
viˆe
.c gia
˙’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
.i d¯u
.a thu
.Trung Hoa c´o thˆe
˙’ d¯u
.a vˆe
`t`ım cˇa
.p gh´ep ho`an
ha
˙’o c´o tro
.ng lu
.o.
.ng nho
˙’ nhˆa
´t [30] (c˜ung xem Phˆa
`n 7.5). C´ac thuˆa
.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.
.c d¯ˆe
`cˆa
.p o.
˙’ d¯ˆay. Ba
.n d¯o
.c quan tˆam c´o thˆe
˙’ xem, chˇa
˙’ng ha
.n [30]. Ch´ung ta
chı
˙’ tr`ınh b`ay trong Phˆa
`n 5.3 nh˜u
.ng kˆe
´t qua
˙’ 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
˙’ d¯ˆe
`xuˆa
´t nh˜u
.ng phu
.o.ng ph´ap heuristic.
5.1 B`ai to´an Euler
D
-i
.nh ngh˜ıa 5.1.1 Gia
˙’ su
.
˙’ G= (V, E) l`a d¯ˆo
`thi
.vˆo hu
.´o
.ng (d¯o
.n hoˇa
.c d¯a d¯ˆo
`thi
.). Dˆay chuyˆe
`n
127
http://www.ebook.edu.vn
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 ca
.nh d¯´ung mˆo
.t lˆa
`n. Chu tr`ınh
Euler l`a dˆay chuyˆe
`n Euler m`a d¯ı
˙’nh d¯ˆa
`u tr`ung v´o
.i d¯ı
˙’nh cuˆo
´i.
V´ı du
.5.1.2 (B`ai to´an Euler) C´ach d¯ˆay khoa
˙’ng ba trˇam nˇam, nhiˆe
`u ngu
.`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
´c cˆa
`u
bˇa
´c qua sˆong nhu
.trˆen H`ınh 5.1(a); c´o thˆe
˙’ d¯i da
.o qua khˇa
´p c´ac cˆa
`u nhu
.ng mˆo
˜i cˆa
`u chı
˙’ d¯i
mˆo
.t lˆa
`n thˆoi khˆong? Nˆe
´u ta coi mˆo
˜i khu vu
.
.ca, 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
.t ca
.nh nˆo
´i hai d¯ı
˙’nh, th`ı ba
˙’n d¯ˆo
`th`anh phˆo
´K¨onigsberg l`a mˆo
.t
d¯ˆo
`thi
.(H`ınh 5.1(b)). Thˇa
´c mˇa
´c cu
˙’a ngu
.`o
.i dˆan th`anh phˆ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
`u tiˆen d¯˜a ch´u
.ng minh b`ai to´an khˆong
c´o l`o
.i gia
˙’i (nˇam 1736, xem [22], [23]), v`a v`ı vˆa
.y b`ai to´an thu
.`o
.ng d¯u
.o.
.c go
.i l`a b`ai to´an Euler
vˆe
`c´ac cˆa
`u o.
˙’ K¨onigsberg.
a
bc
d
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
..
.
.
.
.
.
.
.
..
..
..
..
..
...
...............
..
..
..
.
..
..
..
..
..
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
..
..
.
..
..
..
...
...............
..
..
..
..
..
..
..
..
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.................................................................................
.................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........................................................................................................
...........................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.....
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.......
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(a)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
bc
d(b)
H`ınh 5.1: (a) Ba
˙’n d¯ˆo
`cu
˙’a th`anh phˆo
´K¨onigsberg. (b) D
-ˆo
`thi
.tu
.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
´u sˆo
´c´ac d¯ı
˙’nh bˆa
.c le
˙’ bˇa
`ng 0 hoˇa
.c 2.
Ch´u
.ng minh. Tru
.´o
.c hˆe
´t ch´u ´y rˇa
`ng d¯ˆo
`thi
.khˆong liˆen thˆong khˆong thˆe
˙’ ch´u
.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
´i c´o bˆa
.c le
˙’. Nˆe
´u ngo`ai ra, hai d¯ı
˙’nh n`ay tr`ung nhau (chu tr`ınh Euler) th`ı khˆong
c´o d¯ı
˙’nh bˆa
.c le
˙’.
128
http://www.ebook.edu.vn
Kˆe
´tiˆe
´p ta ch´u
.ng minh d¯iˆe
`u kiˆe
.n d¯u
˙’ bˇa
`ng quy na
.p theo sˆo
´ca
.nh mcu
˙’aG. Hiˆe
˙’n nhiˆen
d¯i
.nh l´y d¯´ung nˆe
´um= 1.Gia
˙’ su
.
˙’ d¯i
.nh l´y d¯´ung cho mo
.i d¯ˆo
`thi
.liˆen thˆong mca
.nh. Nˆe
´uGc´o
hai d¯ı
˙’nh bˆa
.c le
˙’, gia
˙’ su
.
˙’ c´ac d¯ı
˙’nh n`ay l`a av`a b(nˆe
´u tˆa
´t ca
˙’ c´ac d¯ı
˙’nh cu
˙’aGc´o bˆa
.c chˇa
˜n, cho
.n
d¯ı
˙’nh abˆa
´t k`y v`a lˆa
´yb=a).K´y hiˆe
.uµl`a dˆay chuyˆe
`n m`a ta d¯i trˆen d¯ˆo
`thi
.Gxuˆa
´t ph´at t`u
.a
theo hu
.´o
.ng tu`y ´y, d¯i qua mˆo
˜i ca
.nh d¯´ung mˆo
.t lˆa
`n. Nˆe
´u ta
.i th`o
.i d¯iˆe
˙’m n`ao d¯´o ta o
.
˙’ d¯ı
˙’nh x6=b
ngh˜ıa l`a ta d¯˜a su
.
˙’ du
.ng mˆo
.t sˆo
´le
˙’ ca
.nh liˆen thuˆo
.c v´o
.ixnˆ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
.o.
.c n˜u
.a, ngh˜ıa l`a d¯ang o
.
˙’ d¯ı
˙’nh b. Nˆe
´u tˆa
´t ca
˙’ c´ac ca
.nh
d¯˜a d¯u
.o.
.c su
.
˙’ du
.ng, µl`a mˆo
.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.
.c x´ac d¯i
.nh bo.
˙’ i c´ac ca
.nh chu
.a d¯u
.o.
.c su
.
˙’ du
.ng chı
˙’ c´o nh˜u
.ng d¯ı
˙’nh bˆa
.c
chˇa
˜n. K´y hiˆe
.uG′
1, G′
2, . . . , G′
pl`a c´ac th`anh phˆa
`n liˆen thˆong cu
˙’aG′ch´u
.a ´ıt nhˆa
´t mˆo
.t ca
.nh.
Khi d¯´o c´ac d¯ˆo
`thi
.G′
ic´o sˆo
´ca
.nh ´ıt ho.nmv`a do d¯´o theo gia
˙’ thiˆe
´t quy na
.p, ch´ung ch´u
.a mˆo
.t
chu tr`ınh Euler µi.V`ı Gliˆen thˆong, dˆay chuyˆe
`nµc´o chung v´o
.i c´ac d¯ˆo
`thi
.G′
1, G′
2, . . . , G′
pc´ac
d¯ı
˙’nh theo th´u
.tu
.
.i1, i2, . . . , ip.Khi d¯´o h`anh tr`ınh: xuˆa
´t ph´at t`u
.ad¯i trˆen µd¯ˆe
´n d¯ı
˙’nh i1,d¯i
do
.c theo chu tr`ınh µ1t`u
.i1vˆe
`i1,d¯i trˆen µd¯ˆe
´n d¯ı
˙’nh i2d¯i do
.c theo chu tr`ınh µ2t`u
.i2vˆe
`i2,
v`a vˆan vˆan, l`a mˆo
.t dˆay chuyˆe
`n Euler xuˆa
´t ph´at t`u
.av`a kˆe
´t th´uc ta
.ib. D
-i
.nh l´y d¯u
.o.
.c ch´u
.ng
minh. ⊳
D
-ˆo
`thi
.thoa
˙’ c´ac d¯iˆe
`u kiˆe
.n cu
˙’a D
-i
.nh l´y Euler go
.i l`a d¯ˆo
`thi
.Euler.
5.1.1 Thuˆa
.t to´an t`ım dˆay chuyˆe
`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
`n d¯o.n gia
˙’nµxuˆa
´t ph´at t`u
.s.
2. Nˆe
´u tˆa
´t ca
˙’ c´ac ca
.nh cu
˙’aGd¯˜a d¯u
.o.
.c su
.
˙’ du
.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
.uG1l`a d¯ˆo
`thi
.con cu
˙’aGgˆo
`m c´ac ca
.nh chu
.a d¯u
.o.
.c su
.
˙’ du
.ng. Cho
.n d¯ı
˙’nh ccu
˙’aG1
nˇa
`m trˆen dˆay chuyˆe
`nµ. Xˆay du
.
.ng chu tr`ınh d¯o
.n gia
˙’nµ1trong d¯ˆo
`thi
.G1xuˆ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 µ1ta
.i d¯ı
˙’nh c(t´u
.c l`a d˜ay c´ac
ca
.nh cu
˙’aµ1d¯u
.o.
.c ch`en v`ao d˜ay c´ac ca
.nh cu
˙’aµ).
5. Thay Gbo.
˙’ iG1v`a lˇa
.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
(v1, e1, v2, e2, v3, e3, v2, e4, v3, e15, v4, e14, v5, e13, v4, e12, v6, e11,
129
http://www.ebook.edu.vn
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10 e11 e12
e13
e14
e15
e16
e17
v1
v2
v6
v3
v7
v8
v5v4
.......................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
......................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
......................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
..
.......
..
..
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
...
.........
..
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
..
....
....
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.......
..
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
H`ınh 5.2: Mˆo
.t v´ı du
.vˆe
`d¯ˆo
`thi
.Euler.
v5, e16, v3, e17, v7, e10, v6, e9, v8, e8, v7, e5, v1, e7, v8, e6, v1).
Mˆo
.t dˆay chuyˆe
`n hay chu tr`ınh Euler c´o thˆe
˙’ d¯u
.o
.
.c x´ac d¯i
.nh bo.
˙’ i mˆo
.t danh s´ach c´o th´u
.
tu
.
.c´ac d¯ı
˙’nh cu
˙’aGch´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
˙’ d¯´anh dˆa
´u c´ac d¯ı
˙’nh liˆen tiˆe
´p trˆen dˆay chuyˆe
`n, trong d¯´o V ertex l`a sˆo
´hiˆe
.u d¯ı
˙’nh trˆen dˆay
chuyˆe
`n; v`a con tro
˙’ Next chı
˙’ n´ut kˆe
´tiˆe
´p ch´u
.a sˆo
´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
´tGd¯u
.o.
.c cho bo.
˙’ i ma
˙’ng c´ac danh s´ach kˆe
`Vout[] (c´o
tro
.ng sˆo
´), trong d¯´o v´o
.i mˆo
˜i d¯ı
˙’nh vi∈V, V out[i] l`a danh s´ach c´ac d¯ı
˙’nh liˆen thuˆo
.c d¯ı
˙’nh vi
v`a tru
.`o
.ng d¯ˆo
.d`ai Length o.
˙’ n´ut th´u
.j(tu
.o.ng ´u
.ng d¯ı
˙’nh vj) l`a sˆo
´ca
.nh liˆen thuˆo
.c v´o
.i d¯ı
˙’nh
vi.Trong qu´a tr`ınh thu
.
.c hiˆe
.n thuˆa
.t to´an, mˆo
˜i khi d¯i qua ca
.nh (vi, vj) n`ao d¯´o, ta gia
˙’m d¯ˆo
.
130
http://www.ebook.edu.vn
d`ai Length mˆo
.t d¯o.n vi
.o.
˙’ n´ut th´u
.jtrong danh s´ach Vout[i] d¯ˆe
˙’ d¯´anh dˆa
´u ca
.nh d¯˜a d¯u
.o.
.c su
.
˙’
du
.ng.
V`ı mˆo
˜i ca
.nh cu
˙’a d¯ˆo
`thi
.d¯u
.o.
.c kiˆe
˙’m tra nhiˆe
`u nhˆa
´t hai lˆa
`n nˆen d¯ˆo
.ph´u
.c ta
.p cu
˙’a thuˆa
.t
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∈Eta g´an mˆo
.t
sˆo
´w(e) go
.i l`a tro
.ng lu
.o
.
.ng cu
˙’a ca
.nh e).
B`ai to´an ngu
.`o
.i d¯u
.a thu
.Trung Hoa (khˆong d¯u
.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
.ca, b ∈Vsu
.
˙’ du
.ng mˆo
˜i ca
.nh cu
˙’aG´ıt nhˆa
´t mˆo
.t lˆa
`n v`a c´o
d¯ˆo
.d`ai nho
˙’ nhˆa
´t (xem [44]).
Nhiˆe
`u b`ai to´an vˆe
`h`anh tr`ınh (ngu
.`o
.i d¯u
.a thu
., 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
.c´o hu
.´o
.ng, trong d¯´o mˆo
˜i cung cu
˙’aG
cˆa
`n d¯u
.o.
.c su
.
˙’ du
.ng ´ıt nhˆa
´t mˆo
.t lˆa
`n, b`ai to´an c´o thˆe
˙’ 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
´t t´ınh tˆo
˙’ng qu´at c´o thˆe
˙’
gia
˙’ thiˆe
´t d¯ı
˙’nh xuˆa
´t ph´at av`a d¯ı
˙’nh kˆe
´t th´uc btrˆen dˆay chuyˆe
`n l`a tr`ung nhau. Trong tru
.`o
.ng
ho.
.p ngu
.o.
.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
`thi
.m´o
.i n`ay, tˆo
`n ta
.i mˆo
.t dˆay chuyˆe
`n trˆen Gc´o c`ung d¯ˆo
.d`ai v`a
do d¯´o l`a nho
˙’ nhˆa
´t.
Nˆe
´uGl`a d¯ˆo
`thi
.Euler th`ı tˆo
`n ta
.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, Gkhˆong pha
˙’i l`a d¯ˆo
`thi
.Euler, nˆen tˆo
`n ta
.i mˆo
.t sˆo
´c´ac d¯ı
˙’nh bˆa
.c le
˙’. K´y hiˆe
.u
V1l`a tˆa
.p c´ac d¯ı
˙’nh cu
˙’aGc´o bˆa
.c le
˙’. Dˆe
˜thˆa
´y rˇa
`ng sˆo
´phˆa
`n tu
.
˙’ cu
˙’a tˆa
.pV1l`a mˆo
.t sˆo
´chˇa
˜n. Khi
d¯´o b`ai to´an ngu
.`o
.i d¯u
.a thu
.Trung Hoa d¯u
.a vˆe
`viˆe
.c thˆem mˆo
.t sˆo
´ca
.nh v`ao Gd¯ˆe
˙’ tro.
˙’ th`anh
d¯ˆo
`thi
.Euler v`a c`ung l´uc, cu
.
.c tiˆe
˙’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′= (vi, vj) tr`u
.khi d¯˜a tˆo
`n ta
.i mˆo
.t ca
.nh e= (vi, vj)
trong Gv`a g´an tro
.ng lu
.o.
.ng cu
˙’a ca
.nh e′l`a w(e′) := w(e).Ca
.nh e′go
.i l`a ba
˙’n sao cu
˙’ae.
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
.tE′l`a tˆa
.p c´ac ca
.nh d¯u
.o.
.c thˆem v`ao G. K´y
hiˆe
.uG′= (V, E +E′) l`a d¯ˆo
`thi
.Euler nhˆa
.n d¯u
.o.
.c.
131