http://www.ebook.edu.vn
Chu
.
o
.
ng 1
D
-
a
.
i cu
.
o
.
ng vˆe
`
d¯ˆo
`
thi
.
1.1 D
-
i
.
nh ngh˜ıa v`a c´ac kh´ai niˆe
.
m
1.1.1 D
-
ˆo
`

i l`a d¯ı
˙’
nh (hay n´ut) v`a mˆo
.
t tˆa
.
p
E c´ac cung sao cho mˆo
˜
i cung e ∈ E tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t cˇa
.
p c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c sˇa
´

(a, b), ta s˜e viˆe
´
t e := (a, b).
Ch´ung ta s˜e gia
˙’
su
.
˙’
c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c d¯´anh sˆo
´
l`a v
1
, v
2
, . . . , v
n
hay gia
˙’
n tiˆe
.
n, 1, 2, . . . , n,
trong d¯´o n = #V l`a sˆo
´

p th´u
.
tu
.
.
v
i
v`a v
j
th`ı d¯ı
˙’
nh v
i
go
.
i l`a
gˆo
´
c v`a d¯ı
˙’
nh v
j
go
.
i l`a ngo
.
n; cung e go
.
i l`a liˆen thuˆo
.

.
o
.
.
c d¯´anh sˆo
´
l`a e
1
, e
2
, . . . , e
m
.
Mˆo
.
t c´ach h`ınh ho
.
c, c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bo
.

.
Mˆo
.
t cung c´o gˆo
´
c tr`ung v´o
.
i ngo
.
n go
.
i l`a khuyˆen.
Nˆe
´
u c´o nhiˆe
`
u ho
.
n mˆo
.
t cung v´o
.
i gˆo
´
c ta
.
i v
i
v`a ngo
.

.
ng l`a d¯ˆo
`
thi
.
khˆong khuyˆen trong d¯´o hai
d¯ı
˙’
nh bˆa
´
t k`y v
i
v`a v
j
c´o nhiˆe
`
u nhˆa
´
t mˆo
.
t cung (v
i
, v
j
). Chˇa
˙’
ng ha
.
n, d¯ˆo
`

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
´o
.
ng.
1.1.2 D
-
ˆo
`
thi
.
v`a ´anh xa
.
d¯a tri
.
V´o
.
i mˆo
˜
i x ∈ V, k´y hiˆe
.
u Γ(x) := {y ∈ V | (x, y) ∈ E}. Khi d¯´o ta c´o mˆo
.
t ´anh xa
.
d¯a tri
.
Γ: V → 2
V
, x → Γ(x). K´y hiˆe
.

.
c x´ac d¯i
.
nh bo
.
˙’
i tˆa
.
p V v`a ´anh xa
.
d¯a
tri
.
Γ t`u
.
V v`ao 2
V
. V`ı vˆa
.
y, d¯ˆo
`
thi
.
n`ay c`on c´o thˆe
˙’
k´y hiˆe
.
u l`a G = (V, Γ).
Nˆe
´

