Chu
.
o
.
ng 6
D
-
ˆo
`
thi
.
phˇa
˙’
ng
Ch´ung ta d¯˜a nghiˆen c´u
.
u c´ac t´ınh chˆa
´
t cu
˙’
a c´ac d¯ˆo
`
thi
.
con, chˇa
˙’
ng ha
.
n, c´ac dˆay chuyˆe
`

.
ng n`ay bˇa
´
t d¯ˆa
`
u v´o
.
i hai v´ı du
.
vˆe
`
d¯ˆo
`
thi
.
Kuratowski d¯´ong vai tr`o trung tˆam trong
viˆe
.
c kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
. Kˆe
´

.
i d¯ˆo
`
thi
.
phˇa
˙’
ng l`a 4−sˇa
´
c” (ph´at biˆe
˙’
u nˇam
1850 v`a d¯u
.
o
.
.
c ch´u
.
ng minh nˇam 1976). Ch´ung ta c˜ung t`ım hiˆe
˙’
u tiˆeu chuˆa
˙’
n cˆa
`
n v`a d¯u
˙’
d¯ˆe
˙’
d¯ˆo

nh ngh˜ıa v`a c´ac v´ı du
.
Nhˇa
´
c la
.
i rˇa
`
ng d¯ˆo
`
thi
.
G d¯u
.
o
.
.
c go
.
i l`a phˇa
˙’
ng nˆe
´
u tˆo
`
n ta
.
i mˆo
.
t ph´ep biˆe

nh cu
˙’
a ch´ung. C´ac
d¯ˆo
`
thi
.
m`a c´o thˆe
˙’
biˆe
´
n d¯ˆo
˙’
i cho tr`ung nhau bˇa
`
ng ph´ep biˆe
´
n da
.
ng co d˜an liˆen tu
.
c trˆen mˇa
.
t
phˇa
˙’
ng th`ı khˆong coi l`a nh˜u
.
ng d¯ˆo
`

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

t thu
.
.
v`a ba nh`a m´ay v`a tˆa
´
t ca
˙’
c´ac d¯u
.
`o
.
ng vˆa
.
n chuyˆe
˙’
n sao cho khˆong
c´o hai d¯u
.
`o
.
ng n`ao cˇa
´
t nhau o
.
˙’
mˆo
.
t d¯iˆe
˙’
m kh´ac c´ac d¯ˆa

149


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
d
•
c
•
e
•
b
•
a
•
H`ınh 6.1: V´ı du
.
vˆe
`
d¯ˆo
`
thi
.
phˇa
˙’
ng.
(xem H`ınh 6.2); mˆo

a d¯ˆo
`
thi
.
Kuratowski K
3,3
. Bˇa
`
ng thu
.
.
c nghiˆe
.
m c´o thˆe
˙’
chı
˙’
ra rˇa
`
ng d¯ˆo
`
thi
.
n`ay khˆong phˇa
˙’
ng.
.
.
.
.

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
a
•
b
•
c
•
d
•
e
•
f
•
H`ınh 6.2: D
-
ˆo
`
thi
.
Kuratowski K
3,3
.
V´ı du
.
6.1.2 C˜ung bˇa

ng cu
˙’
a c´ac d¯ˆo
`
thi
.
K
3,3
v`a K
5
s˜e d¯u
.
o
.
.
c gia
˙’
i th´ıch trong nh˜u
.
ng phˆa
`
n
sau. Ch´u ´y rˇa
`
ng c´ac d¯ˆo
`
thi
.
K
5

th`ı s˜e nhˆa
.
n d¯u
.
o
.
.
c mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng.
150

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

thi
.
khˆong phˇa
˙’
ng c´o sˆo
´
d¯ı
˙’
nh ´ıt nhˆa
´
t; K
3,3
l`a d¯ˆo
`
thi
.
khˆong phˇa
˙’
ng c´o sˆo
´
ca
.
nh ´ıt
nhˆa
´
t.
6.2 C´ac biˆe
˙’
u diˆe
˜

n d¯ˆo
`
thi
.
phˇa
˙’
ng c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n trˆen mˆo
.
t mˇa
.
t phˇa
˙’
ng sao cho
c´ac ca
.
nh l`a c´ac d¯oa
.
n thˇa
˙’
ng v`a ch´ung chı
˙’
cˇa
´
t nhau ta

.
. Ba
.
n d¯o
.
c quan tˆam c´o thˆe
˙’
xem [24]. Chˇa
˙’
ng ha
.
n, d¯ˆo
`
thi
.
trong H`ınh 6.1 c´o thˆe
˙’
v˜e la
.
i chı
˙’
su
.
˙’
du
.
ng c´ac d¯oa
.
n thˇa
˙’

˙’
ng. 
Diˆe
.
n
K´y hiˆe
.
u R(G) l`a d¯ˆo
`
thi
.
phˇa
˙’
ng G d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t phˇa
˙’
ng. C´ac v`ung liˆen thˆong (theo
tˆo pˆo cu
˙’
a mˇa

o
.
.
c gi´o
.
i ha
.
n bo
.
˙’
i c´ac ca
.
nh go
.
i l`a biˆen; hai diˆe
.
n go
.
i l`a kˆe
`
nhau nˆe
´
u c´ac d¯u
.
`o
.
ng biˆen
cu
˙’
a ch´ung c´o ´ıt nhˆa

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

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

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

.
.
.
.

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

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

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

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

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

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

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

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

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

.
.

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

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

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

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

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

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

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

.

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

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


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

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

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

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

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

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

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

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

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

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

nh r`o
.
i nhau, c´ac ca
.
nh
treo (ca
.
nh c´o mˆo
.
t d¯ı
˙’
nh bˆa
.
c mˆo
.
t), hoˇa
.
c c´ac ca
.
nh nˆo
´
i hai chu tr`ınh. Diˆe
.
n ph´ıa ngo`ai, go
.
i
l`a diˆe
.
n vˆo ha
.

d¯i
.
a l´y l`a d¯ˆo
`
thi
.
tˆo pˆo phˇa
˙’
ng khˆong c´o cˆa
`
u; d¯ˆo
`
thi
.
d¯´o c´o t´ınh chˆa
´
t d¯ˇa
.
c
biˆe
.
t l`a: bˆa
.
c cu
˙’
a mˆo
˜
i d¯ı
˙’
nh ≥ 3. Mˆo

˙’
nh chung; a l`a diˆe
.
n
vˆo ha
.
n.

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

a c´ac diˆe
.
n h˜u
.
u ha
.
n v`a diˆe
.
n vˆo ha
.
n, ch´ung ta thu
.
`o
.
ng biˆe
˙’
u diˆe
˜
n c´ac
d¯ˆo
`
thi
.
phˇa
˙’
ng trˆen mˇa
.
t cˆa
`
u S

.
i mˇa
.
t phˇa
˙’
ng, v`a N l`a d¯iˆe
˙’
m thuˆo
.
c mˇa
.
t cˆa
`
u sao cho NS vuˆong
g´oc v´o
.
i mˇa
.
t phˇa
˙’
ng. V´o
.
i mˆo
˜
i d¯iˆe
˙’
m P ∈ S
2
, P = N, d¯u
.

.
t-mˆo
.
t t`u
.
mˇa
.
t cˆa
`
u (bo
˙’
d¯i d¯iˆe
˙’
m N) lˆen mˇa
.
t
phˇa
˙’
ng.
Theo c´ach xˆay du
.
.
ng n`ay, hiˆe
˙’
n nhiˆen rˇa
`
ng d¯ˆo
`
thi
.

Do d¯´o, theo D
-
i
.
nh l´y 6.2.1 ta c´o
D
-
i
.
nh l´y 6.2.3 Mˆo
.
t d¯ˆo
`
thi
.
c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t cˆa
`
u sao cho c´ac ca
.
nh khˆong tu
.
.

ng d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t cˆa
`
u s˜e phˆan chia mˇa
.
t cˆa
`
u th`anh nhiˆe
`
u v`ung
kh´ac nhau. Mˆo
˜
i v`ung trˆen mˇa
.
t cˆa
`
u l`a miˆe
`
n gi´o
.

