1.3 T´ınh liˆen thˆong
1.3.1 Dˆay chuyˆe
`
n v`a chu tr`ınh
Gia
˙’
su
.
˙’
v
0
, v
k
l`a c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng G := (V, E). Dˆay chuyˆe
`
n µ t`u
.
v
0

d¯ˆe
´
n v
k
d¯ˆo
.
d`ai k l`a mˆo
.
t d˜ay xen k˜e (k + 1) d¯ı
˙’
nh v`a k ca
.
nh bˇa
´
t d¯ˆa
`
u t`u
.
v
0
v`a kˆe
´
t th´uc ta
.
i v
k
,
µ := {v
0
, e

1
, v
1
, e
2
, v
2
, . . . , v
k−1
, e
k
, v
k
},
trong d¯´o ca
.
nh e
i
liˆen thuˆo
.
c c´ac d¯ı
˙’
nh v
i−1
v`a v
i
, i = 1, 2, . . . , k. D
-
ˆe
˙’

gia
˙’
n tiˆe
.
n, ta thu
.
`o
.
ng viˆe
´
t
µ := {e
1
, e
2
, . . . , e
k
}.
Dˆay chuyˆe
`
n d¯u
.
o
.
.
c go
.
i l`a d¯o
.
n gia

˙’
n (tu
.
o
.
ng ´u
.
ng, so
.
cˆa
´
p) nˆe
´
u n´o khˆong d¯i hai lˆa
`
n qua
c`ung mˆo
.
t ca
.
nh (tu
.
o
.
ng ´u
.
ng, d¯ı
˙’
nh).
Chu tr`ınh l`a mˆo

.
t dˆay chuyˆe
`
n trong d¯´o d¯ı
˙’
nh d¯ˆa
`
u tr`ung v´o
.
i d¯ı
˙’
nh cuˆo
´
i. Chu tr`ınh qua
mˆo
˜
i ca
.
nh d¯´ung mˆo
.
t lˆa
`
n go
.
i l`a d¯o
.
n gia
˙’
n. Chu tr`ınh l`a so
.

cˆa
´
p nˆe
´
u n´o d¯i qua mˆo
˜
i d¯ı
˙’
nh d¯´ung
mˆo
.
t lˆa
`
n tr`u
.
d¯ı
˙’
nh d¯ˆa
`
u tiˆen hai lˆa
`
n (mˆo
.
t lˆa
`
n l´uc xuˆa
´
t ph´at v`a mˆo
.
t l´uc tro

.
˙’
vˆe
`
).
D
-
ˆo
`
thi
.
trong H`ınh 1.11 c´o
(a, e
1
, b, e
2
, c, e
3
, d, e
4
, b)
l`a dˆay chuyˆe
`
n t`u
.
d¯ı
˙’
nh a d¯ˆe
´
n d¯ı

˙’
nh b c´o d¯ˆo
.
d`ai bˆo
´
n. C´ac chu tr`ınh sau l`a so
.
cˆa
´
p
(b, e
2
, c, e
3
, d, e
4
, b), v`a (b, e
5
, f, e
7
, e, e
6
, b).


.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
b
c
d
e
f
g

•• •
•
•• •
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
H`ınh 1.11:
Trong tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi

.
khˆong c´o ca
.
nh song song (t´u
.
c l`a hai d¯ı
˙’
nh c´o nhiˆe
`
u nhˆa
´
t mˆo
.
t
ca
.
nh liˆen thuˆo
.
c ch´ung), d¯ˆe
˙’
d¯o
.
n gia
˙’
n dˆay chuyˆe
`
n µ d¯u
.
o
.

.
c viˆe
´
t la
.
i
µ = {v
0
, v
1
, v
2
, . . . , v
k
}.
23
1.3.2 D
-
u
.
`o
.
ng d¯i v`a ma
.
ch
Gia
˙’
su
.
˙’

v
0
, v
k
l`a c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng G := (V, E). D
-
u
.
`o
.
ng d¯i µ t`u
.
v
0
d¯ˆe
´
n v
k

d¯ˆo
.
d`ai
k l`a mˆo
.
t d˜ay xen k˜e (k + 1) d¯ı
˙’
nh v`a k cung bˇa
´
t d¯ˆa
`
u t`u
.
v
0
v`a kˆe
´
t th´uc ta
.
i v
k
,
µ := {v
0
, e
1
, v
1
, e
2

, v
2
, . . . , v
k−1
, e
k
, v
k
},
trong d¯´o cung e
i
liˆen thuˆo
.
c c´ac d¯ı
˙’
nh v
i−1
v`a v
i
, i = 1, 2, . . . , k. D
-
ˆe
˙’
gia
˙’
n tiˆe
.
n, ta c´o thˆe
˙’
k´y

hiˆe
.
u d¯u
.
`o
.
ng d¯i µ l`a {e
1
, e
2
, . . . , e
k
}.
Do d¯´o trong H`ınh 1.12 d˜ay c´ac cung
µ
1
:= {e
6
, e
5
, e
9
, e
8
, e
4
}
µ
2
:= {e

1
, e
6
, e
5
, e
9
}
µ
3
:= {e
1
, e
6
, e
5
, e
9
, e
10
, e
6
, e
4
}
l`a c´ac d¯u
.
`o
.
ng d¯i.

D
-
u
.
`o
.
ng d¯i l`a d¯o
.
n gia
˙’
n nˆe
´
u khˆong ch´u
.
a cung n`ao qu´a mˆo
.
t lˆa
`
n. Suy ra c´ac d¯u
.
`o
.
ng d¯i
µ
1
, µ
2
l`a d¯o
.
n gia

˙’
n, nhu
.
ng d¯u
.
`o
.
ng d¯i µ
3
khˆong d¯o
.
n gia
˙’
n do n´o su
.
˙’
du
.
ng cung e
6
hai lˆa
`
n.
D
-
u
.
`o
.
ng d¯i l`a so

.
cˆa
´
p nˆe
´
u khˆong d¯i qua d¯ı
˙’
nh n`ao qu´a mˆo
.
t lˆa
`
n. Khi d¯´o d¯u
.
`o
.
ng d¯i µ
2
l`a
so
.
cˆa
´
p nhu
.
ng c´ac d¯u
.
`o
.
ng d¯i µ
1

v`a µ
3
l`a khˆong so
.
cˆa
´
p. Hiˆe
˙’
n nhiˆen, d¯u
.
`o
.
ng d¯i so
.
cˆa
´
p l`a d¯o
.
n
gia
˙’
n nhu
.
ng ngu
.
o
.
.
c la
.

i khˆong nhˆa
´
t thiˆe
´
t d¯´ung. Chˇa
˙’
ng ha
.
n, ch´u ´y rˇa
`
ng d¯u
.
`o
.
ng d¯i µ
1
l`a d¯o
.
n
gia
˙’
n nhu
.
ng khˆong so
.
cˆa
´
p, d¯u
.
`o

.
ng d¯i µ
2
v`u
.
a d¯o
.
n gia
˙’
n v`a v`u
.
a so
.
cˆa
´
p, d¯u
.
`o
.
ng d¯i µ
3
khˆong
d¯o
.
n gia
˙’
n c˜ung khˆong so
.
cˆa
´

p.
Ch´u ´y rˇa
`
ng, kh´ai niˆe
.
m dˆay chuyˆe
`
n l`a ba
˙’
n sao khˆong c´o hu
.
´o
.
ng cu
˙’
a d¯u
.
`o
.
ng d¯i v`a ´ap
du
.
ng cho c´ac d¯ˆo
`
thi
.
m`a khˆong d¯ˆe
˙’
´y d¯ˆe
´

n hu
.
´o
.
ng cu
˙’
a c´ac cung.
D
-
u
.
`o
.
ng d¯i c˜ung c´o thˆe
˙’
d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bo
.
˙’
i d˜ay c´ac d¯ı
˙’
nh m`a ch´ung d¯i qua trong tru

.
`o
.
ng
ho
.
.
p khˆong c´o cung song song (t´u
.
c hai cung c´o c`ung gˆo
´
c v`a c`ung ngo
.
n). Do d¯´o, d¯u
.
`o
.
ng d¯i
µ
1
c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n bo
.
˙’
i d˜ay d¯ı

˙’
nh {v
2
, v
5
, v
4
, v
3
, v
5
, v
6
}.
Ma
.
ch l`a mˆo
.
t d¯u
.
`o
.
ng d¯i {e
1
, e
2
, . . . , e
k
} trong d¯´o d¯ı
˙’

nh gˆo
´
c cu
˙’
a cung e
1
tr`ung v´o
.
i d¯ı
˙’
nh
ngo
.
n cu
˙’
a cung e
k
. Do d¯´o d¯u
.
`o
.
ng d¯i {e
5
, e
9
, e
10
, e
6
} trong H`ınh 1.12 l`a ma

.
ch.
1.3.3 T´ınh liˆen thˆong
D
-
ˆo
`
thi
.
vˆo hu
.
´o
.
ng go
.
i l`a liˆen thˆong nˆe
´
u tˆa
´
t ca
˙’
c´ac cˇa
.
p d¯ı
˙’
nh v
i
v`a v
j
tˆo

`
n ta
.
i dˆay chuyˆe
`
n t`u
.
v
i
d¯ˆe
´
n v
j
. Quan hˆe
.
v
i
Rv
j
nˆe
´
u v`a chı
˙’
nˆe
´
u v
i
= v
j
hoˇa

.
c tˆo
`
n ta
.
i mˆo
.
t dˆay chuyˆe
`
n nˆo
´
i hai d¯ı
˙’
nh v
i
v`a v
j
l`a quan hˆe
.
tu
.
o
.
ng d¯u
.
o
.
ng (pha
˙’
n xa

.
, d¯ˆo
´
i x´u
.
ng v`a bˇa
´
c cˆa
`
u).
24
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.

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

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

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

.
.
e
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
1
.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
3
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.

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

.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
7
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
8
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
e
10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
e
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
e
5
.
.
.
.
.
.
.
.
.
.

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

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

.

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

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

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

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

•
H`ınh 1.12:
L´o
.
p tu
.
o
.
ng d¯u
.
o
.
ng trˆen V x´ac d¯i
.
nh bo
.
˙’
i quan hˆe
.
tu
.
o
.
ng d¯u
.
o
.
ng R phˆan hoa
.
ch tˆa

.
p V
th`anh c´ac tˆa
.
p con r`o
.
i nhau V
1
, V
2
, . . . , V
p
. Sˆo
´
p go
.
i l`a sˆo
´
th`anh phˆa
`
n liˆen thˆong cu
˙’
a d¯ˆo
`
thi
.
.
Theo d¯i
.
nh ngh˜ıa, d¯ˆo

`
thi
.
liˆen thˆong nˆe
´
u v`a chı
˙’
nˆe
´
u sˆo
´
th`anh phˆa
`
n liˆen thˆong bˇa
`
ng mˆo
.
t. C´ac
d¯ˆo
`
thi
.
con G
1
, G
2
, . . . , G
p
sinh bo
.

˙’
i c´ac tˆa
.
p con V
1
, V
2
, . . . , V
p
go
.
i l`a c´ac th`anh phˆa
`
n liˆen thˆong
cu
˙’
a d¯ˆo
`
thi
.
. Mˆo
˜
i th`anh phˆa
`
n liˆen thˆong l`a mˆo
.
t d¯ˆo
`
thi
.

liˆen thˆong.
H`ınh 1.13 minh ho
.
a d¯ˆo
`
thi
.
c´o ba th`anh phˆa
`
n liˆen thˆong.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
v
1
v
2
v
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
5
v
7
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

v
8
v
3
v
6
•
• •
•
• •
•
•
H`ınh 1.13: D

-
ˆo
`
thi
.
c´o ba th`anh phˆa
`
n liˆen thˆong.
X´ac d¯i
.
nh sˆo
´
th`anh phˆa
`
n liˆen thˆong cu
˙’
a d¯ˆo
`
thi
.
l`a mˆo
.
t trong nh˜u
.
ng b`ai to´an co
.
ba
˙’
n cu
˙’

a
l´y thuyˆe
´
t d¯ˆo
`
thi
.
v`a c´o nhiˆe
`
u ´u
.
ng du
.
ng trong thu
.
.
c tiˆe
˜
n; chˇa
˙’
ng ha
.
n, x´ac d¯i
.
nh t´ınh liˆen thˆong
cu
˙’
a ma
.
ch d¯iˆe

.
n, ma
.
ng d¯iˆe
.
n thoa
.
i, v.v.
Ch´ung ta s˜e tr`ınh b`ay mˆo
.
t sˆo
´
thuˆa
.
t to´an c´o th`o
.
i gian O(m) gia
˙’
i b`ai to´an n`ay v`ı n´o
25
cho ph´ep t`ım l`o
.
i gia
˙’
i cu
˙’
a mˆo
.
t sˆo
´

b`ai to´an kh´ac.
Bˇa
´
t d¯ˆa
`
u v´o
.
i d¯ı
˙’
nh n`ao d¯´o cu
˙’
a d¯ˆo
`
thi
.
, ch´ung ta liˆe
.
t kˆe c´ac d¯ı
˙’
nh theo th´u
.
tu
.
.
cu
˙’
a thuˆa
.
t
to´an t`ım kiˆe

´
m theo chiˆe
`
u sˆau, t´u
.
c l`a ch´ung ta d¯i, d¯ˆa
`
u tiˆen, xa nhˆa
´
t c´o thˆe
˙’
d¯u
.
o
.
.
c trˆen d¯ˆo
`
thi
.
m`a khˆong ta
.
o th`anh chu tr`ınh, v`a sau d¯´o tro
.
˙’
vˆe
`
vi
.
tr´ı r˜e nh´anh gˆa

`
n d¯ˆay nhˆa
´
t m`a ch´ung ta
d¯˜a bo
˙’
qua, v`a tiˆe
´
p tu
.
c cho d¯ˆe
´
n khi tro
.
˙’
vˆe
`
d¯ı
˙’
nh xuˆa
´
t ph´at. Do d¯´o tˆa
.
p c´ac d¯ı
˙’
nh bˇa
´
t gˇa
.
p s˜e

ta
.
o th`anh th`anh phˆa
`
n liˆen thˆong d¯ˆa
`
u tiˆen.
Nˆe
´
u tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
d¯u
.
o
.
.
c duyˆe
.
t th`ı d¯ˆo
`

thi
.
liˆen thˆong; ngu
.
o
.
.
c la
.
i, ch´ung ta
kho
.
˙’
i d¯ˆa
`
u la
.
i thu
˙’
tu
.
c trˆen v´o
.
i mˆo
.
t d¯ı
˙’
nh m´o
.
i chu

.
a d¯u
.
o
.
.
c viˆe
´
ng thˇam; do d¯´o ta xˆay du
.
.
ng d¯u
.
o
.
.
c
th`anh phˆa
`
n liˆen thˆong th´u
.
hai, v`a vˆan vˆan.
Thuˆa
.
t to´an du
.
´o
.
i d¯ˆay tr`ınh b`ay giai d¯oa
.

n d¯ˆa
`
u tiˆen, t´u
.
c l`a t`ım th`anh phˆa
`
n liˆen thˆong
ch´u
.
a mˆo
.
t d¯ı
˙’
nh d¯˜a cho-nˆe
´
u th`anh phˆa
`
n n`ay ch´u
.
a tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi

.
th`ı d¯ˆo
`
thi
.
liˆen
thˆong.
K´y hiˆe
.
u num(i) l`a sˆo
´
hiˆe
.
u cu
˙’
a d¯ı
˙’
nh v
i
trong qu´a tr`ınh t`ım kiˆe
´
m. Nˆe
´
u ta bˇa
´
t d¯ˆa
`
u bˇa
`
ng

d¯ı
˙’
nh s th`ı d¯ˇa
.
t num(s) = 1 . K´y hiˆe
.
u P (i) l`a d¯ı
˙’
nh d¯´u
.
ng liˆe
`
n tru
.
´o
.
c d¯ı
˙’
nh v
i
trong cˆay c´o gˆo
´
c
(xem Chu
.
o
.
ng 4) d¯u
.
o

.
.
c xˆay du
.
.
ng trong qu´a tr`ınh thu
.
.
c hiˆe
.
n thuˆa
.
t to´an.
X´et d¯ˆo
`
thi
.
d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bo
.
˙’
i ´anh xa

.
d¯a tri
.
Γ. D
-
ˇa
.
t d
+
i
l`a sˆo
´
c´ac d¯ı
˙’
nh kˆe
`
d¯ı
˙’
nh v
i
: d
+
i
:=
#Γ(v
i
). V´o
.
i mˆo
˜

i k = 1, 2, . . . , n, k´y hiˆe
.
u Γ
k
(v
i
) l`a d¯ı
˙’
nh th´u
.
k trong tˆa
.
p Γ(v
i
).
D
-
ˆe
˙’
thu
.
.
c hiˆe
.
n t`ım kiˆe
´
m trˆen d¯ˆo
`
thi
.

, ch´ung ta cˆa
`
n mˆo
˜
i giai d¯oa
.
n cu
˙’
a thuˆa
.
t to´an chı
˙’
sˆo
´
n(i) cu
˙’
a d¯ı
˙’
nh d¯u
.
o
.
.
c viˆe
´
ng thˇam cuˆo
´
i c`ung t`u
.
d¯ı

˙’
nh v
i
. Do d¯´o ta bˇa
´
t d¯ˆa
`
u v´o
.
i n(i) = 0.
Du
.
´o
.
i d¯ˆay l`a thuˆa
.
t to´an (da
.
ng khˆong d¯ˆe
.
qui) cu
˙’
a Tr´emaux d¯u
.
a ra nˇa
`
m 1882 v`a sau d¯´o
d¯u
.
o

.
.
c Tarjan ca
˙’
i tiˆe
´
n [53].
Thuˆa
.
t to´an Tr´emaux-Tarjan t`ım th`anh phˆa
`
n liˆen thˆong ch´u
.
a d¯ı
˙’
nh s.
1. [Kho
.
˙’
i ta
.
o] D
-
ˇa
.
t P (i) = 0, d
+
i
:= #Γ(v
i

) v`a n(i) = 0 v´o
.
i mo
.
i d¯ı
˙’
nh v
i
, i = 1, 2, . . . , n;
k = 0, num(s) = 1, P(s) = s (tu`y ´y, kh´ac khˆong), i = s.
2. [Bu
.
´o
.
c lˇa
.
p] Trong khi (n(i) = d(i)) hoˇa
.
c (i = s) thu
.
.
c hiˆe
.
n
• Nˆe
´
u n(i) = d(i) d¯ˇa
.
t i = P (i) (lˆa
`

n ngu
.
o
.
.
c);
• ngu
.
o
.
.
c la
.
i, d¯ˇa
.
t n(i) = n(i) + 1 (viˆe
´
ng thˇam d¯ı
˙’
nh kˆe
´
tiˆe
´
p trong Γ(v
i
)), v`a j =
Γ
n(i)
(v
i

). Nˆe
´
u P (j) = 0 th`ı g´an P(j) = i, i = j, k = k + 1, num(i) = k.
Kˆe
´
t th ´uc thuˆa
.
t to´an, nˆe
´
u k = n th`ı d¯ˆo
`
thi
.
liˆen thˆong; ngu
.
o
.
.
c la
.
i th`anh phˆa
`
n liˆen thˆong ch´u
.
a
d¯ı
˙’
nh s gˆo
`
m k d¯ı

˙’
nh m`a num(i) nhˆa
.
n c´ac gi´a tri
.
t`u
.
1 d¯ˆe
´
n k.
26
V´ı du
.
1.3.1 X´et d¯ˆo
`
thi
.
trong H`ınh 1.14. C´ac d¯ı
˙’
nh s˜e d¯u
.
o
.
.
c viˆe
´
ng thˇam theo th´u
.
tu
.

.
1, 4, 2, 3
v`a 5. Qu´a tr`ınh t`ım kiˆe
´
m c´o thˆe
˙’
biˆe
˙’
u diˆe
˜
n th`anh cˆay c´o gˆo
´
c (d¯ı
˙’
nh gˆo
´
c l`a v
1
) trong H`ınh

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
1
v
4
v
2

v
3
v
5
• • •
•
•
H`ınh 1.14:
1.15.

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