.
`o
.
ng ho
.
.
p n`ay ta c´o
Γ(v
1
) = {v
2
}, Γ(v
2
) = {v
1
, v
3
}, Γ(v
3
) = {v
4
, v
5
}, Γ(v
4
) = {v
5
}, Γ(v
5
) = {v

´
y rˇa
`
ng ch´ung khˆong phu
.
thuˆo
.
c v`ao
hu
.
´o
.
ng cu
˙’
a c´ac cung, t´u
.
c l`a khˆong cˆa
`
n phˆan biˆe
.
t su
.
.
kh´ac nhau gi˜u
.
a c´ac d¯iˆe
˙’
m bˇa
´
t d¯ˆa

cu
˙’
a ch´ung.
V´o
.
i mˆo
˜
i cung, t´u
.
c l`a mˆo
˜
i cˇa
.
p c´o th´u
.
tu
.
.
(v
i
, v
j
) ta cho tu
.
o
.
ng ´u
.
ng cˇa
.

.
ng d¯˜a bi
.
bo
˙’
quˆen. Vˆe
`
h`ınh ho
.
c, ca
.
nh (v
i
, v
j
) d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bo
.
˙’
i c´ac d¯oa
.
n thˇa

.
ng cu
˙’
a d¯ˆo
`
thi
.
G = (V, E) d¯u
.
a vˆe
`
kha
˙’
o s´at tˆa
.
p E l`a
tˆa
.
p c´ac ca
.
nh, t´u
.
c l`a, mˆo
.
t tˆa
.
p h˜u
.
u ha
.

a d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng l`a d¯ˆo
`
thi
.
m`a c´o thˆe
˙’
c´o nhiˆe
`
u ho
.
n mˆo
.
t ca
.
nh liˆen thuˆo
.
c hai d¯ı
˙’
nh.
D
-
ˆo

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7
e
8
e
9
•
• •
•
•
H`ınh 1.2: D
-
ˆo
`
thi
.
vˆo hu
.
´o
.
ng tu
.
o
.
ng ´u
.
ng d¯ˆo
`
thi
.
trong H`ınh 1.1.

trong H`ınh 1.2 l`a kˆe
`
nhau. Hai d¯ı
˙’
nh v
i
v`a v
j
go
.
i l`a kˆe
`
nhau nˆe
´
u tˆo
`
n ta
.
i
ca
.
nh hoˇa
.
c cung e
k
liˆen thuˆo
.
c ch´ung. V´ı du
.
trong H`ınh 1.2 hai d¯ı

c v`a nu
.
˙’
a bˆa
.
c
Bˆa
.
c ngo`ai cu
˙’
a d¯ı
˙’
nh v ∈ V, k´y hiˆe
.
u d
+
G
(v) (hay d
+
(v) nˆe
´
u khˆong so
.
.
nhˆa
`
m lˆa
˜
n) l`a sˆo
´

c´ac cung c´o d¯ı
˙’
nh v l`a ngo
.
n.
Chˇa
˙’
ng ha
.
n, d¯ˆo
`
thi
.
c´o hu
.
´o
.
ng trong H`ınh 1.1 c´o d
+
(v
2
) = 2, d
−
(v
2
) = 1.
11
http://www.ebook.edu.vn
Hiˆe
˙’

`
thi
.
G, t´u
.
c l`a
n

i=1
d
+
(v
i
) =
n

i=1
d
−
(v
i
) = m.
Nˆe
´
u G l`a d¯ˆo
`
thi
.
vˆo hu
.

.
i khuyˆen d¯u
.
o
.
.
c d¯ˆe
´
m hai lˆa
`
n. V´ı du
.
d¯ˆo
`
thi
.
vˆo
hu
.
´o
.
ng trong H`ınh 1.2 c´o d(v
2
) = 3, d(v
5
) = 5.
C´ac cung (ca
.
nh) liˆen thuˆo
.

n
thuˆo
.
c A
c
:= V \ A, v`a ω
−
(A) l`a tˆa
.
p tˆa
´
t ca
˙’
c´ac cung c´o d¯ı
˙’
nh ngo
.
n thuˆo
.
c A v`a d¯ı
˙’
nh gˆo
´
c thuˆo
.
c
A
c
. D
-

`
thi
.
c´o tro
.
ng sˆo
´
D
-
ˆo
`
thi
.
c´o tro
.
ng sˆo
´
nˆe
´
u trˆen mˆo
˜
i cung (hoˇa
.
c ca
.
nh) e ∈ E c´o tu
.
o
.
ng ´u

.
ng
D
-
ˆo
`
thi
.
c´o hu
.
´o
.
ng go
.
i l`a d¯ˆo
´
i x´u
.
ng nˆe
´
u c´o bao nhiˆeu cung da
.
ng (v
i
, v
j
) th`ı c˜ung c´o bˆa
´
y nhiˆeu
cung da

.
i l`a pha
˙’
n d¯ˆo
´
i x´u
.
ng nˆe
´
u c´o cung da
.
ng (v
i
, v
j
) th`ı khˆong c´o cung da
.
ng
(v
j
, v
i
).
12
http://www.ebook.edu.vn
D
-
ˆo
`
thi

j
tˆo
`
n ta
.
i mˆo
.
t ca
.
nh da
.
ng (v
i
, v
j
).
D
-
o
.
n d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng d¯ˆa
`