´
c N. Hiˆe
˙’
n nhiˆen rˇa
`
ng, bˇa
`
ng ph´ep quay th´ıch
ho
.
.
p qua
˙’
cˆa
`
u ch´ung ta c´o thˆe
˙’
´anh xa
.
mˆo
.
t v`ung bˆa
´
t k `y th`anh diˆe
.
n vˆo ha
.
n trˆen mˇa
.
t phˇa

n trˆen mˆo
.
t mˇa
.
t phˇa
˙’
ng sao cho diˆe
.
n bˆa
´
t k`y
cho tru
.
´o
.
c l`a diˆe
.
n vˆo ha
.
n.
Mˆo
´
i liˆen quan c´ac v`ung trˆen mˇa
.
t cˆa
`
u cho ph´ep ch´ung ta thˆa
´
y rˇa
`

c´ac
v`ung trong mˆo
.
t biˆe
˙’
u diˆe
˜
n cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng trˆen mˇa
.
t phˇa
˙’
ng, ch ´ung ta x´et ca
˙’
diˆe
.
n vˆo ha
.
n.
Ngo`ai ra, do khˆong c´o su
.
.
kh´ac nhau cˆo

xem l`a mˇa
.
t cˆa
`
u bo
˙’
d¯i mˆo
.
t d¯iˆe
˙’
m), thuˆa
.
t ng˜u
.
“biˆe
˙’
u
diˆe
˜
n phˇa
˙’
ng” cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
thu

ng.
Biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t phˇa
˙’
ng v`a t´ınh liˆen thˆong
Trong mˆo
.
t d¯ˆo
`
thi
.
khˆong liˆen thˆong, viˆe
.
c biˆe
˙’
u diˆe
˜
n mˆo
˜
i th`anh phˆa
`
n trˆen mˇa
.
t phˇa
˙’

liˆen thˆong cu
˙’
a n´o l`a phˇa
˙’
ng. Tu
.
o
.
ng tu
.
.
, trong mˆo
.
t d¯ˆo
`
thi
.
t´ach d¯u
.
o
.
.
c (t´u
.
c 1−liˆen thˆong) viˆe
.
c
153

biˆe

.
o
.
.
c
kha
˙’
o s´at d¯ˆo
.
c lˆa
.
p. Do d¯´o mˆo
.
t d¯ˆo
`
thi
.
t´ach d¯u
.
o
.
.
c l`a phˇa
˙’
ng nˆe
´
u v`a chı
˙’
nˆe
´

.
khˆong t´ach d¯u
.
o
.
.
c.
Mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng khˆong t´ach d¯u
.
o
.
.
c c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n duy nhˆa
´
t lˆen mˆo
.

Hai biˆe
˙’
u diˆe
˜
n cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng l`a giˆo
´
ng nhau nˆe
´
u ch´ung c´o thˆe
˙’
l`am tr`ung nhau bˇa
`
ng
ph´ep quay mˇa
.
t cˆa
`
u n`ay th`anh mˇa
.
t cˆa

u l`a tr`ung nhau th`ı ta
n´oi d¯ˆo
`
thi
.
c´o duy nhˆa
´
t mˆo
.
t ph´ep biˆe
˙’
u diˆe
˜
n. D
-
i
.
nh l´y du
.
´o
.
i d¯ˆay, cho ch´ung ta ch´ınh x´ac cˆau
tra
˙’
l`o
.
i khi n`ao th`ı mˆo
.
t d¯ˆo
`

t cˆa
`
u cu
˙’
a mˆo
˜
i d¯ˆo
`
thi
.
phˇa
˙’
ng 3−liˆen thˆong
l`a duy nhˆa
´
t.
Ch´u
.
ng minh. Xem [54]. 
D
-
i
.
nh l´y n`ay d¯´ong mˆo
.
t vai tr`o quan tro
.
ng trong viˆe
.
c x´ac d¯i