.

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


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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 2 3
4
5
v
1
v
4
v
2
v
3
v
5

• • •
•
•
H`ınh 1.15:
Thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u sˆau
1. Thˇam d¯ı
˙’
nh xuˆa
´
t ph´at s.
2. V´o
.
i mˆo
˜
i d¯ı
˙’
nh w kˆe
`
v´o
.
i v (c´o hu
.
´o
.

ng t`u
.
v d¯ˆe
´
n w) l`am c´ac bu
.
´o
.
c sau:
Nˆe
´
u w chu
.
a d¯u
.
o
.
.
c thˇam, ´ap du
.
ng thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u sˆau v´o
.
i w nhu
.

l`a
d¯ı
˙’
nh xuˆa
´
t ph´at.
Trong c´ach t`ım kiˆe
´
m theo chiˆe
`
u sˆau, ta d¯i theo d¯u
.
`o
.
ng t`u
.
d¯ı
˙’
nh xuˆa
´
t ph´at cho d¯ˆe
´
n khi
d¯a
.
t d¯ˆe
´
n mˆo
.
t d¯ı

˙’
nh c´o tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh kˆe
`
n´o d¯˜a d¯u
.
o
.
.
c viˆe
´
ng thˇam. Sau d¯´o ta quay la
.
i d¯ı
˙’
nh
27
cuˆo
´
i c`ung v`u
.
a d¯u
.
o
.

.
c thˇam do
.
c theo d¯u
.
`o
.
ng n`ay sao cho c´ac d¯ı
˙’
nh kˆe
`
v´o
.
i n´o (c´o hu
.
´o
.
ng t`u
.
n´o d¯i ra trong tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.

c´o hu
.
´o
.
ng) c´o thˆe
˙’
thˇam d¯u
.
o
.
.
c. D
-
ˆe
˙’
c´o thˆe
˙’
quay tro
.
˙’
la
.
i, ta
lu
.
u tr˜u
.
c´ac d¯ı
˙’
nh do

.
c theo d¯u
.
`o
.
ng n`ay trong mˆo
.
t ngˇan xˆe
´
p. Nˆe
´
u thu
˙’
tu
.
c d¯u
.
o
.
.
c viˆe
´
t da
.
ng d¯ˆe
.
quy th`ı ngˇan xˆe
´
p n`ay d¯u
.

o
.
.
c ba
˙’
o tr`ı mˆo
.
t c´ach tu
.
.
d¯ˆo
.
ng; trong tru
.
`o
.
ng ho
.
.
p ngu
.
o
.
.
c la
.
i, cˆa
`
n mˆo
.

t
ma
˙’
ng d¯´anh dˆa
´
u c´ac d¯ı
˙’
nh d¯˜a d¯u
.
o
.
.
c viˆe
´
ng thˇam.
Thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u rˆo
.
ng
Trong thuˆa
.
t to´an n`ay, ch´ung ta thˇam c´ac d¯ı
˙’
nh theo t`u
.

ng m´u
.
c mˆo
.
t, v`a khi thˇam mˆo
.
t d¯ı
˙’
nh
o
.
˙’
m´u
.
c n`ao d¯´o, ta pha
˙’
i lu
.
u tr˜u
.
n´o d¯ˆe
˙’
c´o thˆe
˙’
tro
.
˙’
la
.
i khi d¯i hˆe

´
t mˆo
.
t m´u
.
c, v`ı vˆa
.
y c´o thˆe
˙’
thˇam
c´ac d¯ı
˙’
nh kˆe
`
cu
˙’
a n´o. Thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u rˆo
.
ng du
.
´o
.
i d¯ˆay d`ung mˆo
.

t h`ang d¯o
.
.
i theo
c´ach n`ay.
1. Thˇam d¯ı
˙’
nh xuˆa
´
t ph´at.
2. Kho
.
˙’
i d¯ˆo
.
ng mˆo
.
t h`ang d¯o
.
.
i chı
˙’
ch´u
.
a d¯ı
˙’
nh xuˆa
´
t ph´at.
3. Trong khi h`ang d¯o

.
.
i khˆong rˆo
˜
ng l`am c´ac bu
.
´o
.
c sau:
Lˆa
´
y mˆo
.
t d¯ı
˙’
nh v t`u
.
h`ang d¯o
.
.
i.
V´o
.
i tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh w kˆe

`
v´o
.
i v, l`am c´ac bu
.
´o
.
c sau:
Nˆe
´
u (w chu
.
a d¯u
.
o
.
.
c thˇam) th`ı:
Thˇam w.
Thˆem w v`ao h`ang d¯o
.
.
i.
C´ac thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u rˆo

.
ng v`a t`ım kiˆe
´
m theo chiˆe
`
u sˆau l`a rˆa
´
t co
.
ba
˙’
n cho
nhiˆe
`
u thuˆa
.
t to´an kh´ac d¯ˆe
˙’
xu
.
˙’
l´y d¯ˆo
`
thi
.
. V´ı du
.
, d¯ˆe
˙’
duyˆe

.
t mˆo
.
t d¯ˆo
`
thi
.
, ta c´o thˆe
˙’
´ap du
.
ng nhiˆe
`
u
lˆa
`
n mˆo
.
t trong c´ac c´ach n´oi trˆen, cho
.
n c´ac d¯ı
˙’
nh xuˆa
´
t ph´at m´o
.
i nˆe
´
u cˆa
`

n thiˆe
´
t, cho d¯ˆe
´
n khi
tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c thˇam.
1.3.4 Cˆa
`
u, k−liˆen thˆong
D
-
iˆe
˙’
m kh´o
.
p cu
˙’
a d¯ˆo
`

thi
.
l`a mˆo
.
t d¯ı
˙’
nh m`a xo´a n´o s˜e tˇang sˆo
´
th`anh phˆa
`
n liˆen thˆong; cˆa
`
u l`a ca
.
nh
m`a xo´a n´o c˜ung c´o a
˙’
nh hu
.
o
.
˙’
ng tu
.
o
.
ng tu
.
.
. D

-
ˆo
`
thi
.
trong H`ınh 1.14 c´o mˆo
.
t d¯iˆe
˙’
m kh´o
.
p l`a d¯ı
˙’
nh
v
4
v`a hai cˆa
`
u l`a c´ac ca
.
nh (v
1
, v
4
) v`a (v
4
, v
5
).
V´ı du