thi
.
con d¯u
.
o
.
.
c sinh bo
.
˙’
i tˆa
.
p A l`a d¯ˆo
`
thi
.
G
A
:= (A, E
A
) trong d¯´o c´ac d¯ı
˙’
nh l`a
c´ac phˆa
`
n tu
.
˙’
cu
˙’

giao thˆong cu
˙’
a nu
.
´o
.
c Viˆe
.
t Nam th`ı d¯ˆo
`
thi
.
biˆe
˙’
u diˆe
˜
n
ba
˙’
n d¯ˆo
`
giao thˆong cu
˙’
a th`anh phˆo
´
D
-
`a La
.
t l`a mˆo

.
n sinh bo
.
˙’
i tˆa
.
p U l`a d¯ˆo
`
thi
.
v´o
.
i tˆa
.
p d¯ı
˙’
nh V
v`a c´ac cung thuˆo
.
c U (c´ac cung cu
˙’
a E \ U bi
.
xo´a kho
˙’
i G).
D
-
ˆo
`

bˆo
.
phˆa
.
n cu
˙’
a G
A
sinh bo
.
˙’
i U.
1.2 Ma trˆa
.
n biˆe
˙’
u diˆe
˜
n d¯ˆo
`
thi
.
1.2.1 Ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-cung
Ma trˆa

˜
n mˆo
.
t cung cu
˙’
a G v`a mˆo
˜
i
h`ang biˆe
˙’
u diˆe
˜
n mˆo
.
t d¯ı
˙’
nh cu
˙’
a G. Nˆe
´
u e
k
= (v
i
, v
j
) ∈ E th`ı tˆa
´
t ca
˙’

˙’
nh-cung cu
˙’
a d¯ˆo
`
thi
.
trong H`ınh 1.3 l`a





e
1
e
2
e
3
e
4
e
5
a +1 +1 0 0 0
b −1 0 +1 +1 0
c 0 −1 −1 0 +1
d 0 0 0 −1 −1




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
b
d
c
• •
• •
e
1
e
2
e
3
e
4

p m × n go
.
i l`a total unimodular nˆe
´
u tˆa
´
t ca
˙’
c´ac ma trˆa
.
n vuˆong con khˆong
suy biˆe
´
n cu
˙’
a A l`a unimodular.
Mˆe
.
nh d¯ˆe
`
1.2.2 Ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-cung cu
˙’
a d¯ˆo
`

.
t, mˆo
.
t bˇa
`
ng 1 v`a mˆo
.
t bˇa
`
ng −1. Do d¯´o ta c´o thˆe
˙’
ch´u
.
ng
minh theo quy na
.
p nhu
.
sau: Hiˆe
˙’
n nhiˆen, tˆa
´
t ca
˙’
c´ac ma trˆa
.
n vuˆong con khˆong suy biˆe
´
n cˆa
´

´
u mˆo
˜
i cˆo
.
t cu
˙’
a A