u th`ı ph´ep
biˆe
˙’
u diˆe
˜
n n`ay l`a duy nhˆa
´
t.
6.3 C´ac t´ınh chˆa
´
t cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’
ng
Phˆa
`
n n`ay liˆe
.
t kˆe nghiˆen c´u
.
u mˆo
.
t sˆo
´
t´ınh chˆa

tˆo pˆo phˇa
˙’
ng, c´ac chu tuyˆe
´
n cu
˙’
a diˆe
.
n h˜u
.
u ha
.
n ta
.
o
th`anh mˆo
.
t hˆe
.
co
.
so
.
˙’
c´ac chu tr`ınh d¯ˆo
.
c lˆa
.
p.
Ch´u

u ha
.
n. Gia
˙’
su
.
˙’
d¯i
.
nh l´y d¯´ung
cho mo
.
i d¯ˆo
`
thi
.
phˇa
˙’
ng c´o sˆo
´
diˆe
.
n h˜u
.
u ha
.
n l`a (f − 1); ta ch´u
.
ng minh d¯i
.

˙’
c´ac chu tuyˆe
´
n d¯ˆe
`
u l`a c´ac chu tr`ınh khˆong giao nhau
(theo ngh˜ıa l`a c´o ca
.
nh chung) v`ı v´o
.
i tru
.
`o
.
ng ho
.
.
p d¯´o th`ı d¯i
.
nh l ´y l`a hiˆe
˙’
n nhiˆen. Khi d¯´o ta c´o
thˆe
˙’
bo
˙’
b´o
.
t mˆo
.

thiˆe
´
t quy na
.
p lˆa
.
p th`anh mˆo
.
t co
.
so
.
˙’
gˆo
`
m c´ac chu tr`ınh d¯ˆo
.
c lˆa
.
p. Khi
tra
˙’
la
.
i ca
.
nh e, ta c´o mˆo
.
t diˆe
.

´
c´ac chu tr`ınh ˆa
´
y). Do bˆo
˙’
sung mˆo
.
t ca
.
nh khˆong thˆe
˙’
l`am tˇang chu sˆo
´
lˆen qu´a mˆo
.
t d¯o
.
n vi
.
, nˆen
sˆo
´
diˆe
.
n h˜u
.
u ha
.
n cu
˙’

˙’
G l`a d¯ˆo
`
thi
.
tˆo pˆo phˇa
˙’
ng liˆen thˆong n d¯ı
˙’
nh, m ca
.
nh v`a
f diˆe
.
n. Khi d¯´o
f = m − n + 2.
Ch´u
.
ng minh. Thˆa
.
t vˆa
.
y, sˆo
´
c´ac diˆe
.
n h˜u
.
u ha
.

.
, v`ı viˆe
.
c thˆem mˆo
.
t khuyˆen hoˇa
.
c
thˆem mˆo
.
t ca
.
nh song song chı
˙’
d¯o
.
n gia
˙’
n l`a tˇang sˆo
´
diˆe
.
n v`a sˆo
´
ca
.
nh cu
˙’
a d¯ˆo
`

t ca
.
nh v`a mˆo
.
t d¯ı
˙’
nh th`ı hiˆe
.
u sˆo
´
(m − n) khˆong d¯ˆo
˙’
i.
V`ı mˆo
˜
i d¯o
.
n d¯ˆo
`
thi
.
phˇa
˙’
ng c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n trˆen mˇa

o
.
.
c v˜e trˆen mˇa
.
t phˇa
˙’
ng sao cho
c´ac diˆe
.
n l`a c´ac d¯a gi´ac. K´y hiˆe
.
u f l`a sˆo
´
diˆe
.
n v`a k
p
l`a sˆo
´
c´ac diˆe
.
n c´o p ca
.
nh. V`ı mˆo
˜
i ca
.
nh
thuˆo

.
t kh´ac
k
3
+ k
4
+ · · · + k
r
= f.
Tˆo
˙’
ng tˆa
´
t ca
˙’
c´ac g´oc ta
.
i mˆo
˜
i d¯ı
˙’
nh trong d¯a gi´ac tu
.
o
.
ng ´u
.
ng d¯ˆo
`
thi

+ · · · + (r − 2)πk
r
+ 4π
= (2m − 2f)π + 4π.
T`u
.
c´ac d¯ˇa
˙’
ng th´u
.
c trˆen, ta suy ra
2(m − f)π + 4π = 2nπ.
Vˆa
.
y f = m − n + 2. 
155

V´ı du
.
6.3.3 [Euler] Ta x´et trong khˆong gian ba chiˆe
`
u mˆo
.
t d¯a diˆe
.
n lˆo
`
i c´o n d¯ı
˙’
nh, m ca

´
n h`anh ph´ep chiˆe
´
u nˆo
˙’
i v´o
.
i tˆam o
.
˙’
gi˜u
.
a
mˆo
.
t trong c´ac diˆe
.
n ta c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n d¯a diˆe
.
n d¯´o trˆen mˇa
.
t phˇa
˙’
ng. V`ı d¯ˆo

n d¯ˆo
`
thi
.
phˇa
˙’
ng, liˆen thˆong c´o f diˆe
.
n, n d¯ı
˙’
nh, m ca
.
nh (m ≥ 2),
c´ac bˆa
´
t d¯ˇa
˙’
ng th´u
.
c sau luˆon nghiˆe
.
m d¯´ung

2m ≥ 3f,
3n − 6 ≥ m.
Ch´u
.
ng minh. Mˆo
˜
i diˆe

.
u ´y rˇa
`
ng bˆa
´
t d¯ˇa
˙’
ng th´u
.
c th´u
.
hai chı
˙’
l`a mˆo
.
t d¯iˆe
`
u kiˆe
.
n cˆa
`
n m`a khˆong d¯u
˙’
vˆe
`
t´ınh phˇa
˙’
ng cu
˙’
a mˆo

u ngu
.
o
.
.
c la
.
i l`a khˆong d¯´ung. Chˇa
˙’
ng ha
.
n d¯ˆo
`
thi
.
Kuratowski K
3,3
tho
˙’
a
3n − 6 = 3.6 − 6 = 12 ≥ m = 9.
Nhu
.
ng
V´ı du
.
6.3.5 D
-
ˆo
`

a n´o c´o sˆo
´
ca
.
nh nho
˙’
ho
.
n 5. Thˆa
.
t vˆa
.
y, nˆe
´
u d¯ˆo
`
thi
.
l`a
phˇa
˙’
ng th`ı 2m ≥ 4f.
Theo cˆong th´u
.
c Euler
2m ≥ 4(m − n + 2).
Vˆa
.
y
2.9 ≥ 4(9 − 6 + 2).

.
t vˆa
.
y, nˆe
´
u ngu
.
o
.
.
c la
.
i th`ı
K
5
s˜e c´o
f = m − n + 2 = 10 − 5 + 2 = 7
156

diˆe
.
n. Chu tuyˆe
´
n cu
˙’
a mˆo
˜
i diˆe
.
n d¯ˆe

t ≤ 2m v`a mˇa
.
t kh´ac la
.
i ≥ 3f. T`u
.
d¯´o
20 = 2m ≥ 3f = 21.
Vˆo l ´y, vˆa
.
y K
5
l`a khˆong phˇa
˙’
ng.
Hˆe
.
qua
˙’
6.3.7 Mˆo
˜
i ba
˙’
n d¯ˆo
`
d¯i
.
a l´y c´o ´ıt nhˆa
´
t mˆo

`
d¯i
.
a l´y, mˆo
˜
i d¯ı
˙’
nh l`a d¯ˆa
`
u m´ut cu
˙’
a ´ıt nhˆa
´
t 3 ca
.
nh; nˆe
´
u
lˆa
.
p d¯o
.
n d¯ˆo
`
thi
.
liˆen thuˆo
.
c d¯ı
˙’

´
n gˆo
`
m ´ıt nhˆa
´
t 6 ca
.
nh v`a nˆe
´
u lˆa
.
p d¯o
.
n
d¯ˆo
`
thi
.
liˆen thuˆo
.
c diˆe
.
n-ca
.
nh, th`ı sˆo
´
ca
.
nh cu
˙’

.
ng th`anh phˆa
`
n), v`a do d¯´o c´o thˆe
˙’
viˆe
´
t
2 = n − m + f ≤ 2m/3 − m + m/3 = 0.
D
-
iˆe
`
u d¯´o khˆong thˆe
˙’
xa
˙’
y ra. 
Hˆe
.
qua
˙’
6.3.8 Gia
˙’
su
.
˙’
G l`a d¯o
.
n d¯ˆo

.
.
c bao ´ıt nhˆa
´
t bo
.
˙’
i ba ca
.
nh kh´ac nhau;
nˆe
´
u lˆa
.
p d¯ˆo
`
thi
.
H liˆen thuˆo
.
c diˆe
.
n-ca
.
nh (t´u
.
c l`a d¯ˆo
`
thi
.

.
nh nˆo
´
i d¯iˆe
˙’
m x ∈ X v´o
.
i
y ∈ Y nˆe
´
u diˆe
.
n x liˆen thuˆo
.
c ca
.
nh y) th`ı sˆo
´
ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
H, mˆo
.
t mˇa
.

.
.
c n ≤ 2m/6, ngh˜ıa l`a (theo cˆong th´u
.
c Euler)
2 = n − m + f ≤ m/3 − m + 2m/3 = 0.
Vˆo l ´y! 
6.4 Ph´at hiˆe
.
n t´ınh phˇa
˙’
ng
Viˆe
.
c x´ac d¯i
.
nh d¯ˆo
`
thi
.
G l`a phˇa
˙’
ng hay khˆong l`a mˆo
.
t b`ai to´an quan tro
.
ng, chˇa
˙’
ng ha
.

t
157

d¯ˆo
`
thi
.
phˇa
˙’
ng; v`a tra
˙’
l`o
.
i cˆau ho
˙’
i n`ay bˇa
`
ng c´ach cˆo
´
gˇa
´
ng thu
.
˙’
v˜e n´o lˆen mˆo
.
t mˇa
.
t phˇa
˙’

˙’
ng th`ı biˆe
˙’
u diˆe
˜
n n´o nhu
.
thˆe
´
n`ao c´o thˆe
˙’
xem [34], [18].
C˜ung c´o mˆo
.
t thuˆa
.
t to´an [33] th`o
.
i gian O(n log n) d¯ˆe
˙’
kiˆe
˙’
m tra t´ınh d¯ˇa
˙’
ng cˆa
´
u cu
˙’
a hai
d¯ˆo

u qua
˙’
sau cho ph´ep ph´at hiˆe
.
n t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
.
Ph´ep r´ut go
.
n co
.
so
.
˙’
1. Do d¯ˆo
`
thi
.
l`a phˇa
˙’
ng nˆe
´
u v`a chı
˙’

.
p
l`a phˇa
˙’
ng nˆe
´
u v`a chı
˙’
nˆe
´
u c´ac khˆo
´
i cu
˙’
a n´o l`a phˇa
˙’
ng. V`ı vˆa
.
y d¯ˆo
´
i v´o
.
i mˆo
.
t d¯ˆo
`
thi
.
G cho
tru

G. Rˆo
`
i th`ı
ch´ung ta chı
˙’
cˆa
`
n kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a mˆo
˜
i G
i
.
2. Do viˆe
.
c thˆem hay x´oa c´ac khuyˆen khˆong l`am mˆa
´
t t´ınh phˇa
˙’
ng, ta xo´a c´ac khuyˆen.
3. Tˆa
´
t ca
˙’
c´ac ca

4. Loa
.
i bo
˙’
tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh bˆa
.
c hai v`a coi hai ca
.
nh nˆo
´
i v´o
.
i d¯ı
˙’
nh d¯´o l`a mˆo
.
t khˆong a
˙’
nh
hu
.
o
.
˙’

n khi ta d¯u
.
o
.
.
c mˆo
.
t d¯ˆo
`
thi
.
d¯o
.
n gia
˙’
n nhˆa
´
t cho ph´ep x´ac
d¯i
.
nh dˆe
˜
d`ang t´ınh phˇa
˙’
ng cu
˙’
a n´o.
D
-
ˆo

`
thi
.
H
i
c´o c´ac d¯ˇa
.
c tru
.
ng:
D
-
i
.
nh l´y 6.4.1 D
-
ˆo
`
thi
.
H
i
c´o mˆo
.
t trong ba da
.
ng
1. Mˆo
.
t ca