.
1.3.2 Trong mˆo
.
t d¯ˆo
`
thi
.
khˆong c´o chu tr`ınh, c´ac d¯ı
˙’
nh khˆong pha
˙’
i l`a d¯ı
˙’
nh treo, t´u
.
c
d¯ı
˙’
nh c´o bˆa
.
c ≥ 2, l`a d¯iˆe
˙’
m kh´o
.
p. Ngu
.
o
.
.
c la

.
i, d¯ˆo
`
thi
.
c´o chu tr`ınh Hamilton (xem Phˆa
`
n 5.3)
khˆong c´o d¯iˆe
˙’
m kh´o
.
p.
28
V´ı du
.
1.3.3 [Ma
.
ng thˆong tin] Gia
˙’
su
.
˙’
V l`a tˆa
.
p ho
.
.
p nh˜u
.

ng ngu
.
`o
.
i thuˆo
.
c mˆo
.
t tˆo
˙’
ch´u
.
c n`ao
d¯´o; ta d¯ˇa
.
t (a, b) ∈ E nˆe
´
u ngu
.
`o
.
i a v`a b c´o thˆe
˙’
b´ao tin v´o
.
i nhau. Nh˜u
.
ng ngu
.
`o

.
i liˆen la
.
c l`a
nh˜u
.
ng d¯iˆe
˙’
m kh´o
.
p. Nh˜u
.
ng ngu
.
`o
.
i d¯´o l`a nh˜u
.
ng mˇa
´
t x´ıch quan tro
.
ng, v`ı mˆa
´
t ho
.
s˜e ph´a v˜o
.
t´ınh thˆo
´

ng nhˆa
´
t v`a su
.
.
liˆen kˆe
´
t cu
˙’
a tˆo
˙’
ch´u
.
c.
D
-
i
.
nh l´y 1.3.4 Gia
˙’
su
.
˙’
G = (V, E) l`a d¯ˆo
`
thi
.
liˆen thˆong. Khi d¯´o d¯ı
˙’
nh v ∈ V l`a d¯iˆe

˙’
m kh´o
.
p
nˆe
´
u v`a chı
˙’
nˆe
´
u tˆo
`
n ta
.
i hai d¯ı
˙’
nh a v`a b sao cho mo
.
i dˆay chuyˆe
`
n nˆo
´
i a v´o
.
i b d¯ˆe
`
u d¯i qua v.
Ch´u
.
ng minh. D

-
iˆe
`
u kiˆe
.
n cˆa
`
n. Nˆe
´
u d¯ˆo
`
thi
.
con sinh bo
.
˙’
i tˆa
.
p ho
.
.
p V \ {v} khˆong liˆen thˆong th`ı
n´o ch´u
.
a ´ıt nhˆa
´
t hai th`anh phˆa
`
n C v`a C; gia
˙’

su
.
˙’
a l`a mˆo
.
t d¯ı
˙’
nh n`ao d¯´o cu
˙’
a C v`a b l`a mˆo
.
t
d¯ı
˙’
nh n`ao d¯´o cu
˙’
a C. Trong d¯ˆo
`
thi
.
liˆen thˆong ban d¯ˆa
`
u G mo
.
i dˆay chuyˆe
`
n bˆa
´
t k`y nˆo
´

i a v´o
.
i b
d¯ˆe
`
u pha
˙’
i d¯i qua v.
D
-
iˆe
`
u kiˆe
.
n d¯u
˙’
. Nˆe
´
u mˆo
.
t dˆay chuyˆe
`
n bˆa
´
t k`y nˆo
´
i a v´o
.
i b d¯ˆe
`

u d¯i qua v th`ı d¯ˆo
`
thi
.
con sinh ra
bo
.
˙’
i V \ {v} khˆong thˆe
˙’
liˆen thˆong; bo
.
˙’
i vˆa
.
y d¯ı
˙’
nh v l`a d¯iˆe
˙’
m kh´o
.
p. 
Ta c´o thˆe
˙’
d¯i
.
nh ngh˜ıa: d¯ˆo
`
thi
.

n d¯ı
˙’
nh (n ≥ 3) l`a 2−liˆen thˆong hay d¯ˆo
`
thi
.
khˆong t´ach
d¯u
.
o
.
.
c nˆe
´
u v`a chı
˙’
nˆe
´
u n´o liˆen thˆong v`a khˆong c´o d¯iˆe
˙’
m kh´o
.
p. C´ac d¯ˆo
`
thi
.
con 2−liˆen thˆong cu
.
.
c

d¯a
.
i cu
˙’
a G ta
.
o th`anh mˆo
.
t phˆan hoa
.
ch cu
˙’
a G, v`a go
.
i l`a c´ac th`anh phˆa
`
n 2−liˆen thˆong cu
˙’
a G.
D
-
ˆe
˙’
t`ım c´ac d¯iˆe
˙’
m kh´o
.
p v`a c´ac th`anh phˆa
`
n 2−liˆen thˆong ta c´o thˆe

˙’
su
.
˙’
du
.
ng thuˆa
.
t to´an
t`ım kiˆe
´
m theo chiˆe
`
u sˆau.
V´o
.
i mˆo
˜
i d¯ı
˙’
nh v
i
, x´et tˆa
.
p D(i) c´ac d¯ı
˙’
nh d¯´u
.
ng liˆe
`

n tru
.
´o
.
c d¯ı
˙’
nh v
i
trong cˆay T x´ac d¯i
.
nh
bo
.
˙’
i thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u sˆau. Khi d¯´o, v´o
.
i mo
.
i d¯ı
˙’
nh v
j
∈ D(i) ta c´o
l ( j) = min

k∈Γ(v
j
)
(num(k))
l`a sˆo
´
nho
˙’
nhˆa
´
t d¯u
.
o
.
.
c g´an cho d¯ı
˙’
nh kˆe
`
v´o
.
i d¯ı
˙’
nh v
j
trong G. Bˆay gi`o
.
ta d¯i
.
nh ngh˜ıa mˆo

.
t chı
˙’
sˆo
´
m´o
.
i
inf(i) := min
v
j
∈D(i)
l(j).
Do d¯´o chı
˙’
sˆo
´
n`ay tu
.
o
.
ng ´u
.
ng cu
.
.
c tiˆe
˙’
u cu
˙’

a num(i) v`a sˆo
´
nho
˙’
nhˆa
´
t d¯u
.
o
.
.
c g´an cho c´ac
d¯ı
˙’
nh m`a c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c bˇa
`
ng d¯´ung mˆo
.
t ca
.
nh t`u

.
mˆo
.
t trong c´ac hˆa
.
u duˆe
.
cu
˙’
a v
i
trong cˆay
T.
Do d¯´o, trong V´ı du
.
1.3.1 (H`ınh 1.15), d¯ı
˙’
nh v
2
c´o d¯´ung mˆo
.
t d¯ı
˙’
nh tru
.
´o
.
c liˆe
`
n kˆe

`
l`a d¯ı
˙’
nh
v
4
, v`a do d¯´o inf(2) = num(4) = 2.
Ch´u ´y rˇa
`
ng inf(i) ≤ num(i) v`ı kho
.
˙’
i d¯ˆa
`
u t`u
.
tiˆe
`
n bˆo
´
i cu
˙’
a v
i
n´o c´o thˆe
˙’
tro
.
˙’
vˆe

`
v
i
.
29
Ho
.
n n˜u
.
a, dˆe
˜
d`ang chı
˙’
ra rˇa
`
ng, nˆe
´
u inf(i) = num(i) th`ı d¯ı
˙’
nh v
i
l`a d¯iˆe
˙’
m kh´o
.
p cu
˙’
a d¯ˆo
`
thi

.
. Ngo`ai ra, c´ac d¯ı
˙’
nh bˇa
´
t gˇa
.
p khi duyˆe
.
t tro
.
˙’
la
.
i d¯ı
˙’
nh v
i
ta
.
o th`anh mˆo
.
t th`anh phˆa
`
n 2−liˆen
thˆong.
Thuˆa
.
t to´an du
.

´o
.
i d¯ˆay tr`ınh b`ay phu
.
o
.
ng ph´ap x´ac d¯i
.
nh c´ac d¯iˆe
˙’
m kh´o
.
p cu
˙’
a d¯ˆo
`
thi
.
liˆen
thˆong xuˆa
´
t ph´at t`u
.
d¯ı
˙’
nh s.
Thuˆa
.
t to´an Tarjan t`ım d¯iˆe
˙’

m kh´o
.
p cu
˙’
a d¯ˆo
`
thi
.
liˆen thˆong xuˆa
´
t ph´at t`u
.
d¯ı
˙’
nh s
1. [Kho
.
˙’
i ta
.
o] D
-
ˇa
.
t P (i) = 0, d
+
i
:= #Γ(v
i
), n(i) = 0 v`a inf(i) = ∞ v´o

.
i mo
.
i d¯ı
˙’
nh v
i
, i =
1, 2, . . . , n; k = 0, num(s) = 1, P(s) = s, i = s.
2. [Bu
.
´o
.
c lˇa
.
p] Trong khi (n(i) = d(i)) hoˇa
.
c (i = s) thu
.
.
c hiˆe
.
n
• Nˆe
´
u n(i) = d(i) d¯ˇa
.
t
q = inf(i), i = P (i), inf(i) = min(q, inf(i)).
Nˆe

´
u inf(i) =num(i) th`ı v
i
l`a d¯iˆe
˙’
m kh´o
.
p (v`a ta c´o thˆe
˙’
x´ac d¯i
.
nh th`anh phˆa
`
n 2−liˆen
thˆong).
• Ngu
.
o
.
.
c la
.
i, t´u
.
c l`a n(i) = d(i) (viˆe
´
ng thˇam d¯ı
˙’
nh kˆe
´

tiˆe
´
p trong Γ(v
i
))
Nˆe
´
u j = P(i) th`ı g´an n(i) = n(i) + 1, j = Γ
n(i)
(i).
Nˆe
´
u P (j) = 0 th`ı g´an
inf(i) = min(inf(i), num(i)), P(j) = i, i = j, k = k + 1, num(i) = k.
Ngu
.
o
.
.
c la
.
i nˆe
´
u P (j) = 0 g´an inf(i) = min(inf(i), num(j)).
Dˆe
˜
d`ang kiˆe
˙’
m tra v´o
.

i v´ı du
.
tru
.
´o
.
c, d¯ı
˙’
nh v
4
l`a d¯iˆe
˙’
m kh´o
.
p. Ch´u ´y rˇa
`
ng c´o thˆe
˙’
x´ac d¯i
.
nh
th`anh phˆa
`
n 2−liˆen thˆong bˇa
`
ng c´ach su
.
˙’
a d¯ˆo
˙’

i Bu
.
´o
.
c 2 trong Thuˆa
.
t to´an Tarjan.
Mˆe
.
nh d¯ˆe
`
sau l`a hiˆe
˙’
n nhiˆen:
Mˆe
.
nh d¯ˆe
`
1.3.5 C´ac thuˆa
.
t to´an Tr´emaux-Tarjan v`a Tarjan c´o th`o
.
i gian O(m).
Thiˆe
´
t diˆe
.
n A ⊂ V cu
˙’
a d¯ˆo

`
thi
.
liˆen thˆong G l`a tˆa
.
p con A c´ac d¯ı
˙’
nh sao cho d¯ˆo
`
thi
.
con
G
V \A
nhˆa
.
n d¯u
.
o
.
.
c t`u
.
G bˇa
`
ng c´ach xo´a c´ac d¯ı
˙’
nh trong A (v`a c´ac ca
.
nh liˆen thuˆo

.
c n´o) khˆong
liˆen thˆong.
D
-
ˆo
`
thi
.
go
.
i l`a k−liˆen thˆong nˆe
´
u v`a chı
˙’
nˆe
´
u n´o liˆen thˆong, c´o sˆo
´
d¯ı
˙’
nh n ≥ k+1, v`a khˆong
ch´u
.
a mˆo
.
t thiˆe
´
t diˆe
.

n c´o lu
.
.
c lu
.
o
.
.
ng (k − 1).
30
C´ac d¯ˆo
`
thi
.
con k−liˆen thˆong cu
.
.
c d¯a
.
i cu
˙’
a G ta
.
o th`anh mˆo
.
t phˆan hoa
.
ch cu
˙’
a G v`a go

.
i
l`a c´ac th`anh phˆa
`
n k−liˆen thˆong.
C´ac th`anh phˆa
`
n 3−liˆen thˆong cu
˙’
a d¯ˆo
`
thi
.
c´o thˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c trong th`o
.
i gian O(m) bˇa
`
ng
thuˆa
.
t to´an tu

.
o
.
ng tu
.
.
cu
˙’
a Tarjan.
D
-
a d¯ˆo
`
thi
.
liˆen thˆong G go
.
i l`a k−ca
.
nh liˆen thˆong nˆe
´
u n´o vˆa
˜
n c`on liˆen thˆong khi xo´a d¯i
´ıt ho
.
n k ca
.
nh.
Do d¯´o, d¯a d¯ˆo

`
thi
.
l`a 2−liˆen thˆong nˆe
´
u v`a chı
˙’
nˆe
´
u n´o liˆen thˆong v`a khˆong ch´u
.
a cˆa
`
u.
Bˇa
`
ng c´ach su
.
˙’
a d¯ˆo
˙’
i la
.
i thuˆa
.
t to´an Tarjan, ta c´o thˆe
˙’
x´ac d¯i
.
nh c´ac cˆa

`
u trong th`o
.
i gian O(m).
X´et t´ınh 2−ca
.
nh liˆen thˆong c´o nhiˆe
`
u ´u
.
ng du
.
ng trong thu
.
.
c tˆe
´
: ma
.
ng d¯iˆe
.
n, d¯iˆe
.
n thoa
.
i, v.v.,
pha
˙’
i 2−ca
.

nh liˆen thˆong!
1.3.5 D
-
ˆo
`
thi
.
liˆen thˆong ma
.
nh
D
-
ˆo
`
thi
.
c´o hu
.
´o
.
ng go
.
i l`a liˆen thˆong ma
.
nh nˆe
´
u tˆa
´
t ca
˙’

c´ac cˇa
.
p d¯ı
˙’
nh v
i
v`a v
j
tˆo
`
n ta
.
i d¯u
.
`o
.
ng d¯i
t`u
.
v
i
d¯ˆe
´
n v
j
.
X´et quan hˆe
.
v
i

Rv
j
nˆe
´
u v`a chı
˙’
nˆe
´
u hoˇa
.
c v
i
= v
j
hoˇa
.
c tˆo
`
n ta
.
i d¯u
.
`o
.
ng d¯i t`u
.
d¯ı
˙’
nh v
i

d¯ˆe
´
n
d¯ı
˙’
nh v
j
v`a d¯u
.
`o
.
ng d¯i t`u
.
d¯ı
˙’
nh v
j
d¯ˆe
´
n d¯ı
˙’
nh v
i
. Dˆe
˜
thˆa
´
y d¯ˆay l`a quan hˆe
.
tu

.
o
.
ng d¯u
.
o
.
ng (pha
˙’
n
xa
.
, d¯ˆo
´
i x´u
.
ng v`a bˇa
´
c cˆa
`
u).
L´o
.
p tu
.
o
.
ng d¯u
.
o

.
ng trˆen V x´ac d¯i
.
nh bo
.
˙’
i quan hˆe
.
tu
.
o
.
ng d¯u
.
o
.
ng R phˆan hoa
.
ch tˆa
.
p V
th`anh c´ac tˆa
.
p con r`o
.
i nhau V
1
, V
2
, . . . , V

p
. Sˆo
´
p go
.
i l`a sˆo
´
th`anh phˆa
`
n liˆen thˆong ma
.
nh cu
˙’
a d¯ˆo
`
thi
.
. C´ac d¯ˆo
`
thi
.
con G
1
, G
2
, . . . , G
p
sinh bo
.
˙’

i c´ac tˆa
.
p con V
1
, V
2
, . . . , V
p
go
.
i l`a c´ac th`anh phˆa
`
n
liˆen thˆong ma
.
nh cu
˙’
a G. Theo d¯i
.
nh ngh˜ıa, d¯ˆo
`
thi
.
liˆen thˆong ma
.
nh nˆe
´
u v`a chı
˙’
nˆe

´
u sˆo
´
th`anh
phˆa
`
n liˆen thˆong ma
.
nh bˇa
`
ng mˆo
.
t.
Nhˆa
.
n x´et rˇa
`
ng, th`anh phˆa
`
n liˆen thˆong ma
.
nh C
l
ch´u
.
a d¯ı
˙’
nh v
l
d¯u

.
o
.
.
c cho bo
.
˙’
i
C
l
=
ˆ
Γ
v
l
∩
ˆ
Γ
−1
v
l
,
v`a t`u
.
d¯´o suy ra mˆo
.
t thuˆa
.
t to´an rˆa
´

t d¯o
.
n gia
˙’
n th`o
.
i gian d¯a th´u
.
c O(m) du
.
.
a trˆen thuˆa
.
t to´an
t`ım kiˆe
´
m theo chiˆe
`
u sˆau m`a c´o thˆe
˙’
su
.
˙’
du
.
ng n´o d¯ˆe
˙’
t`ım C
l
.

Do d¯´o t´ınh liˆen thˆong ma
.
nh dˆe
˜
d`ang kiˆe
˙’
m tra. Chı
˙’
cˆa
`
n x´et khi n`ao C
l
≡ V. (H˜ay gia
˙’
i
b`ai to´an n`ay bˇa
`
ng ma trˆa
.
n).
Nˆe
´
u mˇa
.
t kh´ac, ch´ung ta muˆo
´
n t`ım tˆa
´
t ca
˙’

c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh, ta s˜e su
.
˙’
du
.
ng Thuˆa
.
t to´an Tarjan.
31
Thˆa
.
t vˆa
.
y ta s˜e ch´u
.
ng minh rˇa
`
ng, thuˆa
.
t to´an Tarjan ´ap du
.
ng v´o
.
i c´ac d¯ˆo
`
thi

.
c´o hu
.
´o
.
ng,
cho ph´ep t`ım c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh.
Ch´ung ta kho
.
˙’
i d¯ˆa
`
u v´o
.
i thuˆa
.
t to´an t`ım kiˆe
´
m theo chiˆe
`
u sˆau, nhu
.
trong c´ac thuˆa
.
t to´an
t`ım kiˆe

´
m theo chiˆe
`
u sˆau v`a Tarjan. V´o
.
i mˆo
˜
i d¯ı
˙’
nh v
i
x´et mˆo
.
t chı
˙’
sˆo
´
m´o
.
i l`a sˆo
´
nho
˙’
nhˆa
´
t cu
˙’
a
chı
˙’

sˆo
´
d¯ı
˙’
nh m`a c´o thˆe
˙’
d¯ˆe
´
n n´o bˇa
`
ng chı
˙’
mˆo
.
t cung t`u
.
mˆo
.
t hˆa
.
u duˆe
.
cu
˙’
a v
i
trong cˆay gia pha
˙’
.
Chı

˙’
sˆo
´
m´o
.
i n`ay d¯u
.
o
.
.
c k´y hiˆe
.
u l`a inf(i).
Nhˆa
.
n x´et rˇa
`
ng ch´ung ta luˆon luˆon c´o inf(i) ≤ num(i). Dˆe
˜
d`ang chı
˙’
ra rˇa
`
ng khi ch´ung
ta tro
.
˙’
la
.
i trong cˆay gia pha

˙’
, th`ı mˆo
.
t d¯ı
˙’
nh m`a xa
˙’
y ra d¯ˇa
˙’
ng th´u
.
c inf(i) = num(i) s˜e phˆan
hoa
.
ch d¯ˆo
`
thi
.
th`anh ´ıt nhˆa
´
t hai th`anh phˆa
`
n liˆen thˆong ma
.
nh, v`a mˆo
.
t trong ch´ung tu
.
o
.

ng ´u
.
ng
tˆa
.
p c´ac d¯ı
˙’
nh m`a d¯˜a d¯u
.
o
.
.
c viˆe
´
ng thˇam tru
.
´o
.
c khi t´o
.
i d¯ı
˙’
nh v
i
.
D
-
ˆo
`
thi

.
trong H`ınh 1.16 c´o ba th`anh phˆa
`
n liˆen thˆong ma
.
nh:
C
1
= {a, b, c, d, e}, C
6
= {g, f}, C
8
= {h}.

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.
.

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

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

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

.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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


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

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

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

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

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

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

.
.
.
.

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

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

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

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

.
.
.
.
.

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.

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

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

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

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

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

.
.



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

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

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

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

.
.

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

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

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

.
.



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

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

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

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

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

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

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

.
.

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

.
.
a

b
c
d
e
f
g
h
•
•
•
•
•
•
•
•
H`ınh 1.16:
Ch´ung ta su
.
˙’
du
.
ng thuˆa
.
t ng˜u
.
d¯ˆo
`
thi
.
thu go

.
n d¯ˆe
˙’
biˆe
˙’
u diˆe
˜
n d¯ˆo
`
thi
.
G qua quan hˆe
.
liˆen
thˆong ma
.
nh G
r
:= G/R. Do d¯´o c´ac d¯ı
˙’
nh cu
˙’
a G
r
l`a c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh cu
˙’

a G
v`a tˆo
`
n ta
.
i cung gi˜u
.
a hai d¯ı
˙’
nh C
i
v`a C
j
nˆe
´
u v`a chı
˙’
nˆe
´
u tˆo
`
n ta
.
i ´ıt nhˆa
´
t mˆo
.
t cung gi˜u
.
a mˆo

.
t
d¯ı
˙’
nh cu
˙’
a C
i
v`a C
j
trong G. Hiˆe
˙’
n nhiˆen d¯ˆo
`
thi
.
G
r
khˆong c´o ma
.
ch. H`ınh 1.17 l`a d¯ˆo
`
thi
.
thu
go
.
n cu
˙’
a d¯ˆo

`
thi
.
c´o hu
.
´o
.
ng trong H`ınh 1.16. Nghiˆen c´u
.
u c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh v`a
t`ım d¯ˆo
`
thi
.
thu go
.
n l`a nh˜u
.
ng b`ai to´an thu
.
.
c tiˆe
˜
n quan tro
.
ng; chˇa

˙’
ng ha
.
n trong mˆo
´
i liˆen hˆe
.
v´o
.
i
x´ıch Markov, trong phˆan t´ıch cˆa
´
u tr´uc cu
˙’
a mˆo
.
t hˆe
.
thˆo
´
ng (xem [30]). Phˆa
`
n tiˆe
´
p theo ch´ung
ta s˜e d¯ˆe
˙’
cˆa
.
p thˆem vˆe

`
vˆa
´
n d¯ˆe
`
n`ay.
32

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

.
.
.
.
.

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

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

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

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

.
.
.
.

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

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

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

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

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

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

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

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

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

.

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C

1
C
8
C
6
• •
•
H`ınh 1.17:
1.4 Pha
.
m vi v`a liˆen thˆong ma
.
nh
Ta biˆe
´
t rˇa
`
ng hˆe
.
thˆo
´
ng truyˆe
`
n thˆong cu
˙’
a mˆo
.
t tˆo
˙’
ch´u

.
c c´o thˆe
˙’
xem nhu
.
mˆo
.
t d¯ˆo
`
thi
.
trong d¯´o
mˆo
˜
i ngu
.
`o
.
i tu
.
o
.
ng ´u
.
ng mˆo
.
t d¯ı
˙’
nh v`a c´ac kˆenh truyˆe
`

n thˆong tu
.
o
.
ng ´u
.
ng c´ac cung. Cˆau ho
˙’
i
d¯ˇa
.
t ra l`a trong hˆe
.
thˆo
´
ng n`ay, thˆong tin t`u
.
v
i
c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c v
j

khˆong? T´u
.
c l`a c´o tˆo
`
n ta
.
i
d¯u
.
`o
.
ng d¯i t`u
.
v
i
d¯ˆe
´
n v
j
? Nˆe
´
u d¯u
.
`o
.
ng d¯i d¯´o tˆo
`
n ta
.
i ta n´oi v

j
thuˆo
.
c pha
.
m vi cu
˙’
a v
i
. Ch´ung ta
c˜ung quan tˆam d¯ˆe
´
n c´o d¯u
.
`o
.
ng d¯i t`u
.
v
i
d¯ˆe
´
n v
j
v´o
.
i sˆo
´
cung ha
.

n chˆe
´
khˆong? Mu
.
c d¯´ıch cu
˙’
a
phˆa
`
n n`ay l`a tha
˙’
o luˆa
.
n mˆo
.
t v`ai kh´ai niˆe
.
m co
.
ba
˙’
n liˆen quan d¯ˆe
´
n c´ac t´ınh chˆa
´
t pha
.
m vi v`a
liˆen thˆong ma
.

nh cu
˙’
a c´ac d¯ˆo
`
thi
.
v`a gi´o
.
i thiˆe
.
u mˆo
.
t sˆo
´
thuˆa
.
t to´an co
.
so
.
˙’
.
Theo thuˆa
.
t ng˜u
.
cu
˙’
a d¯ˆo
`

thi
.
biˆe
˜
u diˆe
˜
n cho mˆo
.
t tˆo
˙’
ch´u
.
c, phˆa
`
n n`ay kha
˙’
o s´at mˆo
.
t sˆo
´
cˆau
ho
˙’
i:
1. Sˆo
´
ngu
.
`o
.

i ´ıt nhˆa
´
t m`a mˆo
˜
i ngu
.
`o
.
i trong tˆo
˙’
ch´u
.
c c´o thˆe
˙’
liˆen la
.
c d¯u
.
o
.
.
c bˇa
`
ng bao nhiˆeu?
2. Sˆo
´
ngu
.
`o
.

i nhiˆe
`
u nhˆa
´
t c´o thˆe
˙’
liˆen la
.
c d¯u
.
o
.
.
c v´o
.
i nhau bˇa
`
ng bao nhiˆeu?
3. Hai b`ai to´an trˆen c´o quan hˆe
.
g`ı v´o
.
i nhau?
1.4.1 Ma trˆa
.
n pha
.
m vi
Ma trˆa
.

n pha
.
m vi R = (r
ij
) d¯i
.
nh ngh˜ıa nhu
.
sau:
r
ij
:=

1 nˆe
´
u tˆo
`
n ta
.
i d¯u
.
`o
.
ng d¯i t`u
.
d¯ı
˙’
nh v
i
d¯ˆe

´
n d¯ı
˙’
nh v
j
,
0 nˆe
´
u ngu
.
o
.
.
c la
.
i.
Tˆa
.
p R(v
i
) c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
G c´o thˆe
˙’

d¯ˆe
´
n d¯u
.
o
.
.
c t`u
.
d¯ı
˙’
nh v
i
gˆo
`
m c´ac d¯ı
˙’
nh v
j
sao cho
phˆa
`
n tu
.
˙’
r
ij
bˇa
`
ng 1. Theo d¯i

.
nh ngh˜ıa, tˆa
´
t ca
˙’
c´ac phˆa
`
n tu
.
˙’
trˆen d¯u
.
`o
.
ng ch´eo cu
˙’
a ma trˆa
.
n pha
.
m
vi bˇa
`
ng 1.
33
Do Γ(v
i
) l`a tˆa
.
p c´ac d¯ı

˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c t`u
.
v
i
theo mˆo
.
t d¯u
.
`o
.
ng d¯i c´o d¯ˆo
.
d`ai 1 nˆen
tˆa
.
p Γ(Γ(v
i
)) = Γ
2
(v

i
) gˆo
`
m nh˜u
.
ng d¯ı
˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c t`u
.
v
i
theo mˆo
.
t d¯u
.
`o
.
ng d¯i c´o d¯ˆo
.
d`ai
2. Tu

.
o
.
ng tu
.
.
, Γ
p
(v
i
) l`a tˆa
.
p nh˜u
.
ng d¯ı
˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c t`u
.
v
i
theo mˆo

.
t d¯u
.
`o
.
ng d¯i c´o d¯ˆo
.
d`ai
p. Do vˆa
.
y, tˆa
.
p c´ac d¯ı
˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c t`u
.
v
i
l`a
R(v
i

) = {v
i
} ∪ Γ
1
(v
i
) ∪ Γ
2
(v
i
) ∪ · · · .
Nhu
.
ng do d¯ˆo
`
thi
.
d¯u
.
o
.
.
c x´et l`a h˜u
.
u ha
.
n v`a mo
.
i d¯u
.

`o
.
ng d¯i d¯ˆe
`
u ch´u
.
a mˆo
.
t d¯u
.
`o
.
ng d¯i con so
.
cˆa
´
p
trong d¯´o, nˆen tˆo
`
n ta
.
i p sao cho
R(v
i
) = {v
i
} ∪ Γ
1
(v
i

) ∪ Γ
2
(v
i
) ∪ · · · ∪ Γ
p
(v
i
). (1.1)
Suy ra tˆa
.
p pha
.
m vi R(v
i
) c´o thˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c t`u
.
Phu
.
o
.

ng tr`ınh (1.1) bˇa
`
ng c´ach thu
.
.
c hiˆe
.
n c´ac
ph´ep to´an ho
.
.
p t`u
.
tr´ai sang pha
˙’
i cho d¯ˆe
´
n khi tˆa
.
p hiˆe
.
n h`anh khˆong tˇang k´ıch thu
.
´o
.
c trong lˆa
`
n
lˇa
.

p kˆe
´
tiˆe
´
p. Sˆo
´
c´ac ph´ep to´an ho
.
.
p phu
.
thuˆo
.
c v`ao d¯ˆo
`
thi
.
, mˇa
.
c d`u hiˆe
˙’
n nhiˆen rˇa
`
ng p ≤ n − 1,
trong d¯´o n l`a sˆo
´
d¯ı
˙’
nh cu
˙’

a d¯ˆo
`
thi
.
.
Vˆa
.
y ma trˆa
.
n pha
.
m vi c´o thˆe
˙’
d¯u
.
o
.
.
c xˆay du
.
.
ng nhu
.
sau. T`ım tˆa
.
p R(v
i
) v´o
.
i mˆo

˜
i d¯ı
˙’
nh v
i
theo trˆen. D
-
ˇa
.
t r
ij
= 1 nˆe
´
u v
j
∈ R(v
i
), v`a r
ij
= 0 nˆe
´
u ngu
.
o
.
.
c la
.
i.
Ma trˆa

.
n d¯a
.
t d¯u
.
o
.
.
c Q = (q
ij
) d¯i
.
nh ngh˜ıa nhu
.
sau:
q
ij
:=

1 nˆe
´
u tˆo
`
n ta
.
i d¯u
.
`o
.
ng d¯i t`u

.
d¯ı
˙’
nh v
j
d¯ˆe
´
n d¯ı
˙’
nh v
i
,
0 nˆe
´
u ngu
.
o
.
.
c la
.
i.
Tˆa
.
p Q(v
i
) cu
˙’
a d¯ˆo
`

thi
.
G l`a tˆa
.
p c´ac d¯ı
˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c d¯ı
˙’
nh v
i
. Tu
.
o
.
ng tu
.
.
nhu
.
trˆen
ta c˜ung c´o

Q(v
i
) = {v
i
} ∪ Γ
−1
(v
i
) ∪ Γ
−2
(v
i
) ∪ · · · ∪ Γ
−p
(v
i
), (1.2)
trong d¯´o Γ
−2
(v
i
) = Γ
−1
(Γ
−1
(v
i
)), . . . .
T`u
.

d¯i
.
nh ngh˜ıa, hiˆe
˙’
n nhiˆen c´o Q = R
t
.
V´ı du
.
1.4.1 X´et d¯ˆo
`
thi
.
G trong H`ınh 1.18. Ma trˆa
.
n kˆe
`
cu
˙’
a G l`a
A =














v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
0 1 0 0 1 0 0
v
2
0 1 0 1 0 0 0
v
3
0 0 0 1 0 0 0
v
4
0 0 0 0 1 0 0

v
5
0 0 0 0 1 0 0
v
6
0 0 1 0 0 0 1
v
7
0 0 0 1 0 1 0













.
34
.
.
.
.
.
.

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

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

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

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

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

.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

.

.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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


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

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

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

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

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

.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.

.

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

•
•
•
v
5
v
7
v
6
v
4
v
1
v
2
v
3
H`ınh 1.18:
C´ac tˆa
.
p pha
.
m vi c´o thˆe
˙’
x´ac d¯i
.
nh t`u
.
Phu
.

o
.
ng tr`ınh (1.1) nhu
.
sau
R(v
1
) = {v
1
} ∪ {v
2
, v
5
} ∪ {v
2
, v
4
, v
5
} ∪ {v
2
, v
4
, v
5
}
= {v
1
, v
2

, v
4
, v
5
},
R(v
2
) = {v
2
} ∪ {v
2
, v
4
} ∪ {v
2
, v
4
, v
5
} ∪ {v
2
, v
4
, v
5
}
= {v
2
, v
4

, v
5
},
R(v
3
) = {v
3
} ∪ {v
4
} ∪ {v
5
} ∪ {v
5
}
= {v
3
, v
4
, v
5
},
R(v
4
) = {v
4
} ∪ {v
5
} ∪ {v
5
}

= {v
4
, v
5
},
R(v
5
) = {v
5
} ∪ {v
5
}
= {v
5
},
R(v
6
) = {v
6
} ∪ {v
3
, v
7
} ∪ {v
4
, v
6
} ∪ {v
3
, v

5
, v
7
} ∪ {v
4
, v
5
, v
6
}
= {v
3
, v
4
, v
5
, v
6
, v
7
},
R(v
7
) = {v
7
} ∪ {v
4
, v
6
} ∪ {v

3
, v
5
, v
7
} ∪ {v
4
, v
5
, v
6
}
= {v
3
, v
4
, v
5
, v
6
, v
7
}.
35
Do d¯´o ma trˆa
.
n pha
.
m vi c´o da
.

ng
R =













v
1
v
2
v
3
v
4
v
5
v
6
v
7
v

1
1 1 0 1 1 0 0
v
2
0 1 0 1 1 0 0
v
3
0 0 1 1 1 0 0
v
4
0 0 0 1 1 0 0
v
5
0 0 0 0 1 0 0
v
6
0 0 1 1 1 1 1
v
7
0 0 1 1 1 1 1














.
Cˆa
`
n ch´u ´y rˇa
`
ng, do R v`a Q l`a c´ac ma trˆa
.
n Boole, mˆo
˜
i h`ang cu
˙’
a ch´ung c´o thˆe
˙’
lu
.
u da
.
ng
mˆo
.
t hoˇa
.
c ho
.
n mˆo
.
t t`u

.
(word) . Viˆe
.
c t`ım c´ac ma trˆa
.
n n`ay l`a mˆo
.
t t´ınh to´an d¯o
.
n gia
˙’
n do chı
˙’
du
.
.
a v`ao c´ac ph´ep to´an logic.
T`u
.
d¯i
.
nh ngh˜ıa, R(v
i
) ∩ Q(v
j
) l`a tˆa
.
p c´ac d¯ı
˙’
nh v

k
m`a c´o ´ıt nhˆa
´
t mˆo
.
t d¯u
.
`o
.
ng d¯i t`u
.
v
i
d¯ˆe
´
n
v
j
qua d¯ı
˙’
nh v
k
. C´ac d¯ı
˙’
nh n`ay go
.
i l`a cˆo
´
t yˆe
´

u. Tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh v
k
/∈ R(v
i
) ∩ Q(v
j
) go
.
i l`a khˆong
cˆo
´
t yˆe
´
u hay du
.
th`u
.
a do bo
˙’
ch´ung d¯i khˆong a
˙’
nh hu
.
o

.
˙’
ng d¯ˆe
´
n c´ac d¯u
.
`o
.
ng d¯i t`u
.
v
i
d¯ˆe
´
n v
j
.
C´ac ma trˆa
.
n R v`a Q d¯i
.
nh ngh˜ıa trˆen l`a tuyˆe
.
t d¯ˆo
´
i theo ngh˜ıa sˆo
´
c´ac cung trˆen d¯u
.
`o

.
ng
d¯i t`u
.
v
i
d¯ˆe
´
n v
j
khˆong bi
.
ha
.
n chˆe
´
. Mˇa
.
t kh´ac ta c˜ung c´o thˆe
˙’
d¯i
.
nh ngh˜ıa tu
.
o
.
ng tu
.
.
c´ac ma

trˆa
.
n n`ay v´o
.
i sˆo
´
cung trˆen d¯u
.
`o
.
ng d¯i khˆong vu
.
o
.
.
t qu´a mˆo
.
t sˆo
´
cho tru
.
´o
.
c. V´o
.
i mo
.
˙’
rˆo
.

ng n`ay ta
c˜ung c´o thˆe
˙’
t´ınh d¯u
.
o
.
.
c c´ac ma trˆa
.
n ha
.
n chˆe
´
theo lu
.
o
.
.
c d¯ˆo
`
trˆen.
D
-
ˆo
`
thi
.
d¯u
.

o
.
.
c go
.
i l`a bˇa
´
c cˆa
`
u nˆe
´
u tˆo
`
n ta
.
i c´ac cung (v
i
, v
j
) v`a (v
j
, v
k
) th`ı c˜ung tˆo
`
n ta
.
i cung
(v
i

, v
k
). Bao d¯´ong bˇa
´
c cˆa
`
u cu
˙’
a d¯ˆo
`
thi
.
G = (V, E) l`a d¯ˆo
`
thi
.
G
tc
= (V, E ∪ E

) trong d¯´o E

l`a
c´ac cung d¯u
.
o
.
.
c thˆem v`ao ´ıt nhˆa
´

t d¯ˆe
˙’
d¯ˆo
`
thi
.
G
tc
c´o t´ınh bˇa
´
c cˆa
`
u. Dˆe
˜
d`ang ch´u
.
ng minh rˇa
`
ng
ma trˆa
.
n kˆe
`
cu
˙’
a d¯ˆo
`
thi
.
G

tc
ch´ınh l`a ma trˆa
.
n pha
.
m vi R v`a bˇa
`
ng
A + A
2
+ · · · + A
p
, (p ≤ n − 1),
trong d¯´o A l`a ma trˆa
.
n kˆe
`
cu
˙’
a G. (Ta
.
i sao?)
1.4.2 T`ım c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh
Th`anh phˆa
`
n liˆen thˆong ma

.
nh d¯i
.
nh ngh˜ıa trong phˆa
`
n tru
.
´o
.
c tru
.
´o
.
c l`a d¯ˆo
`
thi
.
con liˆen thˆong
ma
.
nh l´o
.
n nhˆa
´
t trong G. V`ı v´o
.
i d¯ˆo
`
thi
.

liˆen thˆong ma
.
nh, v´o
.
i mo
.
i cˇa
.
p d¯ı
˙’
nh v
i
, v
j
, luˆon luˆon
tˆo
`
n ta
.
i mˆo
.
t d¯u
.
`o
.
ng d¯i t`u
.
d¯ı
˙’
nh v

i
d¯ˆe
´
n d¯ı
˙’
nh v
j
v`a ngu
.
o
.
.
c la
.
i, nˆen tˆo
`
n ta
.
i duy nhˆa
´
t mˆo
.
t th`anh
phˆa
`
n liˆen thˆong ma
.
nh ch´u
.
a mˆo

.
t d¯ı
˙’
nh cho tru
.
´o
.
c v`a v
i
s˜e xuˆa
´
t hiˆe
.
n trong tˆa
.
p c´ac d¯ı
˙’
nh cu
˙’
a
mˆo
.
t v`a chı
˙’
mˆo
.
t th`anh phˆa
`
n liˆen thˆong ma
.

nh. Khˇa
˙’
ng d¯i
.
nh n`ay l`a hiˆe
˙’
n nhiˆen (ta
.
i sao?).
36
Nˆe
´
u d¯ı
˙’
nh v
i
d¯u
.
o
.
.
c coi v`u
.
a l`a xuˆa
´
t ph´at v`u
.
a l`a kˆe
´
t th´uc th`ı tˆa

.
p c´ac d¯ı
˙’
nh cˆo
´
t yˆe
´
u tu
.
o
.
ng
´u
.
ng v´o
.
i hai d¯ı
˙’
nh tr`ung nhau n`ay (t´u
.
c l`a tˆa
.
p c´ac d¯ı
˙’
nh thuˆo
.
c ma
.
ch n`ao d¯´o ch´u
.

a v
i
) x´ac d¯i
.
nh
bo
.
˙’
i R(v
i
) ∩ Q(v
i
). V`ı tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh cˆo
´
t yˆe
´
u n`ay c´o thˆe
˙’
d¯ˆe
´
n t`u
.
v
i

v`a ngu
.
o
.
.
c la
.
i nˆen ch´ung
c˜ung c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c c´ac d¯ı
˙’
nh kh´ac trong tˆa
.
p n`ay v`a ngu
.
o
.
.
c la
.
i. Ho
.

n n˜u
.
a, dˆe
˜
thˆa
´
y rˇa
`
ng
tˆa
.
p R(v
i
) ∩ Q(v
i
) x´ac d¯i
.
nh c´ac d¯ı
˙’
nh cu
˙’
a th`anh phˆa
`
n liˆen thˆong ma
.
nh duy nhˆa
´
t tu
.
o

.
ng ´u
.
ng
v´o
.
i d¯ı
˙’
nh v
i
.
Nˆe
´
u ta loa
.
i c´ac d¯ı
˙’
nh n`ay kho
˙’
i d¯ˆo
`
thi
.
G = (V, Γ) th`ı c´o thˆe
˙’
´ap du
.
ng t`ım th`anh phˆa
`
n

liˆen thˆong ma
.
nh trˆen d¯ˆo
`
thi
.
con nhˆa
.
n d¯u
.
o
.
.
c G

v´o
.
i tˆa
.
p d¯ı
˙’
nh V \ (R(v
i
) ∩ Q(v
i
)). Qu´a tr`ınh
n`ay lˇa
.
p la
.

i cho d¯ˆe
´
n khi tˆa
´
t ca
˙’
c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh d¯u
.
o
.
.
c t`ım. Kˆe
´
t th´uc ta c´o d¯ˆo
`
thi
.
G d¯u
.
o
.
.
c phˆan hoa
.
ch th`anh c´ac th`anh phˆa
`

n liˆen thˆong ma
.
nh.
V´ı du
.
1.4.2 X´et d¯ˆo
`
thi
.
trong H`ınh 1.19. Ch´ung ta h˜ay t`ım th`anh phˆa
`
n liˆen thˆong ma
.
nh
ch´u
.
a d¯ı
˙’
nh v
1
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

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

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

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

.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
1
v
2
v
3

v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
12
v
13
.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

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

.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

.
.

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

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

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

.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.

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

.
.
.

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

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

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

.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

.
.

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

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

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

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

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

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

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

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

.
.
.

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

•
•
•
• •
•
•
H`ınh 1.19: D
-
ˆo
`
thi
.
G.
T`u
.
c´ac phu
.
o
.
ng tr`ınh (1.1) v`a (1.2) ta c´o
R(v
1
) = {v
1
, v
2
, v
4
, v
5

, v
6
, v
7
, v
8
, v
9
, v
10
}
v`a
Q(v
1
) = {v
1
, v
2
, v
3
, v
5
, v
6
}.
Do d¯´o th`anh phˆa
`
n liˆen thˆong ma
.
nh ch´u

.
a d¯ı
˙’
nh v
1
l`a d¯ˆo
`
thi
.
con
R(v
1
) ∩ Q(v
1
) = {v
1
, v
2
, v
5
, v
6
}.
37
Tu
.
o
.
ng tu
.

.
, th`anh phˆa
`
n liˆen thˆong ma
.
nh ch´u
.
a d¯ı
˙’
nh v
8
l`a d¯ˆo
`
thi
.
con {v
8
, v
10
}, ch´u
.
a
d¯ı
˙’
nh v
7
l`a d¯ˆo
`
thi
.

con {v
4
, v
7
, v
9
}, ch´u
.
a d¯ı
˙’
nh v
11
l`a d¯ˆo
`
thi
.
con {v
11
, v
12
, v
13
}, v`a ch´u
.
a d¯ı
˙’
nh
v
3
l`a d¯ˆo

`
thi
.
con {v
3
}. D
-
ˆo
`
thi
.
thu go
.
n G
r
d¯u
.
o
.
.
c cho trong H`ınh 1.20.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
v
∗
1
= {v
1
, v
2
, v
5
, v
6
} v
∗
2
= {v
8
, v

10
}
v
∗
3
= {v
4
, v
7
, v
9
}v
∗
5
= {v
3
}
v
∗
4
= {v
11
, v
12
, v
13
}
•
•
•

•
•

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.

.
.
.

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

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

.
.
.
.
.
.
.
.
.
.
H`ınh 1.20: D
-
ˆo
`
thi
.
thu go
.
n G
r
.
C´ac ph´ep to´an d¯u
.
o
.
.
c miˆeu ta
˙’
trˆen d¯ˆe
˙’

t`ım c´ac th`anh phˆa
`
n liˆen thˆong ma
.
nh cu
˙’
a mˆo
.
t d¯ˆo
`
thi
.
c˜ung c´o thˆe
˙’
su
.
˙’
du
.
ng tru
.
.
c tiˆe
´
p d¯ˆo
´
i v´o
.
i c´ac ma trˆa
.

n R v`a Q d¯i
.
nh ngh˜ıa phˆa
`
n tru
.
´o
.
c. Do
d¯´o nˆe
´
u ta k´y hiˆe
.
u R ⊗ Q c´o ngh˜ıa l`a ma trˆa
.
n nhˆa
.
n d¯u
.
o
.
.
c t`u
.
R v`a Q bˇa
`
ng c´ach nhˆan c´ac
phˆa
`
n tu

.
˙’
tu
.
o
.
ng ´u
.
ng th`ı phˆa
`
n tu
.
˙’
(R ⊗ Q )
ij
= r
ij
q
ij
bˇa
`
ng 1 nˆe
´
u tˆo
`
n ta
.
i d¯u
.
`o

.
ng d¯i t`u
.
v
i
d¯ˆe
´
n v
j
v`a ngu
.
o
.
.
c la
.
i, v`a bˇa
`
ng 0 trong tru
.
`o
.
ng ho
.
.
p ngu
.
o
.
.

c la
.
i. Do d¯´o hai d¯ı
˙’
nh thuˆo
.
c c`ung mˆo
.
t th`anh
phˆa
`
n liˆen thˆong ma
.
nh nˆe
´
u v`a chı
˙’
nˆe
´
u c´ac h`ang (hoˇa
.
c cˆo
.
t) tu
.
o
.
ng ´u
.
ng bˇa

`
ng nhau. C´ac d¯ı
˙’
nh
m`a h`ang tu
.
o
.
ng ´u
.
ng ch´u
.
a mˆo
.
t phˆa
`
n tu
.
˙’
1 o
.
˙’
cˆo
.
t v
j
ta
.
o th`anh tˆa
.

p d¯ı
˙’
nh cu
˙’
a th`anh phˆa
`
n liˆen
thˆong ma
.
nh ch´u
.
a v
i
. Hiˆe
˙’
n nhiˆen rˇa
`
ng c´o thˆe
˙’
biˆe
´
n d¯ˆo
˙’
i ma trˆa
.
n R ⊗ Q bˇa
`
ng ph´ep ho´an vi
.
c´ac h`ang v`a c´ac cˆo

.
t sao cho ma trˆa
.
n thu d¯u
.
o
.
.
c c´o da
.
ng khˆo
´
i ch´eo; mˆo
˜
i ma trˆa
.
n con ch´eo
tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t th`anh phˆa
`
n liˆen thˆong ma

.
nh cu
˙’
a G v`a c´o c´ac phˆa
`
n tu
.
˙’
bˇa
`
ng 1, c´ac phˆa
`
n
38
tu
.
˙’
kh´ac bˇa
`
ng 0. V´o
.
i v´ı du
.
trˆen, ma trˆa
.
n R ⊗ Q d¯u
.
o
.
.

c sˇa
´
p x´e6p la
.
i c´o da
.
ng
R ⊗ Q =




























v
1
v
2
v
5
v
6
v
8
v
10
v
4
v
7
v
9
v
11
v
12
v
13
v

3
v
1
1 1 1 1
v
2
1 1 1 1
v
5
1 1 1 1
v
6
1 1 1 1
v
8
1 1
v
10
1 1
v
4
1 1 1
v
7
1 1 1
v
9
1 1 1
v
11

1 1 1
v
12
1 1 1
v
13
1 1 1
v
3
1




























.
1.4.3 Co
.
so
.
˙’
Tˆa
.
p B c´ac d¯ı
˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c mo
.
i d¯ı
˙’

nh cu
˙’
a d¯ˆo
`
thi
.
v`a nho
˙’
nhˆa
´
t theo ngh˜ıa khˆong c´o tˆa
.
p
con thu
.
.
c su
.
.
n`ao cu
˙’
a n´o c´o t´ınh chˆa
´
t n`ay go
.
i l`a co
.
so
.
˙’

. Do d¯´o nˆe
´
u ta viˆe
´
t R(B) l`a tˆa
.
p pha
.
m
vi cu
˙’
a B-t´u
.
c l`a
R(B) = ∪
v
i
∈B
R(v
i
)
th`ı B l`a co
.
so
.
˙’
nˆe
´
u v`a chı
˙’

nˆe
´
u
1. B(V ) = V ; v`a
2. v´o
.
i mo
.
i tˆa
.
p con S ⊂ B th`ı R(S) = V.
D
-
iˆe
`
u kiˆe
.
n th´u
.
hai tu
.
o
.
ng d¯u
.
o
.
ng v´o
.
i d¯iˆe

`
u kiˆe
.
n v
j
/∈ R(v
i
) v´o
.
i hai d¯ı
˙’
nh phˆan biˆe
.
t v
i
, v
j
∈ B;
t´u
.
c l`a mˆo
.
t d¯ı
˙’
nh thuˆo
.
c B khˆong thˆe
˙’
d¯ˆe
´

n d¯u
.
o
.
.
c t`u
.
mˆo
.
t d¯ı
˙’
nh kh´ac trong B. D
-
iˆe
`
u n`ay c´o thˆe
˙’
ch´u
.
ng minh nhu
.
sau:
Do v´o
.
i hai tˆa
.
p con H v`a H

⊂ H ta c´o R(H


) ⊂ R(H) nˆen d¯iˆe
`
u kiˆe
.
n R(S) = V v´o
.
i mo
.
i
S ⊂ B tu
.
o
.
ng d¯u
.
o
.
ng v´o
.
i R(B\{v
j
}) = V v´o
.
i mo
.
i v
j
∈ B. N´oi c´ach kh´ac, R(v
j
) ⊂ R(B\{v

j
}).
Nhu
.
ng d¯iˆe
`
u kiˆe
.
n n`ay thoa
˙’
m˜an nˆe
´
u v`a chı
˙’
nˆe
´
u v
j
/∈ R(B \ {v
j
}), t´u
.
c l`a v
j
/∈ R(v
i
) v´o
.
i mo
.

i
v
i
, v
j
∈ B.
Vˆa
.
y, co
.
so
.
˙’
l`a mˆo
.
t tˆa
.
p B c´ac d¯ı
˙’
nh thoa
˙’
m˜an hai d¯iˆe
`
u kiˆe
.
n sau:
39
1. tˆa
´
t ca

˙’
c´ac d¯ı
˙’
nh cu
˙’
a G c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o
.
.
c t`u
.
d¯ı
˙’
nh n`ao d¯´o cu
˙’
a B; v`a
2. khˆong d¯ı
˙’
nh n`ao trong B c´o thˆe
˙’
d¯ˆe
´
n d¯u
.
o

.
.
c t`u
.
mˆo
.
t d¯ı
˙’
nh thuˆo
.
c B.
T`u
.
hai d¯iˆe
`
u kiˆe
.
n n`ay ta suy ra
Mˆe
.
nh d¯ˆe
`
1.4.3 (i) Khˆong tˆo
`
n ta
.
i hai d¯ı
˙’
nh trong co
.

so
.
˙’
B sao cho ch´ung thuˆo
.
c c`ung mˆo
.
t
th`anh phˆa
`
n liˆen thˆong ma
.
nh cu
˙’
a G.
(b) D
-
ˆo
`
thi
.
khˆong ma
.
ch c´o duy nhˆa
´
t mˆo
.
t co
.
so

.
˙’
gˆo
`
m tˆa
.
p c´ac d¯ı
˙’
nh c´o bˆa
.
c trong bˇa
`
ng khˆong.
Ch´u
.
ng minh. Suy tru
.
.
c tiˆe
´
p t`u
.
d¯i
.
nh ngh˜ıa. 
Theo Mˆe
.
nh d¯ˆe
`
trˆen v`a do d¯ˆo

`
thi
.
thu go
.
n G
r
cu
˙’
a d¯ˆo
`
thi
.
G khˆong c´o ma
.
nh nˆen tˆa
.
p co
.
so
.
˙’
B
r
cu
˙’
a G
r
l`a tˆa
.

p c´ac d¯ı
˙’
nh c´o bˆa
.
c trong bˇa
`
ng khˆong. C´ac tˆa
.
p co
.
so
.
˙’
cu
˙’
a G c´o thˆe
˙’
x´ac d¯i
.
nh
du
.
.
a v`ao B
r
. Cu
.
thˆe
˙’
l`a nˆe

´
u B
r
= {S
1
, S
2
, . . . , S
k
}, trong d¯´o k l`a sˆo
´
c´ac tˆa
.
p d¯ı
˙’
nh S
j
trong co
.
so
.
˙’
B
r
cu
˙’
a G
r
, th`ı B l`a tˆa
.

p da
.
ng {v
i
1
, v
i
2
, . . . , v
i
k
} v´o
.
i v
i
j
∈ S
j
, j = 1, 2, . . . , k.
V´ı du
.
1.4.4 V´o
.
i d¯ˆo
`
thi
.
trong H`ınh 1.19, d¯ˆo
`
thi

.
thu go
.
n trong H`ınh 1.20. Co
.
so
.
˙’
cu
˙’
a d¯ˆo
`
thi
.
n`ay l`a {v
∗
4
, v
∗
5
} do v
∗
4
v`a v
∗
5
l`a hai d¯ı
˙’
nh duy nhˆa
´

t cu
˙’
a G c´o bˆa
.
c trong bˇa
`
ng khˆong. Suy ra
c´ac tˆa
.
p co
.
so
.
˙’
cu
˙’
a G l`a {v
3
, v
11
}, {v
3
, v
12
} v`a {v
3
, v
13
.}
D

-
ˆo
´
i ngˆa
˜
u v´o
.
i kh´ai niˆe
.
m co
.
so
.
˙’
c´o thˆe
˙’
d¯i
.
nh ngh˜ıa theo thuˆa
.
t ng˜u
.
cu
˙’
a c´ac tˆa
.
p ho
.
.
p Q(v

i
)
nhu
.
sau.
D
-
ˆo
´
i co
.
so
.
˙’
l`a tˆa
.
p
¯
B c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
G = (V, Γ) thoa
˙’
m˜an
Q(

¯
B) =

v
i
∈B
Q(v
i
) = V,
∀S ⊂
¯
B, Q(S) = V.
T´u
.
c l`a
¯
B l`a tˆa
.
p nho
˙’
nhˆa
´
t c´ac d¯ı
˙’
nh c´o thˆe
˙’
d¯ˆe
´
n d¯u
.

o
.
.
c t`u
.
c´ac d¯ı
˙’
nh kh´ac. C´ac t´ınh chˆa
´
t cu
˙’
a
¯
B
tu
.
o
.
ng tu
.
.
v´o
.
i cu
˙’
a B trong d¯´o c´ac kh´ai niˆe
.
m vˆe
`
hu

.
´o
.
ng d¯u
.
o
.
.
c thay bˇa
`
ng ba
˙’
n sao ngu
.
o
.
.
c la
.
i.
Do vˆa
.
y, d¯ˆo
´
i co
.
so
.
˙’
cu

˙’
a d¯ˆo
`
thi
.
thu go
.
n G
r
l`a tˆa
.
p c´ac d¯ı
˙’
nh cu
˙’
a G
r
c´o bˆa
.
c ngo`ai bˇa
`
ng
khˆong, v`a t`u
.
d¯´o ta c´o thˆe
˙’
nhˆa
.
n d¯u
.

o
.
.
c d¯ˆo
´
i co
.
so
.
˙’
cu
˙’
a G tu
.
o
.
ng tu
.
.
nhu
.
d¯˜a thu
.
.
c hiˆe
.
n o
.
˙’
trˆen.

Trong v´ı du
.
cu
˙’
a d¯ˆo
`
thi
.
G trong H`ınh 1.19, d¯ˆo
`
thi
.
thu go
.
n G
r
chı
˙’
ch´u
.
a mˆo
.
t d¯ı
˙’
nh v
∗
3
c´o bˆa
.
c ngo`ai bˇa

`
ng khˆong. Do d¯´o d¯ˆo
´
i co
.
so
.
˙’
cu
˙’
a G
r
l`a {v
∗
3
} v`a bo
.
˙’
i vˆa
.
y d¯ˆo
´
i co
.
so
.
˙’
cu
˙’
a G l`a

{v
4
}, {v
7
} v`a {v
9
}.
40
´
Ap du
.
ng trong cˆa
´
u tr´uc tˆo
˙’
ch´u
.
c
Nˆe
´
u d¯ˆo
`
thi
.
biˆe
˙’
u diˆe
˜
n cˆa
´

u tr´uc a
˙’
nh hu
.
o
.
˙’
ng cu
˙’
a mˆo
.
t tˆo
˙’
ch´u
.
c th`ı c´ac phˆa
`
n tu
.
˙’
cu
˙’
a mˆo
.
t th`anh
phˆa
`
n liˆen thˆong ma
.
nh cu

˙’
a G c´o a
˙’
nh hu
.
o
.
˙’
ng v`a ch´u
.
c nˇang ngang nhau. Mˆo
.
t co
.
so
.
˙’
cu
˙’
a G c´o
thˆe
˙’
hiˆe
˙’
u l`a mˆo
.
t “liˆen minh” c´o sˆo
´
ngu
.

`o
.
i ´ıt nhˆa
´
t nhu
.
ng l˜anh d¯a
.
o mo
.
i c´a nhˆan trong tˆo
˙’
ch´u
.
c.
Trˆen tˆa
.
p c´ac d¯ı
˙’
nh biˆe
˙’
u diˆe
˜
n c´ac th`anh viˆen cu
˙’
a c`ung tˆo
˙’
ch´u
.
c, ta x´et d¯ˆo

`
thi
.
G

d¯u
.
o
.
.
c
xˆay du
.
.
ng d¯ˆe
˙’
biˆe
˙’
u diˆe
˜
n c´ac kˆenh truyˆe
`
n thˆong sao cho tˆo
`
n ta
.
i cung (v
i
, v
j

) nˆe
´
u v
i
c´o thˆe
˙’
giao
tiˆe
´
p v´o
.
i v
j
. D
-
ˆo
`
thi
.
G

d˜ı nhiˆen c´o liˆen quan v´o
.
i G. Sˆo
´
ngu
.
`o
.
i ´ıt nhˆa

´
t m`a biˆe
´
t hoˇa
.
c c´o thˆe
˙’
nhˆa
.
n tˆa
´
t ca
˙’
c´ac su
.
.
kiˆe
.
n vˆe
`
tˆo
˙’
ch´u
.
c ta
.
o th`anh mˆo
.
t d¯ˆo
´

i co
.
so
.
˙’
cu
˙’
a G

. Ta c´o thˆe
˙’
n´oi rˇa
`
ng mˆo
.
t
liˆen minh hiˆe
.
u qua
˙’
d¯ˆe
˙’
l˜anh d¯a
.
o tˆo
˙’
ch´u
.
c l`a tˆa
.

p H nh˜u
.
ng ngu
.
`o
.
i thoa
˙’
m˜an:
H = B(G) ∪
¯
B(G

),
trong d¯´o B(G) v`a
¯
B(G

) l`a mˆo
.
t trong c´ac co
.
so
.
˙’
v`a c´ac d¯ˆo
´
i co
.
so

.
˙’
cu
˙’
a G v`a G

tu
.
o
.
ng ´u
.
ng
d¯u
.
o
.
.
c cho
.
n sao cho #H nho
˙’
nhˆa
´
t.
Kˆe
´
tiˆe
´
p x´et co

.
so
.
˙’
lu˜y th`u
.
a l`a tˆa
.
p c´ac d¯ı
˙’
nh B
p
⊂ V sao cho
R(B
p
) = V, Q(B
p
) = B
p
,
R(S) = V, ∀S ⊂ B
p
.
D
-
iˆe
`
u kiˆe
.
n th´u

.
hai ngh˜ıa l`a chı
˙’
nh˜u
.
ng ngu
.
`o
.
i bˆen trong B
p
m´o
.
i c´o thˆe
˙’
c´o a
˙’
nh hu
.
o
.
˙’
ng d¯ˆe
´
n
ngu
.
`o
.
i kh´ac c˜ung trong B

p
v`a c´o thˆe
˙’
thay bˇa
`
ng d¯iˆe
`
u kiˆen tu
.
o
.
ng d¯u
.
o
.
ng: R(V \ B
p
) ∩ B
p
= ∅.
D
-
iˆe
`
u kiˆe
.
n n`ay chı
˙’
ra rˇa
`

ng nˆe
´
u mˆo
.
t d¯ı
˙’
nh trong th`anh phˆa
`
n liˆen thˆong ma
.
nh cu
˙’
a G thuˆo
.
c B
p
th`ı mo
.
i d¯ı
˙’
nh kh´ac trong c`ung th`anh phˆa
`
n liˆen thˆong ma
.
nh n`ay c˜ung thuˆo
.
c B
p
. Do tˆa
.

p co
.
so
.
˙’
cu
˙’
a G
r
l`a tˆa
.
p c´ac d¯ı
˙’
nh c´o bˆa
.
c trong bˇa
`
ng khˆong nˆen tˆa
.
p co
.
so
.
˙’
l˜uy th`u
.
a cu
˙’
a G ch´ınh l`a
B

p
=

S
i
∈B
∗
S
i
.
Chˇa
˙’
ng ha
.
n d¯ˆo
`
thi
.
trong H`ınh 1.19 c´o co
.
so
.
˙’
l˜uy th`u
.
a l`a {v
3
, v
11
, v

12
, v
13
}. Cˆa
`
n ch´u ´y
rˇa
`
ng, nˆe
´
u d¯ˆo
`
thi
.
n`ay tu
.
o
.
ng ´u
.
ng mˆo
.
t tˆo
˙’
ch´u
.
c th`ı v
3
c´o thˆe
˙’

xem l`a ngu
.
`o
.
i l˜anh d¯a
.
o cao nhˆa
´
t
cu
˙’
a c´ac nh´om v
∗
1
, v
∗
2
v`a v
∗
3
.
1.5 D
-
ˇa
˙’
ng cˆa
´
u cu
˙’
a c´ac d¯ˆo

`
thi
.
Ta d¯˜a biˆe
´
t rˇa
`
ng c`ung mˆo
.
t d¯ˆo
`
thi
.
c´o thˆe
˙’
d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bˇa
`
ng nhiˆe
`
u h`ınh v˜e kh´ac nhau. Viˆe
.

c
nhˆa
.
n biˆe
´
t d¯u
.
o
.
.
c trong tru
.
`o
.
ng ho
.
.
p n`ao hai h`ınh v˜e biˆe
˙’
u diˆe
˜
n c`ung mˆo
.
t d¯ˆo
`
thi
.
, trong tru
.
`o

.
ng
ho
.
.
p n`ao biˆe
˙’
u diˆe
˜
n hai d¯ˆo
`
thi
.
kh´ac nhau, l`a mˆo
.
t vˆa
´
n d¯ˆe
`
khˆong d¯o
.
n gia
˙’
n.
41
R˜o r`ang l`a hai h`ınh cho tru
.
´o
.
c biˆe

˙’
u diˆe
˜
n c `ung mˆo
.
t d¯ˆo
`
thi
.
chı
˙’
khi c´ac d¯iˆe
`
u kiˆe
.
n sau d¯ˆay
d¯u
.
o
.
.
c thoa
˙’
m˜an:
1. Sˆo
´
d¯ı
˙’
nh bˇa
`

ng nhau;
2. Sˆo
´
ca
.
nh bˇa
`
ng nhau;
3. Sˆo
´
d¯ı
˙’
nh c`ung bˆa
.
c bˇa
`
ng nhau.
D
-
´o l`a nh˜u
.
ng d¯iˆe
`
u kiˆe
.
n cˆa
`
n: hai h`ınh khˆong thoa
˙’
m˜an mˆo

.
t trong c´ac d¯iˆe
`
u kiˆe
.
n d¯´o th`ı
khˆong biˆe
˙’
u diˆe
˜
n c`ung mˆo
.
t d¯ˆo
`
thi
.
. Nhu
.
ng ch´ung c˜ung khˆong pha
˙’
i l`a d¯iˆe
`
u kiˆe
.
n d¯u
˙’
(h˜ay cho
v´ı du
.
). Hiˆe

˙’
n nhiˆen rˇa
`
ng
D
-
i
.
nh l´y 1.5.1 D
-
iˆe
`
u kiˆe
.
n cˆa
`
n v`a d¯u
˙’
d¯ˆe
˙’
hai h`ınh biˆe
˙’
u diˆe
˜
n c`ung mˆo
.
t d¯ˆo
`
thi
.

l`a tˆo
`
n ta
.
i mˆo
.
t
tu
.
o
.
ng ´u
.
ng mˆo
.
t-mˆo
.
t lˆen gi˜u
.
a c´ac d¯ı
˙’
nh cu
˙’
a hai h`ınh sao cho nˆe
´
u hai d¯ı
˙’
nh cu
˙’
a h`ınh n`ay d¯u

.
o
.
.
c
nˆo
´
i bo
.
˙’
i mˆo
.
t ca
.
nh th`ı hai d¯ı
˙’
nh tu
.
o
.
ng ´u
.
ng cu
˙’
a h`ınh kia c˜ung d¯u
.
o
.
.
c nˆo

´
i v´o
.
i nhau bo
.
˙’
i mˆo
.
t
ca
.
nh v`a ngu
.
o
.
.
c la
.
i.
Viˆe
.
c t`ım mˆo
.
t tiˆeu chuˆa
˙’
n d¯o
.
n gia
˙’
n v`a hiˆe

.
u qua
˙’
d¯ˆe
˙’
ph´at hiˆe
.
n t´ınh d¯ˇa
˙’
ng cˆa
´
u cu
˙’
a c´ac d¯ˆo
`
thi
.
vˆa
˜
n l`a b`ai to´an mo
.
˙’
cu
˙’
a l´y thuyˆe
´
t d¯ˆo
`
thi
.

v`a d¯ang c`on d¯u
.
o
.
.
c tiˆe
´
p tu
.
c nghiˆen c´u
.
u.
1.5.1 1−d¯ˇa
˙’
ng cˆa
´
u
D
-
ˆo
`
thi
.
c´o c´ac d¯iˆe
˙’
m kh´o
.
p gˆo
`
m ´ıt nhˆa

´
t hai d¯ˆo
`
thi
.
con khˆong c´o d¯iˆe
˙’
m kh´o
.
p. Mˆo
˜
i d¯ˆo
`
thi
.
con
liˆen thˆong l´o
.
n nhˆa
´
t khˆong c´o d¯iˆe
˙’
m kh´o
.
p go
.
i l`a khˆo
´
i. D
-

ˆo
`
thi
.
trong H`ınh 1.21 c´o nˇam khˆo
´
i
(v`a ba d¯iˆe
˙’
m kh´o
.
p a, b v`a c). Ch´u ´y rˇa
`
ng d¯ˆo
`
thi
.
liˆen thˆong khˆong c´o d¯iˆe
˙’
m kh´o
.
p chı
˙’
c´o mˆo
.
t
khˆo
´
i.
.

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

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

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

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

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

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

.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.

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

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

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

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

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

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

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

a
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

.
.
.
.
.

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

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

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

.
.
.

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.

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

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

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

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

.
.
.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
•
b

•
c
.
.
.
.
.
.
.
.

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

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

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

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

.
.

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

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

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

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

.
.

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

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

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

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

.
.
.
.
.
.
.

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

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

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

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

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

•
•
•
H`ınh 1.21:
42
So s´anh d¯ˆo
`
thi
.
khˆong liˆen thˆong trong H`ınh 1.22 v`a d¯ˆo
`
thi
.
trong H`ınh 1.21. Hiˆe
˙’
n nhiˆen
hai d¯ˆo

`
thi
.
n`ay khˆong d¯ˇa
˙’
ng cˆa
´
u (ch´ung c´o sˆo
´
d¯ı
˙’
nh kh´ac nhau); nhu
.
ng ch´ung c´o mˆo
´
i liˆen hˆe
.
l`a c´ac khˆo
´
i trong H`ınh 1.21 d¯ˇa
˙’
ng cˆa
´
u v´o
.
i c´ac th`anh phˆa
`
n cu
˙’
a d¯ˆo

`
thi
.
trong H`ınh 1.22. C´ac
d¯ˆo
`
thi
.
n`ay go
.
i l`a 1-d¯ˇa
˙’
ng cˆa
´
u. Ch´ınh x´ac ho
.
n:
D
-
i
.
nh ngh˜ıa 1.5.2 Hai d¯ˆo
`
thi
.
G
1
v`a G
2
go

.
i l`a 1−d¯ˇa
˙’
ng cˆa
´
u nˆe
´
u ch´ung tro
.
˙’
th`anh d¯ˇa
˙’
ng cˆa
´
u
v´o
.
i nhau sau khi ´ap du
.
ng mˆo
.
t sˆo
´
lˆa
`
n ph´ep to´an sau:
Ph´ep to´an 1. “T´ach” mˆo
.
t d¯iˆe
˙’

m kh´o
.
p th`anh hai d¯ı
˙’
nh d¯ˆe
˙’
ta
.
o th`anh hai d¯ˆo
`
thi
.
con
khˆong c´o d¯iˆe
˙’
m kh´o
.
p r`o
.
i nhau.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
•
a
1
x
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
a
2
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
•
•
•
•
b
1
a
3
y

• •
b
2
c
1
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

•
•
•
•
c
2
H`ınh 1.22:
T`u
.
d¯i
.
nh ngh˜ıa suy ra rˇa
`

ng hai d¯ˆo
`
thi
.
khˆong c´o d¯iˆe
˙’
m kh´o
.
p l`a 1-d¯ˇa
˙’
ng cˆa
´
u nˆe
´
u v`a chı
˙’
nˆe
´
u ch´ung d¯ˇa
˙’
ng cˆa
´
u.
D
-
iˆe
`
u g`ı s˜e xa
˙’
y ra khi ta nˆo

´
i hai th`anh phˆa
`
n cu
˙’
a H`ınh 1.22 bˇa
`
ng c´ach “d´an” hai d¯ı
˙’
nh
(chˇa
˙’
ng ha
.
n x v`a y)? Ch´ung ta nhˆa
.
n d¯u
.
o
.
.
c d¯ˆo
`
thi
.
trong H`ınh 1.23.
Hiˆe
˙’
n nhiˆen c´ac d¯ˆo
`

thi
.
trong H`ınh 1.23 l`a 1−d¯ˇa
˙’
ng cˆa
´
u v´o
.
i d¯ˆo
`
thi
.
trong H`ınh 1.22. V`ı
c´ac khˆo
´
i cu
˙’
a d¯ˆo
`
thi
.
trong H`ınh 1.23 d¯ˇa
˙’
ng cˆa
´
u v´o
.
i c´ac khˆo
´
i cu

˙’
a d¯ˆo
`
thi
.
trong H`ınh 1.21, nˆen
hai d¯ˆo
`
thi
.
n`ay l`a 1−d¯ˇa
˙’
ng cˆa
´
u. Do d¯´o ba d¯ˆo
`
thi
.
trong c´ac H`ınh 1.21, 1.22 v`a 1.23 l`a d¯ˆoi mˆo
.
t
1−d¯ˇa
˙’
ng cˆa
´
u.
1.5.2 2−d¯ˇa
˙’
ng cˆa
´

u
Trong phˆa
`
n trˆen ch´ung ta d¯˜a tˆo
˙’
ng qu´at ho´a kh´ai niˆe
.
m d¯ˇa
˙’
ng cˆa
´
u bˇa
`
ng kh´ai niˆe
.
m 1−d¯ˇa
˙’
ng
cˆa
´
u. C´ac d¯ˆo
`
thi
.
d¯ˇa
˙’
ng cˆa
´
u th`ı 1−d¯ˇa
˙’

ng cˆa
´
u nhu
.
ng ngu
.
o
.
.
c la
.
i khˆong d¯´ung. Su
.
.
tˆo
˙’
ng qu´at ho´a
rˆa
´
t h˜u
.
u ´ıch trong viˆe
.
c nghiˆen c´u
.
u c´ac d¯ˆo
`
thi
.
c´o d¯iˆe

˙’
m kh´o
.
p.
43
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
•
•
•
a
1
xy
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
•
•
a
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
•
•
•
•

b
1
a
3

• •
b
2
c
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


•
•
•
•
c
2
H`ınh 1.23:
Ch´ung ta c`on c´o thˆe
˙’
mo
.
˙’
rˆo
.
ng kh´ai niˆe
.
m n`ay cho c´ac d¯ˆo
`
thi
.
2−liˆen thˆong nhu
.
sau.
Trong d¯ˆo
`
thi
.
2−liˆen thˆong G x´et hai d¯ı
˙’

nh x v`a y m`a xo´a ch´ung (v`a c´ac ca
.
nh liˆen thuˆo
.
c
ch´ung) th`ı d¯ˆo
`
thi
.
mˆa
´
t t´ınh liˆen thˆong. N´oi c´ach kh´ac, G gˆo
`
m mˆo
.
t d¯ˆo
`
thi
.
con g
1
v`a phˆa
`
n b`u
cu
˙’
a n´o ¯g
1
sao cho g
1

v`a ¯g
1
c´o d¯´ung hai d¯ı
˙’
nh chung: x v`a y. Gia
˙’
su
.
˙’
rˇa
`
ng ch´ung ta thu
.
.
c hiˆe
.
n
ph´ep to´an sau trˆen G :
Ph´ep to´an 2. “T´ach” d¯ı
˙’
nh x th`anh x
1
v`a x
2
v`a d¯ı
˙’
nh y th`anh y
1
v`a y
2

sao cho ta thu
d¯u
.
o
.
.
c t`u
.
G hai th`anh phˆa
`
n g
1
v`a ¯g
1
. Gia
˙’
su
.
˙’
c´ac d¯ı
˙’
nh x
1
v`a y
1
thuˆo
.
c th`anh phˆa
`
n g

1
v`a x
2
v`a y
2
thuˆo
.
c ¯g
1
. Bˆay gi`o
.
nˆo
´
i hai d¯ˆo
`
thi
.
g
1
v`a ¯g
1
bˇa
`
ng c´ach ho
.
.
p nhˆa
´
t d¯ı
˙’

nh x
1
v´o
.
i d¯ı
˙’
nh y
2
v`a
d¯ı
˙’
nh x
2
v´o
.
i d¯ı
˙’
nh y
1
. (Hiˆe
˙’
n nhiˆen c´ac ca
.
nh m`a liˆen thuˆo
.
c v´o
.
i x hoˇa
.
c y trong G d¯i c`ung v´o

.
i
g
1
hoˇa
.
c ¯g
1
, khˆong a
˙’
nh hu
.
o
.
˙’
ng d¯ˆe
´
n d¯ˆo
`
thi
.
thu d¯u
.
o
.
.
c o
.
˙’
bu

.
´o
.
c cuˆo
´
i).
Hai d¯ˆo
`
thi
.
go
.
i l`a 2− d¯ˇa
˙’
ng cˆa
´
u nˆe
´
u ch´ung tro
.
˙’
th`anh d¯ˇa
˙’
ng cˆa
´
u sau Ph´ep to´an 1 hoˇa
.
c
Ph´ep to´an 2, hoˇa
.

c ca
˙’
hai ph´ep to´an sau mˆo
.
t sˆo
´
lˆa
`
n thu
.
.
c hiˆe
.
n. H`ınh 1.24 chı
˙’
ra hai d¯ˆo
`
thi
.
trong H`ınh 1.24(a) v`a (d) l`a 2−d¯ˇa
˙’
ng cˆa
´
u. Ch´u ´y rˇa
`
ng trong H`ınh 1.24(a), bˆa
.
c cu
˙’
a d¯ı

˙’
nh x
bˇa
`
ng bˆo
´
n, c`on trong H`ınh 1.24(d) khˆong c´o d¯ı
˙’
nh n`ao bˆa
.
c bˆo
´
n.
T`u
.
d¯i
.
nh ngh˜ıa, suy ra 1−d¯ˇa
˙’
ng cˆa
´
u l`a 2−d¯ˇa
˙’
ng cˆa
´
u, nhu
.
ng ngu
.
o

.
.
c la
.
i chu
.
a chˇa
´
c d¯´ung.
Tuy nhiˆen, v´o
.
i c´ac d¯ˆo
`
thi
.
k−liˆen thˆong v´o
.
i k ≥ 3 th`ı ba kh´ai niˆe
.
m d¯ˇa
˙’
ng cˆa
´
u, 1−d¯ˇa
˙’
ng cˆa
´
u
v`a 2−d¯ˇa
˙’

ng cˆa
´
u l`a nhu
.
nhau (ta
.
i sao?).
Tu
.
o
.
ng ´u
.
ng chu tr`ınh
Hai d¯ˆo
`
thi
.
G
1
v`a G
2
go
.
i l`a cho mˆo
.
t tu
.
o
.

ng ´u
.
ng chu tr`ınh nˆe
´
u ch´ung thoa
˙’
d¯iˆe
`
u kiˆe
.
n sau: Tˆo
`
n
ta
.
i tu
.
o
.
ng ´u
.
ng mˆo
.
t-mˆo
.
t gi ˜u
.
a c´ac ca
.
nh cu

˙’
a G
1
v`a G
2
v`a mˆo
.
t tu
.
o
.
ng ´u
.
ng gi ˜u
.
a c´ac chu tr`ınh
cu
˙’
a G
1
v`a G
2
sao cho mˆo
.
t chu tr`ınh trong G
1
d¯u
.
o
.

.
c ta
.
o bo
.
˙’
i c´ac ca
.
nh cu
˙’
a G
1
c´o mˆo
.
t chu
tr`ınh tu
.
o
.
ng ´u
.
ng trong G
2
d¯u
.
o
.
.
c ta
.

o bo
.
˙’
i c´ac ca
.
nh tu
.
o
.
ng ´u
.
ng trong G
2
, v`a ngu
.
o
.
.
c la
.
i. T`u
.
44