ch´u
.
a d¯´ung hai phˆa
`
n tu
.
˙’
kh´ac khˆong th`ı det(A

) = 0 (thˆa
.
t vˆa
.
y, tˆo
˙’
ng tˆa
´
t ca
˙’
c´ac h`ang cu
˙’


) = 0. Cuˆo
´
i c`ung, nˆe
´
u tˆo
`
n ta
.
i cˆo
.
t j cu
˙’
a A

sao cho c´o d¯´ung mˆo
.
t phˆa
`
n tu
.
˙’
kh´ac khˆong
a
ij
(bˇa
`
ng 1, hay −1) th`ı det(A

) = ± det(A


) bˇa
`
ng 1, −1
hay 0 v`a do d¯´o mˆe
.
nh d¯ˆe
`
d¯u
.
o
.
.
c ch´u
.
ng minh. 
14
http://www.ebook.edu.vn
1.2.2 Ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-ca
.
nh
X´et d¯ˆo
`
thi

˙’
0 v`a 1, trong d¯´o mˆo
˜
i cˆo
.
t biˆe
˙’
u diˆe
˜
n
mˆo
.
t ca
.
nh cu
˙’
a G v`a mˆo
˜
i h`ang biˆe
˙’
u diˆe
˜
n mˆo
.
t d¯ı
˙’
nh cu
˙’
a G; ngo`ai ra, nˆe
´

i tr`u
.
a
ik
= 1, a
jk
= 1.
V´ı du
.
1.2.3 Ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
trong H`ınh 1.4 l`a





e

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
a
b
d
c
• •
• •
e
1
e
2
e
3
e
4
e
5
H`ınh 1.4:
Tr´ai v´o
.
i ma trˆa



c´o d¯i
.
nh th´u
.
c bˇa
`
ng −2.
D
-
ˆo
`
thi
.
vˆo hu
.
´o
.
ng G = (V, E) go
.
i l`a hai phˆa
`
n nˆe
´
u c´o thˆe
˙’
phˆan hoa
.
ch tˆa

1
, v
j
∈ V
2
hoˇa
.
c v
j
∈ V
1
, v
i
∈ V
2
.
15
http://www.ebook.edu.vn
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
nh d¯ˆe
`
1.2.5 Ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng G = (V, E) l`a total
unimodular nˆe
´
u v`a chı
˙’
nˆe
´
u G l`a d¯ˆo
`

a ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-ca
.
nh c´o d¯i
.
nh th´u
.
c det(B) = 0, 1 hoˇa
.
c
−1. D
-
iˆe
`
u n`ay d¯´ung v´o
.
i c´ac ma trˆa
.
n vuˆong con cˆa
´
p 1; gia
˙’
su
.
˙’

n tu
.
˙’
bˇa
`
ng 1 th`ı

i∈I
1
B
i
=

i∈I
2
B
i
,
trong d¯´o I
1
v`a I
2
l`a c´ac tˆa
.
p chı
˙’
sˆo
´
tu
.

.
c la
.
i, tˆo
`
n ta
.
i cˆo
.
t c´o d¯´ung mˆo
.
t phˆa
`
n tu
.
˙’
bˇa
`
ng 1, chˇa
˙’
ng ha
.
n b
ij
= 1, k´y hiˆe
.
u C
l`a ma trˆa
.
n nhˆa

c d¯ı
˙’
nh-ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
l`a mˆo
.
t chu
tr`ınh d¯ˆo
.
d`ai le
˙’
(t´u
.
c l`a sˆo
´
ca
.
nh trˆen chu tr`ınh l`a le
˙’
-xem Phˆa
`
n 1.3) c´o d¯i
.
nh th´u

.
´o
.
ng G l`a hai phˆa
`
n nˆe
´
u v`a chı
˙’
nˆe
´
u G khˆong ch´u
.
a chu tr`ınh c´o d¯ˆo
.
d`ai le
˙’
.
Ch´u
.
ng minh. D
-
iˆe
`
u kiˆe
.
n cˆa
`
n. Do V d¯u
.

.
t chu tr`ınh c´o d¯ˆo
.
d`ai le
˙’
µ = {v
i
1
, v
i
2
, . . . , v
i
q
, v
i
1
}
v`a khˆong mˆa
´
t t´ınh tˆo
˙’
ng qu´at, lˆa
´
y v
i
1
∈ V
1
. Do G l`a hai phˆa

∈ V
1
, . . . ,
v`a tˆo
˙’
ng qu´at, v
i
k
∈ V
1
nˆe
´
u k le
˙’
v`a v
i
k
∈ V
2
nˆe
´
u k chˇa
˜
n. M`a chu tr`ınh µ c´o d¯ˆo
.
d`ai le
˙’
nˆen
v
i

u kiˆe
.
n d¯u
˙’
. Khˆong mˆa
´
t t´ınh tˆo
˙’
ng qu´at gia
˙’
thiˆe
´
t d¯ˆo
`
thi
.
G liˆen thˆong. Gia
˙’
su
.
˙’
khˆong tˆo
`
n
ta
.
i chu tr`ınh c´o d¯ˆo
.
d`ai le
˙’

v`a g´an nh˜an ngu
.
o
.
.
c v´o
.
i nh˜an cu
˙’
a v
j
cho tˆa
´
t ca
˙’
c´ac
d¯ı
˙’
nh kˆe
`
v´o
.
i d¯ı
˙’
nh v
j
.
Tiˆe
´
p tu

t k`y kˆe
`
nhau c´o nh˜an kh´ac nhau (mˆo
.
t
mang dˆa
´
u + v`a mˆo
.
t mang dˆa
´
u −); hoˇa
.
c
(b) Tˆo
`
n ta
.
i d¯ı
˙’
nh, chˇa
˙’
ng ha
.
n v
j
k
, d¯u
.
o

.
p tˆa
´
t
ca
˙’
c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c g´an nh˜an “−”. Do tˆa
´
t ca
˙’
c´ac ca
.
nh liˆen thuˆo
.
c gi˜u
.
a c´ac cˇa
.
p d¯ı
˙’
nh c´o nh˜an
kh´ac nhau nˆen d¯ˆo
`

n`ao
d¯´o, v´o
.
i c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c g´an nh˜an “+” v`a “−” xen k˜e nhau xuˆa
´
t ph´at t`u
.
v
i
v`a kˆe
´
t th´uc ta
.
i
v
j
k
. Tu
.
o
.
ng tu
.

´
t ph´at t`u
.
v
i
v`a kˆe
´
t th´uc ta
.
i v
j
k
. Nhu
.
ng
nhu
.
thˆe
´
chu tr`ınh d¯i do
.
c theo µ
1
t`u
.
d¯ı
˙’
nh v
i
d¯ˆe

`
u n`ay mˆau thuˆa
˜
n v´o
.
i gia
˙’
thiˆe
´
t, v`a do d¯´o khˆong thˆe
˙’
xa
˙’
y ra Tru
.
`o
.
ng
ho
.
.
p (b). D
-
i
.
nh l´y d¯u
.
o
.
.

.
t cung liˆen thuˆo
.
c hai d¯ı
˙’
nh bˆa
´
t k`y v
i
v`a v
j
. Ma trˆa
.
n kˆe
`
hay ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-d¯ı
˙’
nh l`a ma trˆa
.
n vuˆong A = (a
ij
) cˆa
´
p n × n

c la
.
i.
Trong tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng, ma trˆa
.
n kˆe
`
cu
˙’
a d¯o
.
n d¯ˆo
`
thi
.

) v`a (v
j
, v
i
). Trong tru
.
`o
.
ng
ho
.
.
p n`ay, ma trˆa
.
n kˆe
`
l`a d¯ˆo
´
i x´u
.
ng.
1.2.4 C´ac biˆe
˙’
u diˆe
˜
n cu
˙’
a d¯ˆo
`
thi

i quan d¯iˆe
˙’
m
lˆa
.
p tr`ınh, n´oi chung c´ac biˆe
˙’
u diˆe
˜
n n`ay khˆong tu
.
o
.
ng d¯u
.
o
.
ng theo kh´ıa ca
.
nh hiˆe
.
u qua
˙’
cu
˙’
a
thuˆa
.
t to´an.
C´o hai c´ach biˆe

du
.
ng ma trˆa
.
n liˆen thuˆo
.
c hoˇa
.
c c´ac dˆa
˜
n xuˆa
´
t cu
˙’
a n´o.
Su
.
˙’
du
.
ng ma trˆa
.
n kˆe
`
Ch´ung ta biˆe
´
t rˇa
`
ng c´ac ma trˆa
.

.
i c´ach biˆe
˙’
u diˆe
˜
n d¯ˆo
`
thi
.
qua ma trˆa
.
n kˆe
`
, ta thˆa
´
y sˆo
´
lu
.
o
.
.
ng thˆong
tin, gˆo
`
m c´ac bit 0 v`a 1, cˆa
`
n lu
.
u tr˜u

c´ac bit trong mˆo
.
t t`u
.
m´ay t´ınh). Khi d¯´o mˆo
˜
i h`ang cu
˙’
a ma
trˆa
.
n kˆe
`
c´o thˆe
˙’
d¯u
.
o
.
.
c viˆe
´
t nhu
.
mˆo
.
t d˜ay n bit trong n/w t`u
.
1
. Do d¯´o sˆo

i x´u
.
ng, nˆen ta chı
˙’
cˆa
`
n lu
.
u tr˜u
.
nu
.
˙’
a tam gi´ac trˆen
cu
˙’
a n´o, v`a do d¯´o chı
˙’
cˆa
`
n n(n − 1)/2 bit. Tuy nhiˆen, v´o
.
i c´ach lu
.
u tr˜u
.
n`ay, s˜e tˇang d¯ˆo
.
ph´u
.

.
´o
.
ng; m 
1
2
n(n + 1) d¯ˆo
´
i
v´o
.
i d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng) c´ach biˆe
˜
u diˆe
˜
n n`ay l`a l˜ang ph´ı. Do d¯´o ta s˜e t`ım c´ach biˆe
˙’
u diˆe
˜
n chı
˙’
c´ac

`
thi
.
c´o
hu
.
´o
.
ng d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bo
.
˙’
i mˆo
.
t ma
˙’
ng c´ac con tro
˙’
V out[1], V out[2], . . . , V out[n], trong d¯´o
mˆo
˜
i con tro

a ma
˙’
ng V out[i]
chı
˙’
d¯ˆe
´
n mˆo
.
t n´ut d¯ˆa
`
u lu
.
u tr˜u
.
mu
.
c d˜u
.
liˆe
.
u cu
˙’
a n´ut tu
.
o
.
ng ´u
.
ng d¯ı

´
t cu
˙’
a c´ac d¯ı
˙’
nh kˆe
`
(d¯ı
˙’
nh d¯u
.
o
.
.
c nˆo
´
i v´o
.
i v
i
theo hu
.
´o
.
ng t`u
.
v
i
ra).
Mˆo

.
`o
.
ng liˆen kˆe
´
t chı
˙’
d¯ˆe
´
n n´ut kˆe
´
tiˆe
´
p trong danh s´ach kˆe
`
n`ay.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
v
1
v
2
v
3
v
4
v
5
v
6
• •
•
••
•
H`ınh 1.6:
C´ach biˆe
˙’
u diˆe
˜
n ma
˙’

.
c d˜u
.
liˆe
.
u tu
.
o
.
ng ´u
.
ng c´ac d¯ı
˙’
nh theo th´u
.
tu
.
.
l`a
A, B, C, D, E, F ).
N´ut d¯ˆa
`
u
V out[1]
..........................................................
.
.
.
.
.

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B
v
1
v
3
NULL
V out[3]
..........................................................
.

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

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

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

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

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

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

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

.
.
.
.
D
v
2
v
3
NULL
V out[5]
..........................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

.
ng d¯ˆo
`
thi
.
trong H`ınh 1.6.
Thay v`ı con tro
˙’
chı
˙’
d¯ˆe
´
n mˆo
.
t danh s´ach c´ac d¯ı
˙’
nh t`u
.
v
i
d¯i ra trong V out[i], ta tro
˙’
d¯ˆe
´
n
danh s´ach c´ac d¯ı
˙’
nh d¯i d¯ˆe
´
n v

c´o hu
.
´o
.
ng trong H`ınh
1.6.
D
-
ˆe
˙’
´y rˇa
`
ng, c´ac sˆo
´
trong n´ut kˆe
`
cu
˙’
a V out[] (tu
.
o
.
ng ´u
.
ng, V in[]) l`a nh˜u
.
ng chı
˙’
sˆo
´

.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng, hai danh s´ach kˆe
`
n`ay l`a tr`ung nhau.
Khi d¯ˆo
`
thi
.
c´o tro
.
ng sˆo
´
, t´u
.
c l`a nˆe
´
u mˆo

i n´ut trong danh s´ach kˆe
`
bˇa
`
ng c´ach thˆem mˆo
.
t tru
.
`o
.
ng
lu
.
u tr˜u
.
tro
.
ng lu
.
o
.
.
ng cu
˙’
a cung.
C´ach biˆe
˙’
u diˆe
˜
n bˇa

.
viˆe
.
n Graph.h (xem Phu
.
lu
.
c A). D
-
ˆe
˙’
xˆay du
.
.
ng
ma
˙’
ng c´ac danh s´ach kˆe
`
V out[] v`a V in[] cho mˆo
.
t d¯ˆo
`
thi
.
, ta c´o thˆe
˙’
su
.
˙’

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
A
v
2
v
6
NULL
V in[2]
..........................................................
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B
v
4
NULL

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
E
v
1
NULL
V in[6]
..........................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
F
v
5
NULL
H`ınh 1.8: Danh s´ach kˆe
`
V in[] tu
.
o
.
ng ´u
.
ng d¯ˆo
`
thi
.
trong H`ınh 1.6.

nh cho ph´ep ch´ung ta mˆo ta
˙’
d¯ˆa
`
y d¯u
˙’
cˆa
´
u tr´uc cu
˙’
a
mˆo
.
t d¯a d¯ˆo
`
thi
.
khˆong c´o khuyˆen. Tuy nhiˆen, do chı
˙’
c´o hai phˆa
`
n tu
.
˙’
kh´ac khˆong trong mˆo
˜
i
cˆo
.
t, nˆen c´o thˆe

.
c ca
.
nh e
k
, k = 1, 2, . . . , m, c´ac gi´a tri
.
α[k] v`a β[k] l`a c´ac chı
˙’
sˆo
´
cu
˙’
a c´ac d¯ı
˙’
nh m`a e
k
liˆen
20
http://www.ebook.edu.vn
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2
v
3
•
••
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
H`ınh 1.9:
thuˆo
.
c. Trong tru
.
`o
.
ng ho
.

`
, c´ach biˆe
˙’
u diˆe
˜
n n`ay c˜ung c´o thˆe
˙’
d¯ˇa
.
c tru
.
ng cho c´ac d¯a
d¯ˆo
`
thi
.
c´o khuyˆen.
Chˇa
˙’
ng ha
.
n, d¯a d¯ˆo
`
thi
.
cu
˙’
a H`ınh 1.9 trong d¯´o c´ac cung d¯u
.
o

, ta chı
˙’
cˆa
`
n thˆem mˆo
.
t ma
˙’
ng w[] k´ıch thu
.
´o
.
c m lu
.
u
tr˜u
.
tro
.
ng lu
.
o
.
.
ng cu
˙’
a mˆo
˜
i ca
.

˙’
a d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng su
.
˙’
du
.
ng danh s´ach c´ac ca
.
nh
xem [43].
Mˆo
´
i liˆen hˆe
.
gi˜u
.
a c´ac biˆe
˙’
u diˆe
˜
n
Dˆe

thi
.
. H`ınh 1.10 minh ho
.
a c´ac kha
˙’
nˇang c´o thˆe
˙’
c´o.
D
-
ˆe
˙’
chuyˆe
˙’
n d¯ˆo
˙’
i gi˜u
.
a c´ac kiˆe
˙’
u d˜u
.
liˆe
.
u, cˆa
`
n c´ac chu
.
o

n, d¯ˆo
`
thi
.
c´o
21
http://www.ebook.edu.vn
Ma trˆa
.
n kˆe
`
d¯u
.
o
.
.
c kˆe
´
t theo h`ang
Ma trˆa
.
n kˆe
`
da
.
ng tu
.
`o
.
ng minh

.
o
.
.
c kˆe
´
t theo cˆo
.
t
Ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-cung
hoˇa
.
c ma trˆa
.
n liˆen thuˆo
.
c d¯ı
˙’
nh-ca
.
nh
da
.
ng kˆe

2
)
|
↓
↑
|
O(mn)
|
↓
↑
|
O(mn)
|
↓
↑
|
O(m)
|
↓
↑
|
O(m)
|
↓
↑
|
O(m)
|
↓
H`ınh 1.10: Mˆo

˙’
d¯u
.
o
.
.
c biˆe
˙’
u diˆe
˜
n bo
.
˙’
i mˆo
.
t ma trˆa
.
n tro
.
ng lu
.
o
.
.
ng (c`on go
.
i l`a ma trˆa
.
n chi ph´ı
hay khoa

ng, t´ınh hiˆe
.
u qua
˙’
cu
˙’
a nhiˆe
`
u vˆa
´
n d¯ˆe
`
phu
.
thuˆo
.
c v`ao biˆe
˙’
u diˆe
˜
n
cu
˙’
a d¯ˆo
`
thi
.
. Do d¯´o, viˆe
.
c cho

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

, 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

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
.

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
`

p
(b, e
2
, c, e
3
, d, e
4
, b), v`a (b, e
5
, f, e
7
, e, e
6
, b).
....................................................................................................................................................................................................................................................................................................................................................................
....................................................................................................................................................................................................................................................................................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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
`

1
, v
2
, . . . , v
k
}.
23
http://www.ebook.edu.vn
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
˙’

´
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

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

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 µ

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

.
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

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

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

`
u).
24