.
khˆong t´ach d¯u
.
o
.
.
c c´o sˆo
´
d¯ı
˙’
nh n ≥ 5 v`a sˆo
´
ca
.
nh m ≥ 7.
158

Ch´u
.
ng minh. D
-
i
.
nh l´y c´o thˆe
˙’
d¯u
.
o
.
.

n hoˇa
.
c bˇa
`
ng s´au. 
´
Ap du
.
ng d¯i
.
nh l ´y, ch´ung ta thˆa
´
y rˇa
`
ng tˆa
´
t ca
˙’
c´ac d¯ˆo
`
thi
.
H
i
ro
.
i v`ao loa
.
i 1 hoˇa
.

c v´o
.
i ´ıt nhˆa
´
t nˇam d¯ı
˙’
nh, v`a mˆo
˜
i d¯ı
˙’
nh c´o bˆa
.
c l´o
.
n ho
.
n hay bˇa
`
ng ba. Kˆe
´
d¯ˆe
´
n, ch´ung
ta cˆa
`
n kiˆe
˙’
m tra bˆa
´
t d¯ˇa

ng d¯i
.
nh l´y Kuratowski
du
.
´o
.
i d¯ˆay. Tru
.
´o
.
c hˆe
´
t ta cˆa
`
n d¯i
.
nh ngh˜ıa sau.
D
-
i
.
nh ngh˜ıa 6.4.2 (a) Trong mˆo
.
t d¯ˆo
`
thi
.
, hai ca
.

c go
.
i l`a d¯ˆo
`
ng phˆoi nˆe
´
u d¯ˆo
`
thi
.
n`ay c´o thˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c t`u
.
d¯ˆo
`
thi
.
kia bˇa
`
ng
c´ach ta
.

2
trong H`ınh 6.6 l`a d¯ˆo
`
ng phˆoi, do c´o thˆe
˙’
d¯u
.
a vˆe
`
c`ung d¯ˆo
`
thi
.
G

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

•
•
•
•
••
G
2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

•
•
•
•
•
G

H`ınh 6.6:
Hiˆe
˙’
n nhiˆen rˇa
`
ng d¯ˆo
`
thi
.
l`a phˇa
˙’
ng nˆe
´
u v`a chı
˙’
nˆe
´
u mo
.
i d¯ˆo
`
thi
.

u v`a chı
˙’
nˆe
´
u G
1
v`a G
2
d¯ˆo
`
ng
phˆoi l`a quan hˆe
.
tu
.
o
.
ng d¯u
.
o
.
ng.
D
-
i
.
nh l´y 6.4.4 [Kuratowski, 1930] D
-
ˆo
`


Ch´u
.
ng minh. D
-
iˆe
`
u kiˆe
.
n cˆa
`
n. R˜o r`ang, v`ı G khˆong thˆe
˙’
biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t phˇa
˙’
ng sao cho c´ac
ca
.
nh cu
˙’
a ch´ung khˆong cˇa
´
t nhau ngoa
.

`
u kiˆe
.
n d¯u
˙’
. Xem [4]. 
V´ı du
.
6.4.5 Bˇa
`
ng c´ach ´ap du
.
ng D
-
i
.
nh l´y Kuratowski ta c´o d¯ˆo
`
thi
.
trong H`ınh 6.7 khˆong
phˇa
˙’
ng. Thˆa
.
t vˆa
.
y, tru
.
´o

.
.
c l`a K
3,3
.
Suy ra G ch´u
.
a mˆo
.
t d¯ˆo
`
thi
.
con d¯ˆo
`
ng phˆoi v´o
.
i K
3,3
v`a do d¯´o khˆong phˇa
˙’
ng.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

´
i v´o
.
i c´ac d¯ˆo
`
thi
.
l´o
.
n
(chˇa
˙’
ng ha
.
n, d¯o
.
n d¯ˆo
`
thi
.
khˆong t´ach d¯u
.
o
.
.
c c´o 25 d¯ı
˙’
nh v`a bˆa
.
c cu

.
o
.
.
c x´et
trong phˆa
`
n kˆe
´
tiˆe
´
p.
D
-
i
.
nh l´y 6.4.6 Mo
.
i d¯ˆo
`
thi
.
phˇa
˙’
ng d¯ˆe
`
u 5−sˇa
´
c.
Ch´u

.
phˇa
˙’
ng c´o (n − 1) d¯ı
˙’
nh. Ta s˜e ch´u
.
ng minh d¯i
.
nh l ´y c˜ung d¯´ung cho
nh˜u
.
ng d¯ˆo
`
thi
.
phˇa
˙’
ng c´o n d¯ı
˙’
nh.
160

Thˆa
.
t vˆa
.
y, theo Hˆe
.
qua

.
nh liˆen thuˆo
.
c n´o l`a 5−sˇa
´
c; ta tˆo c´ac d¯ı
˙’
nh cu
˙’
a n´o bˇa
`
ng
nˇam m`au α, β, γ, δ, . Ta c´o thˆe
˙’
tˆo m`au d¯ı
˙’
nh v, tr`u
.
khi n´o kˆe
`
v´o
.
i nˇam d¯ı
˙’
nh mang nˇam m`au
kh´ac nhau.
Trong tru
.
`o
.

.
ng. K´y hiˆe
.
u G
α,β
l`a d¯ˆo
`
thi
.
con sinh bo
.
˙’
i tˆa
.
p ho
.
.
p
c´ac d¯ı
˙’
nh c´o m`au α hay β, v.v. C´o hai tru
.
`o
.
ng ho
.
.
p xa
˙’
y ra:

i. C´ach tˆo m`au m´o
.
i cho G l`a chˆa
´
p
nhˆa
.
n d¯u
.
o
.
.
c, v`a d¯ı
˙’
nh v bˆay gi`o
.
d¯u
.
o
.
.
c bao quanh bo
.
˙’
i c´ac d¯ı
˙’
nh c´o m`au γ, β, γ, δ,  nˆen c´o
thˆe
˙’
tˆo n´o bˇa

G
β,δ
(v`ı nˆe
´
u ngu
.
o
.
.
c la
.
i, G ch ´u
.
a d¯ˆo
`
thi
.
K
5
). Khi ho´an vi
.
c´ac
m`au β v`a δ trong th`anh phˆa
`
n cu
˙’
a d¯ˆo
`
thi
.

˙’
l`am tˆo
´
t ho
.
n:
D
-
i
.
nh l´y 6.4.7 [Gia
˙’
thuyˆe
´
t bˆo
´
n m`au] Sˇa
´
c sˆo
´
cu
˙’
a mo
.
i d¯ˆo
`
thi
.
phˇa
˙’

`o
.
i ho
.
c tr`o cu
˙’
a ˆong v`ao nˇam 1850. Sau d¯´o, Morgan d¯˜a d¯ˆe
`
cˆa
.
p b`ai to´an n`ay v´o
.
i
Hamilton trong mˆo
.
t b´u
.
c thu
.
viˆe
´
t ng`ay 23 th´ang 10 nˇam 1852. Kˆe
´
t qua
˙’
l`a rˆa
´
t nhiˆe
`
u “ch´u

.
`o
.
i
M˜y l`a Appel v`a Haken (xem [1]), su
.
˙’
du
.
ng h`ang ng`an gi`o
.
trˆen m´ay t´ınh d¯iˆe
.
n tu
.
˙’
, d¯˜a ch´u
.
ng
minh t´ınh d¯´ung d¯ˇa
´
n cu
˙’
a gia
˙’
thuyˆe
´
t bˆo
´
n m`au. 

a Kuratowski v`a Whitney cho ph´ep kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
. Tuy
nhiˆen c´ac d¯ˇa
.
c tru
.
ng n`ay khˆong ph`u ho
.
.
p khi thu
.
.
c hiˆe
.
n trˆen m´ay t´ınh do kh´o thˆe
˙’
hiˆe
.
n bˇa
`
ng

.
`o
.
i ta biˆe
´
t rˇa
`
ng [52], nˆe
´
u su
.
˙’
du
.
ng tiˆeu chuˆa
˙’
n cu
˙’
a Kuratowski d¯ˆe
˙’
kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.

(xem [52] d¯ˆe
˙’
c´o tˆo
˙’
ng quan vˆe
`
c´ac kˆe
´
t qua
˙’
n`ay). Hˆa
`
u hˆe
´
t c´ac phu
.
o
.
ng ph´ap n`ay ´ap du
.
ng c´ach “xˆay du
.
.
ng ba
˙’
n d¯ˆo
`
”: D
-
ˆa

.
t chu tr`ınh). Sau d¯´o thˆem c´ac ca
.
nh v`ao d¯ˆo
`
thi
.
g sao cho n´o khˆong
cˇa
´
t c´ac ca
.
nh kh´ac (ngoa
.
i tr`u
.
ta
.
i c´ac d¯ı
˙’
nh chung). Nˆe
´
u ch´ung ta th`anh cˆong khi biˆe
˙’
u diˆe
˜
n
la
.
i th`ı d¯ˆo

.
˙’
chˆo
˜
trong nh˜u
.
ng giai d¯oa
.
n tru
.
´o
.
c d¯´o,
viˆe
.
c thˆem c´ac ca
.
nh v`ao g t`u
.
nh˜u
.
ng kha
˙’
nˇang c´o thˆe
˙’
khˆong d¯ˆe
˙’
´y d¯ˆe
´
n c´ac giai d¯oa

bu
.
´o
.
c sau, mˇa
.
c d`u
d¯ˆo
`
thi
.
d¯˜a cho l`a phˇa
˙’
ng. Chˇa
˙’
ng ha
.
n, trong H`ınh 6.8(a), gia
˙’
su
.
˙’
ta bˇa
´
t d¯ˆa
`
u v´o
.
i d¯ˆo
`

1
, v
6
)
sao cho d¯ˆo
`
thi
.
thu d¯u
.
o
.
.
c vˆa
˜
n phˇa
˙’
ng. Hiˆe
˙’
n nhiˆen l`a ca
.
nh (v
2
, v
5
) khˆong thˆe
˙’
d¯ˇa
.
t d¯u

H`ınh 6.8(b).

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

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

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

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

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

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

.

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

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

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

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

.
.
.
.
.
.
.

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

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

.

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

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

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

.
.
.
.
.

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

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

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

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

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

.
.

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

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

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

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

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

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

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

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

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

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

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

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

• •
•
•
•
•
v
1
v
2
v
3
v
4
v
5
v
6
(a)

.
.
.
.
.
.
.
.

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

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


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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
D
-
ˆay ch´ınh l`a mˆo
.
t tro
.
˙’
nga
.
i cu
˙’
a phu
.
o
.
ng ph´ap xˆay du
.
.
ng ba
˙’
n d¯ˆo
`
; v`a ta cˆa
`
n mˆo
.
t sˆo
´

.
n d¯ˆe
˙’
d¯o
.
n gia
˙’
n
ho´a tiˆe
´
n tr`ınh kiˆe
˙’
m tra. C´ac bu
.
´o
.
c thu go
.
n khˆong a
˙’
nh hu
.
o
.
˙’
ng d¯ˆe
´
n t´ınh phˇa
˙’
ng (hoˇa

phˆa
`
n liˆen thˆong.
2. Xo´a c´ac khuyˆen, v`a thay tˆa
´
t ca
˙’
c´ac ca
.
nh song song bo
.
˙’
i d¯´ung mˆo
.
t ca
.
nh.
3. Xo´a c´ac d¯ı
˙’
nh bˆa
.
c hai v`a ho
.
.
p nhˆa
´
t hai ca
.
nh liˆen thuˆo
.

thi
.
th`anh c´ac th`anh phˆa
`
n
khˆong t´ach d¯u
.
o
.
.
c .
5. V´o
.
i mˆo
˜
i th`anh phˆa
`
n khˆong t´ach d¯u
.
o
.
.
c, thu
.
.
c hiˆe
.
n ph´ep thu go
.
n su

.
nh, kiˆe
˙’
m tra c´ac bˆa
´
t d¯ˇa
˙’
ng th´u
.
c
n ≥ 5, m ≥ 9, m ≤ 3n − 6.
Nˆe
´
u c´ac r`ang buˆo
.
c n`ay khˆong thoa
˙’
m˜an, thuˆa
.
t to´an kˆe
´
t th´uc; ngu
.
o
.
.
c la
.
i kiˆe
˙’

Mˆo
˜
i d¯ˆo
`
thi
.
khˆong t´ach d¯u
.
o
.
.
c c´o thˆe
˙’
t´ach th`anh c´ac th`anh phˆa
`
n 3−liˆen thˆong. Su
.
˙’
du
.
ng
kˆe
´
t qua
˙’
cu
˙’
a Tutte [54]: D
-
ˆo

bˇa
`
ng thuˆa
.
t to´an cu
˙’
a Hopcroft
v`a Tarjan sau d¯ˆay.
Thuˆa
.
t to´an Hopcroft-Tarjan
Thuˆa
.
t to´an kiˆe
˙’
m tra t´ınh phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
rˆa
´
t ph´u
.
c ta
.
p. Do d¯´o ch´ung ta s˜e chı

`
thi
.
khˆong t´ach d¯u
.
o
.
.
c G c´o n d¯ı
˙’
nh v`a m ca
.
nh.
Phˆan r˜a chu tr`ınh-dˆay chuyˆe
`
n:
1. T`ım chu tr`ınh µ trong G. G´an g = µ. G´an nh˜an c´ac d¯ı
˙’
nh v`a c´ac ca
.
nh cu
˙’
a g l`a v
1
, v
2
, . . . ,
v`a e
1
, e

t d¯ˆa
`
u v`a kˆe
´
t
th´uc ta
.
i c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c g´an nh˜an nhu
.
ng dˆay chuyˆe
`
n n`ay chı
˙’
gˆo
`
m nh˜u
.
ng ca
.
nh chu
.
a
d¯u

c 4.
163

3. D
-
ˇa
.
t g = g ∪µ
i
; v`a i = i +1. G´an nh˜an c´ac ca
.
nh v`a c´ac d¯ı
˙’
nh chu
.
a d¯u
.
o
.
.
c g´an nh˜an trong
g v`a chuyˆe
˙’
n sang Bu
.
´o
.
c 2.
4. Xuˆa
´

.
.
c G
th`anh mˆo
.
t chu tr`ınh v`a e = m − n dˆay chuyˆe
`
n. V`ı chu tr`ınh c´o thˆe
˙’
xem l`a kˆe
´
t nˆo
´
i cu
˙’
a hai
dˆay chuyˆe
`
n khˆong c´o chung ca
.
nh, nˆen G d¯u
.
o
.
.
c phˆan r˜a th`anh m − n + 2 dˆay chuyˆe
`
n. Cˆa
`
n

t chu tr`ınh v`a bˆo
´
n
(10 − 6 = 4) dˆay chuyˆe
`
n:
{v
1
, v
2
, v
3
, v
4
, v
5
, v
1
}, {(v
1
, v
4
)}, {(v
2
, v
5
)}, {(v
4
, v
6

)}, {(v
1
, v
6
)}, {(v
1
, v
4
)}, {(v
2
, v
5
)}.
Trong qu´a tr`ınh phˆan r˜a chu tr`ınh-dˆay chuyˆe
`
n, ch´ung ta c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n chu tr`ınh µ
trˆen mˇa
.
t phˇa
˙’
ng, v`a tiˆe
´
p tu
.

n ta
.
i th`anh hai diˆe
.
n m´o
.
i hoˇa
.
c
s˜e khiˆe
´
n cho g ∪ µ
i
khˆong phˇa
˙’
ng khi thˆem n´o v`ao g. Do ch´ung ta thˆem tu`y ´y, nˆen c´o thˆe
˙’
xa
˙’
y ra t`ınh tra
.
ng nhu
.
trong H`ınh 6.8. D
-
ˆe
˙’
gia
˙’
i quyˆe

˙’
la
.
i t`ım kiˆe
´
m cho
.
n lu
.
.
a c´ach biˆe
˙’
u diˆe
˜
n kh´ac (t´u
.
c l`a d`ung phu
.
o
.
ng ph´ap lˆa
`
n ngu
.
o
.
.
c) thay
cho qu´a tr`ınh tru
.

`
n d¯u
.
o
.
.
c d¯ˇa
.
t v`ao, hoˇa
.
c l`a biˆe
´
t chˇa
´
c rˇa
`
ng khˆong c´o
tro
.
˙’
nga
.
i v´o
.
i diˆe
.
n m`a d¯ˇa
.
t dˆay chuyˆe
`

ng minh rˇa
`
ng thuˆa
.
t to´an cu
˙’
a ho
.
l`a hiˆe
.
u qua
˙’
ho
.
n.
´
Y ch´ınh
cu
˙’
a thuˆa
.
t to´an n`ay l`a gia
˙’
i quyˆe
´
t su
.
.
nhˆa
.

˙’
nh cu
˙’
a mˆo
.
t danh
s´ach ch´u
.
a c´ac dˆay chuyˆe
`
n cˆa
`
n xu
.
˙’
l´y) m`a ch´ung ta cˆa
`
n gia
˙’
i quyˆe
´
t su
.
.
nhˆa
.
p nhˇa
`
ng cu
˙’

o
.
ng ph´ap xu
.
˙’
l´y tu
.
o
.
ng ´u
.
ng s˜e d¯u
.
o
.
.
c tr`ınh b`ay du
.
´o
.
i d¯ˆay. C´ac t`ınh
huˆo
´
ng n`ay d¯u
.
o
.
.
c gia
˙’

i
v`a gia
˙’
i quyˆe
´
t su
.
.
nhˆa
.
p nhˇa
`
ng cu
˙’
a dˆay chuyˆe
`
n
kˆe
´
tiˆe
´
p trong stack.
(b) Ngu
.
o
.
.
c la
.
i (stack bˇa

.
c la
.
i gia
˙’
su
.
˙’
P
j
l`a dˆay chuyˆe
`
n (kh´ac P
i
) ch´u
.
a hai d¯ı
˙’
nh a v`a b (xem H`ınh 6.9(a)).
Gi˜u
.
la
.
i P
i
trong danh s´ach. Xˆay du
.
.
ng dˆay chuyˆe
`

.
c P
k
(xem H`ınh 6.9(b)) th`ı d¯ˇa
.
t dˆay chuyˆe
`
n P
k
trˆen P
i
v`ao stack v`a
gia
˙’
i quyˆe
´
t t´ınh nhˆa
.
p nhˇa
`
ng cu
˙’
a dˆay chuyˆe
`
n P
k
.
(b) Ngu
.
o

i su
.
.
nhˆa
.
p nhˇa
`
ng cu
˙’
a dˆay chuyˆe
`
n kˆe
´
tiˆe
´
p trong stack.
(c) Ngu
.
o
.
.
c la
.
i nˆe
´
u y nˇa
`
m gi ˜u
.
a a v`a b (H`ınh 6.9(d)) th`ı lu

a a v`a b.
(d) Ngu
.
o
.
.
c la
.
i (H`ınh 6.9(e)), lu
.
u tr˜u
.
P
k
. Tiˆe
´
p tu
.
c gia
˙’
i t´ınh nhˆa
.
p nhˇa
`
ng cu
˙’
a dˆay chuyˆe
`
n
P

`
n µ
j
. Su
.
.
nhˆa
.
p nhˇa
`
ng n`ay cˆa
`
n d¯u
.
o
.
.
c xu
.
˙’
l´y. D
-
ˆe
˙’
gia
˙’
i
quyˆe
´
t, ta xˆay du

.
o
.
.
c g´an nh˜an v`a kˆe
´
t th´uc ngay khi n´o gˇa
.
p mˆo
.
t d¯ı
˙’
nh
d¯u
.
o
.
.
c g´an nh˜an, chˇa
˙’
ng ha
.
n y).
Nˆe
´
u ca
˙’
hai d¯ı
˙’
nh x v`a y cu

.
c ph´ıa
“du
.
´o
.
i” dˆay chuyˆe
`
n µ
i
. V`ı vˆa
.
y ch´ung ta khˆong nh˜u
.
ng cˆa
`
n xu
.
˙’
l´y cho µ
i
m`a tru
.
´o
.
c hˆe
´
t c`on
pha
˙’

.
t ngˇan xˆe
´
p, v`a ta bˇa
´
t d¯ˆa
`
u xu
.
˙’
l´y tu
.
o
.
ng tu
.
.
µ
i
d¯ˆo
´
i v´o
.
i µ
k
.
Kha
˙’
nˇang kh´ac l`a d¯ı
˙’

n µ
i
khˆong
thˆe
˙’
xoay sang ph´ıa bˆen kia, v`a do d¯´o khˆong c´o su
.
.
nhˆa
.
p nhˇa
`
ng vˆe
`
diˆe
.
n m`a dˆay chuyˆe
`
n n`ay
phˆan chia.
Nhu
.
trong H`ınh 6.9(d), nˆe
´
u d¯ı
˙’
nh cuˆo
´
i cu
˙’

˜
n c´o su
.
.
nhˆa
.
p nhˇa
`
ng d¯ˆo
´
i v´o
.
i dˆay chuyˆe
`
n µ
i
. Tuy nhiˆen khi d¯´o dˆay chuyˆe
`
n µ
k
phˆan d¯ˆoi diˆe
.
n x´ac d¯i
.
nh
bo
.
˙’
i chu tuyˆe
´

i quyˆe
´
t su
.
.
nhˆa
.
p nhˇa
`
ng v´o
.
i µ
i
.
165


µ
j
.
.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
• • • • •
a
b
µ
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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


µ
j
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
µ
k
•
•
• • • • •

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
µ
i

.
.
.

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

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

µ
j
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

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

.

µ
k
•
• •
•• • •
•
•
• • • •
•• •
a
b
x
y
(c)
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

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

.
.
.
µ
i

µ
j
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

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

••
• •
•
•
a
b
x
y
(b)

µ
j
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

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

i
• ••
• • • • •
•
a
b
(a)
H`ınh 6.9: Phˆan t´ıch c´ac kha
˙’
nˇang xa
˙’
y ra cu
˙’
a dˆay chuyˆe
`
n µ
i
.
Cuˆo
´
i c`ung, trong tru
.
`o
.
ng ho
.
.
p dˆay chuyˆe
`
n µ

˙’
xoay.
Nhu
.
ng kh´ac v´o
.
i tru
.
`o
.
ng ho
.
.
p cu
˙’
a H`ınh 6.9(b), khˆong c´o su
.
.
nhˆa
.
p nhˇa
`
ng cu
˙’
a dˆay chuyˆe
`
n µ
k
tu
.

˙’
a
dˆay chuyˆe
`
n µ
i
v`a dˆay chuyˆe
`
n m´o
.
i n`ay c´o thˆe
˙’
xuˆa
´
t ph´at t`u
.
mˆo
.
t d¯ı
˙’
nh bˆa
´
t k`y trˆen dˆay chuyˆe
`
n
y, a, x, b; ngo`ai ra ta c ˜ung mo
.
˙’
rˆo
.

.
c:
1. T`ım c´ac th`anh phˆa
`
n khˆong t´ach d¯u
.
o
.
.
c;
2. Phˆan hoa
.
ch c´ac th`anh phˆa
`
n khˆong t´ach d¯u
.
o
.
.
cth`anh c´ac dˆay chuyˆe
`
n;
166

3. X´ac d¯i
.
nh vi
.
tr´ı d¯ˆe
˙’

i quyˆe
´
t c´ac Bu
.
´o
.
c 1 v`a 2. C´ac dˆay chuyˆe
`
n
d¯u
.
o
.
.
c ta
.
o bo
.
˙’
i hai bu
.
´o
.
c trˆen c´o nh˜u
.
ng t´ınh chˆa
´
t th´ıch ho
.
.

.
i gian xˆay du
.
.
ng mˆo
.
t biˆe
˙’
u
diˆe
˜
n phˇa
˙’
ng l`a O(n log n). V`ı vˆa
.
y th`o
.
i gian thu
.
.
c hiˆe
.
n cu
˙’
a thuˆa
.
t to´an l`a O(n log n) (do cˆong
th´u
.
c Euler, sˆo

n tˆo
´
t ho
.
n v´o
.
i th`o
.
i gian thu
.
.
c hiˆe
.
n l`a O(n) (xem
[34]).
6.5 D
-
ˆo
´
i ngˆa
˜
u h`ınh ho
.
c
X´et d¯ˆo
`
thi
.
phˇa
˙’

t mˆo
.
t d¯ı
˙’
nh s
∗
cu
˙’
a G
∗
; v´o
.
i mˆo
˜
i ca
.
nh e
cu
˙’
a G thiˆe
´
t lˆa
.
p tu
.
o
.
ng ´u
.
ng mˆo

a ca
.
nh e trong R(G). D
-
ˆo
`
thi
.
G
∗
go
.
i l`a d¯ˆo
´
i ngˆa
˜
u (tˆo pˆo) cu
˙’
a
G (hay c`on go
.
i l`a d¯ˆo
´
i ngˆa
˜
u h`ınh ho
.
c cu
˙’
a G).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

´
p cu
˙’
a R(G) chia mˇa
.
t phˇa
˙’
ng th`anh hai v`ung liˆen thˆong kh´ac trˆo
´
ng
v`a r`o
.
i nhau. Bo
˙’
d¯i tˆa
´
t ca
˙’
c´ac ca
.
nh d¯ˆo
´
i ngˆa
˜
u tu
.
o
.
ng ´u
.

ng mˆo
.
t d¯ˆo
´
i chu tr`ınh so
.
cˆa
´
p cu
˙’
a G
∗
, v`a ngu
.
o
.
.
c la
.
i. T´ınh chˆa
´
t n`ay rˆa
´
t
h˜u
.
u ´ıch v`ı ta c´o thˆe
˙’
t`ım mˆo
.

a c´ac ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
G v`a d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa
˜
u
G
∗
−mˆo
.
t ca
.
nh cu
˙’
a G
∗
giao v´o
.
i mˆo

.
nh treo trong G tu
.
o
.
ng ´u
.
ng khuyˆen trong G
∗
.
3. Nˆe
´
u G c´o d¯iˆe
˙’
m kh´o
.
p th`ı G
∗
c˜ung c´o d¯iˆe
˙’
m kh´o
.
p.
4. C´ac ca
.
nh trong chuˆo
˜
i cu
˙’
a G tu

.
nh ta
.
o th`anh biˆen trong diˆe
.
n F cu
˙’
a G, bˇa
`
ng bˆa
.
c cu
˙’
a d¯ı
˙’
nh tu
.
o
.
ng ´u
.
ng trong
G
∗
v`a ngu
.
o
.
.
c la

∗
)
∗
= G.
9. Nˆe
´
u k´y hiˆe
.
u n, m v`a f l`a sˆo
´
c´ac d¯ı
˙’
nh, ca
.
nh v`a diˆe
.
n tu
.
o
.
ng ´u
.
ng cu
˙’
a d¯ˆo
`
thi
.
phˇa
˙’

.
o
.
ng ´u
.
ng, th`ı
n
∗
= f, m
∗
= m, f
∗
= n.
V´ı du
.
6.5.2 X´et mˆo
.
t ma
.
ng vˆa
.
n ta
˙’
i phˇa
˙’
ng (vˆo hu
.
´o
.
ng) G m`a mˆo

.
d¯ˆo
´
i ngˆa
˜
u G
∗
bˇa
`
ng c´ach cho hai d¯ı
˙’
nh kh´ac nhau s
∗
v`a t
∗
tu
.
o
.
ng ´u
.
ng v´o
.
i diˆe
.
n vˆo ha
.
n cu
˙’
a

a mˇa
.
t phˇa
˙’
ng trˆen. G´an tro
.
ng
lu
.
o
.
.
ng w(e
∗
) = c(e) cho ca
.
nh e
∗
(´u
.
ng v´o
.
i e). Bˆay gi`o
.
ta x´et c´ac b`ai to´an sau:
B`ai to´an 1. Trong G t`ım thiˆe
´
t diˆe
.
n A c´o kha

d¯i t`u
.
s
∗
d¯ˆe
´
n t
∗
; t´u
.
c l`a l`am cu
.
.
c tiˆe
˙’
u
w(µ
∗
) =

v
∗
∈µ
∗
w(v
∗
).
168

B`ai to´an 1 tu

ng d¯i ngˇa
´
n nhˆa
´
t v`a r˜o r`ang d¯ˆo
´
i v´o
.
i d¯ˆo
`
thi
.
phˇa
˙’
ng th`ı ca
˙’
hai b`ai to´an d¯´o l`a
mˆo
.
t.
B`ai to´an bˆo
´
n m`au c`on c´o thˆe
˙’
ph´at biˆe
˙’
u du
.
´o
.

.
t m`au.
T´ınh duy nhˆa
´
t cu
˙’
a d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa
˜
u
Vˆa
´
n d¯ˆe
`
d¯ˇa
.
t ra l`a d¯ˆo
´
i ngˆa
˜
u cu
˙’
a mˆo
.
t d¯ˆo

o
.
ng ph´ap xˆay du
.
.
ng cu
˙’
a d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa
˜
u, du
.
`o
.
ng
nhu
.
ho
.
.
p l´y cho rˇa
`
ng mˆo
.
t d¯ˆo

ng (trˆen mˇa
.
t phˇa
˙’
ng hoˇa
.
c mˇa
.
t cˆa
`
u) duy nhˆa
´
t.
V´ı du
.
6.5.3 Hai d¯ˆo
`
thi
.
trong H`ınh 6.11 l`a d¯ˇa
˙’
ng cˆa
´
u v´o
.
i hai biˆe
˙’
u diˆe
˜
n phˇa


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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
• •
••
•
e
1
e
2
e
3
e
4
e
5
e
6

.
n`ay.
D
-
i
.
nh l´y 6.5.4 Tˆa
´
t ca
˙’
c´ac d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa
˜
u cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng G l`a 2−d¯ˇa
˙’

˙’
a G.
V`ı mˆo
.
t d¯ˆo
`
thi
.
phˇa
˙’
ng 3−liˆen thˆong c´o biˆe
˙’
u diˆe
˜
n duy nhˆa
´
t trˆen mˇa
.
t cˆa
`
u, nˆen d¯ˆo
´
i ngˆa
˜
u
cu
˙’
a n´o l`a duy nhˆa
´
t. N´oi c´ach kh´ac, tˆa

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

•
• •
•
e
∗
1
e
∗
2
e
∗
3
e
∗
4
e
∗
5
e
∗

6.11(b).
6.6 D
-
ˆo
´
i ngˆa
˜
u tˆo
˙’
ho
.
.
p
Trong c´ac phˆa
`
n tru
.
´o
.
c ch´ung ta d¯˜a d¯i
.
nh ngh˜ıa v`a tha
˙’
o luˆa
.
n vˆe
`
d¯ˆo
´
i ngˆa

ng cu
˙’
a kh´ai
niˆe
.
m d¯ˆo
´
i ngˆa
˜
u khˆong phu
.
thuˆo
.
c v`ao c´ac kh´ai niˆe
.
m h`ınh ho
.
c. Tru
.
´o
.
c hˆe
´
t ta c´o
D
-
i
.
nh l´y 6.6.1 D
-

.
i tu
.
o
.
ng ´u
.
ng mˆo
.
t-mˆo
.
t gi˜u
.
a c´ac ca
.
nh trong G
1
v`a c´ac ca
.
nh trong G
2
sao cho mˆo
.
t
tˆa
.
p c´ac ca
.
nh trong G
1

Ch´u
.
ng minh. D
-
iˆe
`
u kiˆe
.
n cˆa
`
n. X´et mˆo
.
t biˆe
˙’
u diˆe
˜
n phˇa
˙’
ng cu
˙’
a d¯ˆo
`
thi
.
G. Ch´ung ta c˜ung v˜e mˆo
.
t
d¯ˆo
´
i ngˆa

n cu
˙’
a G v`a phˆan
chia mˇa
.
t phˇa
˙’
ng th`anh hai v`ung (D
-
i
.
nh l´y D
-
u
.
`o
.
ng cong Jordan). Do d¯´o c´ac d¯ı
˙’
nh cu
˙’
a G
∗
d¯u
.
o
.
.
c
phˆan hoa

t thiˆe
´
t diˆe
.
n trong
G
∗
. (Khˆong tˆa
.
p con thu
.
.
c su
.
.
n`ao cu
˙’
a µ
∗
l`a thiˆe
´
t diˆe
.
n cu
˙’
a G
∗
; ta
.
i sao?). Tu

.
t chu tr`ınh gˆo
`
m tˆa
.
p c´ac ca
.
nh
tu
.
o
.
ng ´u
.
ng S trong G sao cho S l`a mˆo
.
t chu tr`ınh.
170

D
-
iˆe
`
u kiˆe
.
n d¯u
˙’
. Gia
˙’
su

.
n trong G v`a c´ac chu tr`ınh trong G

v`a ngu
.
o
.
.
c la
.
i. Gia
˙’
su
.
˙’
G
∗
l`a d¯ˆo
`
thi
.
d¯ˆo
´
i ngˆa
˜
u cu
˙’
a
G. Khi d¯´o c´o mˆo
.

.
i tu
.
o
.
ng ´u
.
ng mˆo
.
t
mˆo
.
t gi˜u
.
a c´ac chu tr`ınh cu
˙’
a G

v`a G
∗
m`a d¯iˆe
`
u n`ay chı
˙’
ra rˇa
`
ng G

v`a G
∗

ˆo
´
i ngˆa
˜
u cu
˙’
a d¯ˆo
`
thi
.
con
Gia
˙’
su
.
˙’
G l`a d¯ˆo
`
thi
.
phˇa
˙’
ng v`a G
∗
l`a d¯ˆo
´
i ngˆa
˜
u cu
˙’

i d¯ˆo
`
thi
.
G v`a t`ım d¯ˆo
´
i ngˆa
˜
u cu
˙’
a d¯ˆo
`
thi
.
G \ {a}. Nˆe
´
u a l`a ca
.
nh biˆen cu
˙’
a hai diˆe
.
n, th`ı viˆe
.
c xo´a ca
.
nh a s˜e ho
.
.
p nhˆa

`
ng c´ach xo´a ca
.
nh
tu
.
o
.
ng ´u
.
ng a
∗
v`a sau d¯´o d¯ˆo
`
ng nhˆa
´
t hai d¯ı
˙’
nh m`a a
∗
liˆen thuˆo
.
c trong G
∗
\ {a
∗
}. Mˇa
.
t kh´ac nˆe
´

.
t d¯ˆo
´
i ngˆa
˜
u G
∗
th`ı d¯ˆo
´
i ngˆa
˜
u cu
˙’
a d¯ˆo
`
thi
.
con cu
˙’
a G c´o
thˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c bˇa

˙’
su
.
˙’
G l`a d¯ˆo
`
thi
.
phˇa
˙’
ng v`a G
∗
l`a d¯ˆo
´
i ngˆa
˜
u cu
˙’
a n´o. Gia
˙’
su
.
˙’
a l`a mˆo
.
t ca
.
nh cu
˙’
a G v`a ca

.
c l`a a tro
.
˙’
th`anh hai ca
.
nh trong chuˆo
˜
i). Khi d¯´o d¯ˆo
´
i ngˆa
˜
u cu
˙’
a d¯ˆo
`
thi
.
m´o
.
i nhˆa
.
n
d¯u
.
o
.
.
c ch´ınh l`a thˆem ca
.

c´ach r´ut go
.
n chuˆo
˜
i s˜e tu
.
o
.
ng ´u
.
ng v´o
.
i xo´a mˆo
.
t ca
.
nh song song trong G
∗
. Do d¯´o nˆe
´
u G c´o mˆo
.
t
d¯ˆo
´
i ngˆa
˜
u G
∗
, th`ı mo

bˇa
`
ng
phu
.
o
.
ng ph´ap trˆen.
D
-
ˆe
´
n nay ch´ung ta m´o
.
i chı
˙’
nghiˆen c´u
.
u d¯ˆo
´
i ngˆa
˜
u cu
˙’
a c´ac d¯ˆo
`
thi
.
phˇa
˙’

.
trˆen mˇa
.
t
phˇa
˙’
ng. Tuy nhiˆen, D
-
i
.
nh l´y 6.6.1 cho ph´ep ch´ung ta c´o thˆe
˙’
d¯i
.
nh ngh˜ıa la
.
i kh´ai niˆe
.
m n`ay m`a
khˆong phu
.
thuˆo
.
c v`ao c´ach biˆe
˙’
u diˆe
˜
n trˆen mˇa
.
t phˇa

.
khˆong phˇa
˙’
ng? N´oi c´ach
kh´ac, v´o
.
i d¯ˆo
`
thi
.
khˆong phˇa
˙’
ng G, c´o tˆo
`
n ta
.
i mˆo
.
t d¯ˆo
`
thi
.
G

tu
.
o
.
ng ´u
.


,
v`a ngu
.
o
.
.
c la
.
i? Cˆau tra
˙’
l`o
.
i l`a khˆong do kˆe
´
t qua
˙’
sau
D
-
i
.
nh l´y 6.6.2 [Whitney] D
-
ˆo
`
thi
.
c´o d¯ˆo
´

.
ng minh d¯ˆo
`
thi
.
khˆong phˇa
˙’
ng s˜e khˆong c´o d¯ˆo
´
i ngˆa
˜
u. Gia
˙’
su
.
˙’
G l`a d¯ˆo
`
thi
.
khˆong phˇa
˙’
ng. Khi d¯´o theo D
-
i
.
nh l´y
Kuratowski, G ch´u
.
a K

´
i ngˆa
˜
u chı
˙’
nˆe
´
u mo
.
i d¯ˆo
`
thi
.
con g cu
˙’
a G v`a mo
.
i d¯ˆo
`
thi
.
d¯ˆo
`
ng
phˆoi v´o
.
i g c´o mˆo
.
t d¯ˆo
´

nh l´y d¯u
.
o
.
.
c ch´u
.
ng minh. Ta s˜e ch´u
.
ng minh pha
˙’
n
ch´u
.
ng nhu
.
sau:
(a) Gia
˙’
su
.
˙’
K
3,3
c´o mˆo
.
t d¯ˆo
´
i ngˆa
˜

khˆong c´o thiˆe
´
t diˆe
.
n gˆo
`
m hai ca
.
nh
nˆen D khˆong c´o chu tr`ınh d¯ˆo
.
d`ai hai. T´u
.
c D khˆong c´o c´ac ca
.
nh song song. Do mo
.
i chu
tr`ınh trong K
3,3
c´o d¯ˆo
.
d`ai bˆo
´
n hoˇa
.
c s´au nˆen D khˆong c´o thiˆe
´
t diˆe
.

bˆa
.
c cu
˙’
a c´ac d¯ı
˙’
nh ´ıt nhˆa
´
t bˇa
`
ng bˆo
´
n nˆen D c´o ´ıt nhˆa
´
t nˇam d¯ı
˙’
nh, mˆo
˜
i d¯ı
˙’
nh c´o bˆa
.
c l´o
.
n ho
.
n
hoˇa
.
c bˇa

nh. Do d¯´o K
3,3
khˆong c´o d¯ˆo
´
i ngˆa
˜
u.
(b) Gia
˙’
su
.
˙’
K
5
c´o mˆo
.
t d¯ˆo
´
i ngˆa
˜
u l`a H. Ch´u ´y rˇa
`
ng K
5
c´o
1. 10 ca
.
nh;
2. khˆong c´o ca
.

nh;
2. khˆong c´o d¯ı
˙’
nh bˆa
.
c nho
˙’
ho
.
n ba;
3. khˆong c´o cˇa
.
p ca
.
nh song song;
4. c´ac chu tr`ınh c´o d¯ˆo
.
d`ai bˆo
´
n hoˇa
.
c s´au.
Khi d¯´o H ch´u
.
a mˆo
.
t lu
.
c gi´ac (mˆo
.

y ra trong H v`a H c´o 10 ca
.
nh, nˆen H c´o ´ıt nhˆa
´
t ba
˙’
y
d¯ı
˙’
nh. Bˆa
.
c cu
˙’
a mˆo
˜
i d¯ı
˙’
nh n`ay ´ıt nhˆa
´
t bˇa
`
ng ba. D
-
iˆe
`
u n`ay dˆa
˜
n d¯ˆe
´
n H c´o ´ıt nhˆa