http://www.ebook.edu.vn
Chu
.
o
.
ng 7
Ma
.
ng vˆa
.
n ta
˙’
i
7.1 Mo
.
˙’
d¯ˆa
`
u
Mˆo
.
t trong nh˜u
.
ng b`ai to´an l´y th´u v`a quan tro
.
ng cu
˙’
a l´y thuyˆe
´
t d¯ˆo
`

n s cu
˙’
a d¯ˆo
`
thi
.
d¯ˆe
´
n mˆo
.
t d¯ı
˙’
nh d¯´ıch t. Trong
khung ca
˙’
nh d¯´o, mˆo
˜
i cung (v
i
, v
j
) cu
˙’
a d¯ˆo
`
thi
.
G d¯u
.
o

i qua cung n`ay. B`ai to´an n`ay v`a nh˜u
.
ng ca
˙’
i biˆen cu
˙’
a n´o
c´o rˆa
´
t nhiˆe
`
u ´u
.
ng du
.
ng trong thu
.
.
c tˆe
´
, chˇa
˙’
ng ha
.
n, x´ac d¯i
.
nh mˆa
.
t d¯ˆo
.

.
n`ay, l`o
.
i gia
˙’
i
cu
˙’
a b`ai to´an luˆo
`
ng l´o
.
n nhˆa
´
t c˜ung chı
˙’
ra nh˜u
.
ng no
.
i “ba
˙’
o ho`a” trˆen ma
.
ng giao thˆong v`a ta
.
o
mˆo
.
t “tˇa

n d¯ˆa
`
u tiˆen bo
.
˙’
i Ford
v`a Fulkerson [27] v`a k˜y thuˆa
.
t “g´an nh˜an” cu
˙’
a ho
.
l`a co
.
so
.
˙’
cho nh˜u
.
ng thuˆa
.
t to´an kh´ac gia
˙’
i
quyˆe
´
t nh˜u
.
ng vˆa
´

thi
.
khˆong chı
˙’
d¯u
.
o
.
.
c gˇa
´
n v´o
.
i kha
˙’
nˇang q
ij
cho biˆe
´
t cˆa
.
n trˆen
cu
˙’
a luˆo
`
ng trˆen cung (v
i
, v
j

t tˆa
.
p chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c c´ac gi´a
tri
.
cu
˙’
a luˆo
`
ng c˜ung thoa
˙’
m˜an c`ung l´uc hai r`ang buˆo
.
c n`ay. Tuy nhiˆen-n´oi chung-nhiˆe
`
u
luˆo
`
ng thoa
˙’
d¯iˆe

`
ng chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c
v´o
.
i chi ph´ı nho
˙’
nhˆa
´
t t`u
.
s d¯ˆe
´
n t.
2. X´et tru
.
`o
.
ng ho
.
.
p d¯`oi ho

ng l´o
.
n nhˆa
´
t t`u
.
s d¯ˆe
´
n t nhu
.
ng c´ach
l`am n`ay qu´a thˆo! Tu
.
o
.
ng tu
.
.
v´o
.
i t`ım tˆa
´
t ca
˙’
c´ac d¯u
.
`o
.
ng d¯i ngˇa
´

.
vˆo hu
.
´o
.
ng, phu
.
o
.
ng
ph´ap gia
˙’
i quyˆe
´
t n´o khˆong liˆen quan d¯ˆe
´
n l`o
.
i gia
˙’
i cu
˙’
a b`ai to´an luˆo
`
ng l´o
.
n nhˆa
´
t gi˜u
.

i c´ac h`ang ho´a kh´ac nhau gi˜u
.
a hai tˆo
˙’
ho
.
.
p nguˆo
`
n-d¯´ıch kh´ac nhau, th`ı b`ai to´an
cu
.
.
c d¯a
.
i tˆo
˙’
ng sˆo
´
tˆa
´
t ca
˙’
c´ac luˆo
`
ng t`u
.
c´ac nguˆo
`
n d¯ˆe

thiˆe
´
t (ˆa
˙’
n) trong tˆa
´
t ca
˙’
c´ac tru
.
`o
.
ng ho
.
.
p trˆen l`a sˆo
´
lu
.
o
.
.
ng luˆo
`
ng d¯ˆe
´
n bˇa
`
ng sˆo
´

`
ng
luˆo
`
ng d¯ˆe
´
n nhˆan v´o
.
i mˆo
.
t sˆo
´
nguyˆen khˆong ˆam n`ao d¯´o, th`ı b`ai to´an luˆo
`
ng l´o
.
n nhˆa
´
t (t`u
.
s d¯ˆe
´
n t) d¯u
.
o
.
.
c xem nhu
.
b`ai to´an trong c´ac d¯ˆo

” bo
.
˙’
i d¯ˆo
`
thi
.
, v`a do vˆa
.
y luˆo
`
ng v`ao s
v`a luˆo
`
ng ra kho
˙’
i t c´o thˆe
˙’
thay d¯ˆo
˙’
i ho`an to`an d¯ˆo
.
c lˆa
.
p.
C´ac b`ai to´an vˆe
`
luˆo
`
ng d¯u

n go
.
n c´ac b`ai to´an thu
.
`o
.
ng gˇa
.
p, chı
˙’
ra mˆo
´
i liˆen hˆe
.
gi˜u
.
a
ch´ung v`a xˆay du
.
.
ng mˆo
.
t sˆo
´
thuˆa
.
t to´an gia
˙’
i quyˆe
´

ng d¯a-h`ang ho´a rˆa
´
t kh´ac biˆe
.
t
vˆe
`
ba
˙’
n chˆa
´
t, v`a khˆong pha
˙’
i d¯ˆe
`
u hiˆe
.
u qua
˙’
nhu
.
phu
.
o
.
ng ph´ap g´an nh˜an, nˆen s˜e khˆong d¯u
.
o
.
.

n nhˆa
´
t trˆen ma
.
ng vˆa
.
n ta
˙’
i G l`a mˆo
.
t luˆo
`
ng v´o
.
i gi´a tri
.
l´o
.
n nhˆa
´
t. N´oi chung c´o mˆo
.
t
v`ai luˆo
`
ng v´o
.
i c`ung gi´a tri
.
l´o

u v´o
.
i luˆo
`
ng n`ao d¯´o v`a tˇang gi´a tri
.
cu
˙’
a luˆo
`
ng cho d¯ˆe
´
n khi
khˆong thˆe
˙’
tˇang d¯u
.
o
.
.
c n˜u
.
a. Kˆe
´
t qua
˙’
ta c´o luˆo
`
ng l´o
.

`
u d¯u
.
o
.
.
c
dˆa
˜
n t`u
.
t`au s v`a d¯u
.
o
.
.
c bo
.
m thˆong qua ma
.
ng d¯ˆe
´
n nh`a m´ay lo
.
c dˆa
`
u t. C´ac d¯ı
˙’
nh b, c, d v`a e l`a
c´ac tra

˙’
a ˆo
´
ng dˆa
˜
n. B`ai to´an d¯ˇa
.
t ra
l`a t`ım c´ach chuyˆe
˙’
n nhiˆe
`
u nhˆa
´
t lu
.
o
.
.
ng dˆa
`
u t`u
.
t`au d¯ˆe
´
n nh`a m´ay v`a t´ınh gi´a tri
.
n`ay. H`ınh 7.1
l`a mˆo
.

3
5
2
2
2
4
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
H`ınh 7.1: V´ı du
.
vˆe
`
ma
.
ng vˆa
.

(a) c´o mˆo
.
t v`a chı
˙’
mˆo
.
t d¯ı
˙’
nh s, go
.
i l`a d¯ı
˙’
nh v`ao (hoˇa
.
c d¯ı
˙’
nh nguˆo
`
n) cu
˙’
a ma
.
ng, khˆong c´o cung
d¯ˆe
´
n n´o.
(b) c´o mˆo
.
t v`a chı
˙’

.
c g´an mˆo
.
t sˆo
´
nguyˆen khˆong ˆam q
ij
, go
.
i l`a kha
˙’
nˇang cu
˙’
a
cung u.
(d) d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng nhˆa
.
n d¯u
.
o
.
.

´
i v`ao l`a d¯ı
˙’
nh s v`a lˆo
´
i ra
l`a d¯ı
˙’
nh t. Kha
˙’
nˇang cung (s, b) l`a q
sb
= 3 v`a cu
˙’
a cung (b, c) l`a q
bc
= 2.
Trong chu
.
o
.
ng n`ay, nˆe
´
u G l`a ma
.
ng vˆa
.
n ta
˙’
i ch´ung ta s˜e k´y hiˆe

) l`a q
ij
. Luˆo
`
ng (chˆa
´
p
nhˆa
.
n d¯u
.
o
.
.
c) F trong G g´an mˆo
˜
i cung (v
i
, v
j
) mˆo
.
t sˆo
´
khˆong ˆam f
ij
sao cho
(a) 0 ≤ f
ij
≤ q

˙’
c´ac gi´a tri
.
i; nˆe
´
u khˆong c´o cung (v
i
, v
j
), ta d¯ˇa
.
t f
ij
= 0).
Ta n´oi f
ij
l`a luˆo
`
ng trˆen cung (v
i
, v
j
). V´o
.
i mˆo
˜
i j, ta go
.
i


.
n (7.1) go
.
i l`a ba
˙’
o to`an luˆo
`
ng. Trong v´ı du
.
dˆa
˜
n dˆa
`
u cu
˙’
a H`ınh 7.1, ba
˙’
o to`an luˆo
`
ng c´o
ngh˜ıa dˆa
`
u khˆong d¯u
.
o
.
.
c su
.
˙’

= 1, f
de
= 2, f
ez
= 2,
x´ac d¯i
.
nh luˆo
`
ng trˆen ma
.
ng vˆa
.
n ta
˙’
i cu
˙’
a H`ınh 7.1. Chˇa
˙’
ng ha
.
n, luˆo
`
ng d¯ˆe
´
n d¯ı
˙’
nh d l`a
f
sd

˙’
nˇang cu
˙’
a e
l`a x v`a luˆo
`
ng trˆen e l`a y.
s
t
b
c
d
e
• •
• •
• •
3, 2
5, 3
2, 2
2, 1
2, 2
4, 3
4, 2
.
.
.
.
.
.
.

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

.
.
.

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

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

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

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

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

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

.

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


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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

˙’
nh s l`a
f
sb
+ f
sd
bˇa
`
ng luˆo
`
ng d¯ˆe
´
n d¯ı
˙’
nh t :
f
ct
+ f
et
v`a bˇa
`
ng 5. Thˆa
.
t vˆa
.
y, ta c´o
D
-
i
.

c l`a

i
f
si
=

i
f
it
.
Ch´u
.
ng minh. Ta c´o

j∈V


i∈V
f
ij

=

j∈V


i∈V
f
ji


i∈V
f
it
−

i∈V
f
ti
) + (

i∈V
f
is
−

i∈V
f
si
) +

j∈V,j=s,t
(

i∈V
f
ij
−

i∈V

su
.
˙’
F l`a luˆo
`
ng trˆen ma
.
ng vˆa
.
n ta
˙’
i G. D
-
a
.
i lu
.
o
.
.
ng

i
f
si
=

i
f
it

o
.
.
c l´o
.
n nhˆa
´
t trˆen d¯ˆo
`
thi
.
G; t´u
.
c l`a trong sˆo
´
tˆa
´
t
ca
˙’
c´ac luˆo
`
ng trˆen G, t`ım luˆo
`
ng F c´o gi´a tri
.
l´o
.
n nhˆa
´

D
-
i
.
nh ngh˜ıa 7.2.9 Nˆe
´
u c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
G = (V, E) d¯u
.
o
.
.
c phˆan hoa
.
ch th`anh hai tˆa
.
p con
V
0
v`a
˜
V
0

´
t th´uc thuˆo
.
c
˜
V
0
go
.
i l`a thiˆe
´
t diˆe
.
n cu
˙’
a G. Tˆa
.
p c´ac cung
cu
˙’
a thiˆe
´
t diˆe
.
n thu
.
`o
.
ng d¯u
.

n (V
0
→
˜
V
0
) t´ach s kho
˙’
i t nˆe
´
u s ∈ V
0
v`a t ∈
˜
V
0
.
Kha
˙’
nˇang thˆong qua hay gi´a tri
.
cu
˙’
a thiˆe
´
t diˆe
.
n l`a tˆo
˙’
ng cu

.
c
˜
V
0
; t´u
.
c l`a
v(V
0
→
˜
V
0
) :=

(v
i
,v
j
)∈(V
0
→
˜
V
0
)
q
ij
.

.
n nho
˙’
nhˆa
´
t-luˆo
`
ng l´o
.
n nhˆa
´
t) Gi´a tri
.
cu
˙’
a luˆo
`
ng l´o
.
n nhˆa
´
t
t`u
.
s d¯ˆe
´
n t bˇa
`
ng kha
˙’

´
t t`u
.
s d¯ˆe
´
n t khˆong thˆe
˙’
l´o
.
n ho
.
n v(V
m
→
˜
V
m
)
do tˆa
´
t ca
˙’
c´ac d¯u
.
`o
.
ng d¯i t`u
.
s d¯ˆe
´

i mˆo
.
t luˆo
`
ng d¯a
.
t gi´a tri
.
n`ay. Ta xem luˆo
`
ng d¯˜a cho F tu
.
o
.
ng
´u
.
ng v´o
.
i mˆo
.
t vector m chiˆe
`
u v`a d¯i
.
nh ngh˜ıa thiˆe
´
t diˆe
.
n (V

0
, v`a hoˇa
.
c f
ij
< q
ij
hoˇa
.
c f
ij
> 0 th`ı d¯ˇa
.
t v
j
v`ao trong tˆa
.
p V
0
.
3. Lˇa
.
p la
.
i Bu
.
´o
.
c 2 cho d¯ˆe
´

.
.
p 1. t ∈ V
0
.
Theo Bu
.
´o
.
c 2 trˆen, tˆo
`
n ta
.
i mˆo
.
t dˆay chuyˆe
`
n t`u
.
s d¯ˆe
´
n t sao cho mo
.
i cung (v
i
, v
j
) d¯u
.
o

ij
< q
ij
v`a c´ac cung
(v
k
, v
l
) d¯u
.
o
.
.
c d¯i
.
nh hu
.
´o
.
ng ngu
.
o
.
.
c, t´u
.
c l`a hu
.
´o
.

f
= min
(v
i
,v
j
)
[q
ij
− f
ij
]; (v
i
, v
j
) thuˆa
.
n hu
.
´o
.
ng,
δ
b
= min
(v
k
,v
i
)

ng trˆen tˆa
´
t ca
˙’
c´ac cung d¯i
.
nh hu
.
´o
.
ng thuˆa
.
n v`a tr`u
.
d¯i δ trˆen
tˆa
´
t ca
˙’
c´ac cung d¯i
.
nh hu
.
´o
.
ng ngu
.
o
.
.

˙’
ho
.
n luˆo
`
ng ban d¯ˆa
`
u mˆo
.
t lu
.
o
.
.
ng δ. D
-
iˆe
`
u n`ay l`a hiˆe
˙’
n nhiˆen
v`ı thˆem mˆo
.
t lu
.
o
.
.
ng δ v`ao c´ac cung theo chiˆe
`

c th`ı luˆo
`
ng vˆa
˜
n khˆong
ˆam (do δ < δ
b
).
´
Ap du
.
ng la
.
i v´o
.
i luˆo
`
ng m´o
.
i theo c´ac Bu
.
´o
.
c 1-3 trˆen ta la
.
i thu d¯u
.
o
.
.

c 2, f
ij
= q
ij
v´o
.
i mo
.
i cung (v
i
, v
j
) ∈ (V
0
→
˜
V
0
) v`a f
kl
= 0 v´o
.
i mo
.
i cung (v
k
, v
l
) ∈
(

˜
V
0
)
q
ij
v`a

(v
k
,v
l
)∈(
˜
V
0
→V
0
)
f
kl
= 0;
t´u
.
c l`a gi´a tri
.
cu
˙’
a luˆo
`

f
kl
v`a bˇa
`
ng kha
˙’
nˇang thˆong qua cu
˙’
a thiˆe
´
t diˆe
.
n (V
0
→
˜
V
0
).
Do Tru
.
`o
.
ng ho
.
.
p 1, luˆo
`
ng tˇang ´ıt nhˆa
´

t c´o thˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c sau mˆo
.
t sˆo
´
h˜u
.
u ha
.
n bu
.
´o
.
c
khi Tru
.
`o
.
ng ho
.
.
p 2 xa

t v`a thiˆe
´
t diˆe
.
n tu
.
o
.
ng ´u
.
ng c´o kha
˙’
nˇang thˆong qua nho
˙’
nhˆa
´
t. 
Phu
.
o
.
ng ph´ap xˆay du
.
.
ng d¯u
.
o
.
.
c su

.
.
c tr`ınh b`ay du
.
´o
.
i d¯ˆay.
Xuˆa
´
t ph´at t`u
.
luˆo
`
ng chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c tu`y ´y (c´o thˆe
˙’
su
.
˙’
du
.
ng luˆo

`
n d¯iˆe
`
u chı
˙’
nh luˆo
`
ng d¯u
.
o
.
.
c thu
.
.
c hiˆe
.
n bˇa
`
ng c´ach g´an nh˜an. Khi t`ım d¯u
.
o
.
.
c mˆo
.
t
dˆay chuyˆe
`
n d¯iˆe

ng d¯ˆe
˙’
g´an nh˜an la
.
i. Nˆe
´
u khˆong tˆo
`
n ta
.
i dˆay chuyˆe
`
n d¯iˆe
`
u chı
˙’
nh luˆo
`
ng
th`ı thuˆa
.
t to´an kˆe
´
t th´uc, luˆo
`
ng chˆa
´
p nhˆa
.
n d¯u

˜
i d¯ı
˙’
nh chı
˙’
c´o thˆe
˙’
c´o mˆo
.
t trong ba kha
˙’
nˇang:
1. d¯u
.
o
.
.
c g´an nh˜an v`a d¯u
.
o
.
.
c kiˆe
˙’
m tra (t´u
.
c l`a n´o d¯u
.
o
.

a d¯u
.
o
.
.
c kiˆe
˙’
m tra (t´u
.
c l`a n´o d¯u
.
o
.
.
c g´an nh˜an v`a tˆo
`
n ta
.
i d¯ı
˙’
nh liˆen
thuˆo
.
c v´o
.
i n´o chu
.
a d¯u
.
o

ng hoˇa
.
c (+v
j
, δ) hoˇa
.
c (−v
j
, δ).
Trong tru
.
`o
.
ng ho
.
.
p d¯ˆa
`
u, c´o thˆe
˙’
tˇang luˆo
`
ng do
.
c theo cung (v
i
, v
j
); trong tru
.

˙’
hai tru
.
`o
.
ng ho
.
.
p l`a lu
.
o
.
.
ng h`ang
nhiˆe
`
u nhˆa
´
t c´o thˆe
˙’
thˆem hoˇa
.
c b´o
.
t gi´a tri
.
cu
˙’
a luˆo
`

`
u chı
˙’
nh luˆo
`
ng t`u
.
s d¯ˆe
´
n v
i
.
Kho
.
˙’
i ta
.
o tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh chu
.
a d¯u
.
o
.
.

.
c kiˆe
˙’
m
tra; tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh kh´ac chu
.
a d¯u
.
o
.
.
c g´an nh˜an.
2. Cho
.
n d¯ı
˙’
nh v
i
∈ V d¯˜a d¯u
.
o
.
.
c g´an nh˜an v`a chu

.
.
c la
.
i, gia
˙’
su
.
˙’
(±v
k
, δ(v
i
)) l`a nh˜an cu
˙’
a
d¯ı
˙’
nh v
i
.
• G´an nh˜an (+v
i
, δ(v
j
)) cho tˆa
´
t ca
˙’
c´ac d¯ı

i
, δ(v
j
)) cho tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh v
j
∈ Γ
−1
(v
i
) chu
.
a d¯u
.
o
.
.
c g´an nh˜an sao
cho f
ji
> 0, trong d¯´o
δ(v
j
) := min{δ(v
i

.
.
c
g´an nh˜an v`a chu
.
a d¯u
.
o
.
.
c kiˆe
˙’
m tra).
3. Nˆe
´
u d¯ı
˙’
nh t d¯u
.
o
.
.
c g´an nh˜an, chuyˆe
˙’
n sang Bu
.
´o
.
c 4; ngu
.

˜
V
0
l`a tˆa
.
p c´ac d¯ı
˙’
nh chu
.
a d¯u
.
o
.
.
c
g´an nh˜an th`ı (V
0
→
˜
V
0
) l`a thiˆe
´
t diˆe
.
n nho
˙’
nhˆa
´
t.

f
zc
+ δ(t);
• Nˆe
´
u nh˜an cu
˙’
a d¯ı
˙’
nh c c´o da
.
ng (−z, δ(c)) th`ı thay luˆo
`
ng trˆen cung (x, z) l`a f
cz
bo
.
˙’
i
f
cz
− δ(t);
5. Nˆe
´
u z = s th`ı xo´a tˆa
´
t ca
˙’
c´ac nh˜an t`u
.

7.2.2 D
-
ˆo
`
thi
.
d¯iˆe
`
u chı
˙’
nh luˆo
`
ng
Qu´a tr`ınh t`ım mˆo
.
t dˆay chuyˆe
`
n d¯ˆe
˙’
tˇang gi´a tri
.
cu
˙’
a luˆo
`
ng F trong d¯ˆo
`
thi
.
G = (V, E) c´o

, E
µ
),
V
µ
= V, E
µ
= E
µ
1
∪ E
µ
2
, trong d¯´o
E
µ
1
:= {(v
µ
i
, v
µ
j
) | f
ij
< q
ij
, (v
i
, v

:= {(v
µ
j
, v
µ
i
) | f
ij
> 0, (v
i
, v
j
) ∈ E}
v´o
.
i kha
˙’
nˇang cu
˙’
a mˆo
˜
i cung (v
µ
j
, v
µ
i
) ∈ E
µ
2

.
m vi R(s) trong d¯ˆo
`
thi
.
d¯iˆe
`
u chı
˙’
nh luˆo
`
ng G
µ
(F ). Nˆe
´
u t ∈ R(s),
t´u
.
c l`a nˆe
´
u d¯ı
˙’
nh t d¯u
.
o
.
.
c g´an nh˜an, th`ı c´o thˆe
˙’
x´ac d¯i

nh luˆo
`
ng cu
˙’
a G l`a d¯u
.
`o
.
ng d¯i P m`a c´ac
cung cu
˙’
a P thuˆo
.
c E
µ
1
tu
.
o
.
ng ´u
.
ng cung d¯i
.
nh hu
.
´o
.
ng thuˆa
.

Trong mˆo
.
t sˆo
´
tru
.
`o
.
ng ho
.
.
p ta muˆo
´
n phˆan t´ıch mˆo
.
t luˆo
`
ng ph´u
.
c ta
.
p th`anh tˆo
˙’
ng cu
˙’
a nh˜u
.
ng
luˆo
`

t cu
˙’
a luˆo
`
ng trˆen ma
.
ng vˆa
.
n ta
˙’
i, v`a ngo`ai ra phu
.
c vu
.
mˆo
.
t sˆo
´
thuˆa
.
t to´an vˆe
`
luˆo
`
ng.
K´y hiˆe
.
u h◦ (S) l`a luˆo
`
ng trong d¯ˆo

p S tu`y ´y.
Hiˆe
˙’
n nhiˆen rˇa
`
ng h ◦ (S) l`a mˆo
.
t luˆo
`
ng th`ı tˆa
.
p S c´ac cung hoˇa
.
c ta
.
o th`anh mˆo
.
t d¯u
.
`o
.
ng d¯i t`u
.
s
d¯ˆe
´
n t hoˇa
.
c l`a mˆo
.

ng t`u
.
s d¯ˆe
´
n t c´o gi´a tri
.
nguyˆen v trong G th`ı F c´o thˆe
˙’
phˆan
t´ıch th`anh
F = 1 ◦ (P
1
) + 1 ◦ (P
2
) + · · · + 1 ◦ (P
v
) + 1 ◦ (Φ
1
) + 1 ◦ (Φ
2
) + · · · + 1 ◦ (Φ
κ
),
trong d¯´o P
1
, P
2
, P
v
l`a c´ac d¯u

khˆong nhˆa
´
t thiˆe
´
t phˆan biˆe
.
t).
Ch´u
.
ng minh. T`u
.
G = (V, E) v´o
.
i luˆo
`
ng F cho tru
.
´o
.
c ta xˆay du
.
.
ng d¯ˆo
`
thi
.
unitary G
e
= (V
e

, v
j
) cu
˙’
a G th`ı ta thay bˇa
`
ng f
ij
cung song song gi˜u
.
a c´ac d¯ı
˙’
nh tu
.
o
.
ng ´u
.
ng v
e
i
v`a v
e
j
cu
˙’
a G
e
.
Nˆe

d¯´o mˆo
˜
i cung cu
˙’
a n´o tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t d¯o
.
n vi
.
luˆo
`
ng trˆen cung tu
.
o
.
ng ´u
.
ng trong G; n´oi c´ach
kh´ac, G
e
biˆe

m˜an
d
+
(v
e
i
) = d
−
(v
e
i
), v´o
.
i mo
.
i v
e
i
= s
e
hoˇa
.
c t
e
,
d
+
(s
e
) = d

`
thi
.
G
e
s˜e c´o mˆo
.
t ma
.
ch Euler (xem Phˆa
`
n 5.1). Loa
.
i bo
˙’
v cung n`ay kho
˙’
i ma
.
ch Euler, ta d¯u
.
o
.
.
c v
d¯u
.
`o
.
ng d¯i t`u

, . . . , P

v
. C´ac d¯u
.
`o
.
ng d¯i P

i
khˆong nhˆa
´
t thiˆe
´
t so
.
cˆa
´
p (mˇa
.
c d`u ch´ung l`a d¯o
.
n gia
˙’
n). Tuy
nhiˆen, mˆo
˜
i d¯u
.
`o

t
e
v`a mˆo
.
t sˆo
´
c´ac ma
.
ch so
.
cˆa
´
p r`o
.
i nhau. Do vˆa
.
y,
F = 1 ◦ (P
1
) + 1 ◦ (P
2
) + · · · + 1 ◦ (P
v
) + 1 ◦ (Φ
1
) + 1 ◦ (Φ
2
) + · · · + 1 ◦ (Φ
κ
),

.
`o
.
ng d¯i v`a c´ac chu tr`ınh c´o thˆe
˙’
tr`ung nhau. Nˆe
´
u chı
˙’
c´o v

d¯u
.
`o
.
ng d¯i v`a
κ

ma
.
ch d¯ˆa
`
u tiˆen kh´ac nhau, v´o
.
i d¯u
.
`o
.
ng d¯i P
i

, . . . , Φ
κ
th`ı F c´o thˆe
˙’
viˆe
´
t du
.
´o
.
i da
.
ng
F =
v


i=1
h
i
◦ (P
i
) +
κ


i=1
l
i
◦ (Φ

c phˆan t´ıch th`anh c´ac d¯u
.
`o
.
ng d¯i (t`u
.
s d¯ˆe
´
n t)
v`a c´ac ma
.
ch so
.
cˆa
´
p:
F = 2 ◦ P
1
+ 1 ◦ P
2
+ 1 ◦ Φ
1
+ 1 ◦ Φ
2
+ 1 ◦ Φ
3
,
trong d¯´o
P
1

2
, v
4
, v
5
, v
6
, v
2
},
Φ
3
= {v
5
, v
6
, v
7
, v
5
}.
7.3 C´ac ca
˙’
i biˆen d¯o
.
n gia
˙’
n cu
˙’
a b`ai to´an luˆo

´
t.
7.3.1 C´ac d¯ˆo
`
thi
.
c´o nhiˆe
`
u nguˆo
`
n v`a nhiˆe
`
u d¯´ıch
X´et d¯ˆo
`
thi
.
v´o
.
i n
s
d¯ı
˙’
nh v`ao v`a n
t
d¯ı
˙’
nh ra v`a gia
˙’
su

´
n tˆa
´
t ca
˙’
c´ac d¯´ıch c´o thˆe
˙’
d¯u
.
a vˆe
`
b`ai to´an luˆo
`
ng l´o
.
n nhˆa
´
t bˇa
`
ng c´ach thˆem mˆo
.
t d¯ı
˙’
nh nguˆo
`
n nhˆan ta
.
o s v`a mˆo
.
t d¯ı

n
d¯ı
˙’
nh t. Kha
˙’
nˇang cu
˙’
a c´ac cung thˆem v`ao t`u
.
s d¯ˆe
´
n c´ac nguˆo
`
n c´o thˆe
˙’
d¯ˇa
.
t bˇa
`
ng vˆo c`ung, hoˇa
.
c
trong tru
.
`o
.
ng ho
.
.
p lu

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

.
.
.
.
.
.

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

.
.
.

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

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

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

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

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

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


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

.

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

.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

.
.
.
.
.

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

.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.
.
.
.
.
.

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

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

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

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

.
.
.
.
.
.
•
s
t
•
v
1
•
v
2
•
v
3
•
v
6
•
v
7
•
v
5
•
v
4

˙’
nh ra t c´o
thˆe
˙’
d¯ˇa
.
t bˇa
`
ng nhu cˆa
`
u ta
.
i c´ac d¯ı
˙’
nh ra t
k
hoˇa
.
c bˇa
`
ng vˆo ha
.
n nˆe
´
u c´o nhu cˆa
`
u l`a vˆo ha
.
n.
Nˆe

c la
.
i, th`ı b`ai to´an khˆong pha
˙’
i l`a ca
˙’
i biˆen d¯o
.
n gia
˙’
n cu
˙’
a b`ai to´an luˆo
`
ng l´o
.
n nhˆa
´
t t`u
.
s
d¯ˆe
´
n t m`a c´o thˆe
˙’
d¯u
.
a vˆe
`
b`ai to´an d¯a luˆo

u ngo`ai kha
˙’
nˇang q
ij
cu
˙’
a c´ac cung, ta thˆem kha
˙’
nˇang cu
˙’
a c´ac d¯ı
˙’
nh w
j
, j = 1, 2, . . . , n, sao
cho tˆo
˙’
ng sˆo
´
lu
.
o
.
.
ng h`ang d¯i d¯ˆe
´
n d¯ı
˙’
nh v
j

n t`ım luˆo
`
ng l´o
.
n nhˆa
´
t t`u
.
s d¯ˆe
´
n t v´o
.
i gia
˙’
thiˆe
´
t thˆem ta
.
i c´ac d¯ı
˙’
nh. X´et d¯ˆo
`
thi
.
G
0
sao cho mo
.
i d¯ı
˙’

.
i cung (v
i
, v
j
) cu
˙’
a G d¯ˆe
´
n d¯ı
˙’
nh v
j
tu
.
o
.
ng ´u
.
ng mˆo
.
t cung (v
−
i
, v
+
j
) d¯ˆe
´
n d¯ı

, v
+
k
) cu
˙’
a G
0
xuˆa
´
t ph´at t`u
.
v
−
j
. Ngo`ai
ra ta thˆem mˆo
.
t cung gi˜u
.
a v
+
j
v`a v
−
j
v´o
.
i kha
˙’
nˇang thˆong qua w

j
pha
˙’
i d¯u
.
o
.
.
c chuyˆe
˙’
n do
.
c theo cung (v
+
j
, v
−
j
) v´o
.
i kha
˙’
184
http://www.ebook.edu.vn
nˇang thˆong qua w
j
nˆen luˆo
`
ng l´o
.

.
i r`ang buˆo
.
c chı
˙’
ta
.
i c´ac cung. Cˆa
`
n ch´u ´y rˇa
`
ng nˆe
´
u thiˆe
´
t diˆe
.
n nho
˙’
nhˆa
´
t cu
˙’
a G
0
khˆong ch´u
.
a c´ac cung da
.
ng (v

.
i, thiˆe
´
t diˆe
.
n nho
˙’
nhˆa
´
t cu
˙’
a G
0
ch´u
.
a c´ac
cung loa
.
i n`ay th`ı c´ac d¯ı
˙’
nh tu
.
o
.
ng ´u
.
ng cu
˙’
a G l`a ba
˙’

.
G trong d¯´o c´ac cung (v
i
, v
j
) ngo`ai cˆa
.
n trˆen q
ij
c`on c´o cˆa
.
n du
.
´o
.
i vˆe
`
luˆo
`
ng l`a r
ij
.
Gia
˙’
su
.
˙’
ta muˆo
´
n biˆe

).
T`u
.
G, ta thˆem mˆo
.
t d¯ı
˙’
nh v`ao nhˆan ta
.
o s
a
v`a d¯ı
˙’
nh ra nhˆan ta
.
o t
a
d¯ˆe
˙’
nhˆa
.
n d¯u
.
o
.
.
c G
a
.
Mˆo

hai (v
i
, t
a
) v´o
.
i kha
˙’
nˇang r
ij
v`a cˆa
.
n du
.
´o
.
i bˇa
`
ng khˆong. Thay
q
ij
bo
.
˙’
i q
ij
− r
ij
v`a r
ij

a
. Nˆe
´
u gi´a tri
.
cu
˙’
a luˆo
`
ng l´o
.
n
nhˆa
´
t bˇa
`
ng

r
ij
=0
r
ij
(t´u
.
c l`a, nˆe
´
u tˆa
´
t ca

`
ng chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c v´o
.
i gia
tri
.
f
ts
trong d¯ˆo
`
thi
.
ban d¯ˆa
`
u. Thˆa
.
t vˆa
.
y, nˆe
´
u ta tr`u

) th`ı tˆo
˙’
ng lu
.
o
.
.
ng h`ang t`u
.
s
a
d¯ˆe
´
n t
a
gia
˙’
m mˆo
.
t lu
.
o
.
.
ng l`a r
ij
, luˆo
`
ng trˆen c´ac cung (v
i

ij
bˇa
`
ng r
ij
nˆe
´
u gi´a tri
.
ban d¯ˆa
`
u cu
˙’
a f
ij
tu
.
o
.
ng ´u
.
ng luˆo
`
ng l´o
.
n nhˆa
´
t bˇa
`
ng khˆong, v`a gi´a tri

´o
.
c tr`u
.
luˆo
`
ng l´o
.
n nhˆa
´
t ngu
.
o
.
.
c v´o
.
i bu
.
´o
.
c d¯iˆe
`
u chı
˙’
nh luˆo
`
ng trong
thuˆa
.

´
i c`ung, tiˆe
´
n tr`ınh tr`u
.
luˆo
`
ng s˜e cho luˆo
`
ng t`u
.
s
a
d¯ˆe
´
n t
a
c´o gi´a tri
.
bˇa
`
ng khˆong (do d¯´o
s˜e khiˆe
´
n hai d¯ı
˙’
nh nhˆan ta
.
o v`a c´ac cung liˆen thuˆo
.

t luˆo
`
ng
“lu
.
u thˆong” trong d¯ˆo
`
thi
.
v´o
.
i gi´a tri
.
bˇa
`
ng f
ts
.
Mˇa
.
t kh´ac ta c´o
D
-
i
.
nh l´y 7.3.1 Nˆe
´
u gi´a tri
.
cu

n ta
.
i luˆo
`
ng chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c trong G.
Ch´u
.
ng minh. B`ai tˆa
.
p. 
185
http://www.ebook.edu.vn
7.4 Luˆo
`
ng v´o
.
i chi ph´ı nho
˙’
nhˆa
´
t

n n`ay kha
˙’
o s´at b`ai to´an t`ım luˆo
`
ng v´o
.
i gi´a tri
.
v
cho tru
.
´o
.
c t`u
.
s d¯ˆe
´
n t sao cho chi ph´ı cu
˙’
a luˆo
`
ng l`a nho
˙’
nhˆa
´
t. Cu
.
thˆe
˙’
l`a:

n mˆo
.
t d¯o
.
n vi
.
h`ang trˆen cung
(i, j) ∈ E. T`ım luˆo
`
ng F := (f
ij
) c´o gi´a tri
.
v trˆen G v´o
.
i chi ph´ı nho
˙’
nhˆa
´
t; t´u
.
c l`a gia
˙’
i b`ai
to´an

(v
i
,v
j

n nhiˆen, b`ai to´an khˆong c´o l`o
.
i gia
˙’
i nˆe
´
u v l´o
.
n ho
.
n gi´a tri
.
l´o
.
n nhˆa
´
t cu
˙’
a luˆo
`
ng t`u
.
s
d¯ˆe
´
n t. Tuy nhiˆen, nˆe
´
u v nho
˙’
ho

.
.
” d¯ˆe
˙’
t`ım luˆo
`
ng v´o
.
i chi ph´ı nho
˙’
nhˆa
´
t. C´ac thuˆa
.
t to´an tr`ınh b`ay du
.
´o
.
i d¯ˆay du
.
.
a theo nh˜u
.
ng
kˆe
´
t qua
˙’
cu
˙’

.
t to´an Klein, Busacker, Gowen
Thuˆa
.
t to´an n`ay du
.
.
a v`ao viˆe
.
c x´ac d¯i
.
nh ma
.
ch c´o d¯ˆo
.
d`ai ˆam. Ch´ung ta h˜ay gia
˙’
thiˆe
´
t rˇa
`
ng tˆo
`
n
ta
.
i luˆo
`
ng chˆa
´

c bˇa
`
ng c´ach ´ap du
.
ng thuˆa
.
t to´an t`ım luˆo
`
ng l´o
.
n nhˆa
´
t v`a ch´ung ta tˇang luˆo
`
ng cho d¯ˆe
´
n khi
nhˆa
.
n d¯u
.
o
.
.
c luˆo
`
ng c´o gi´a tri
.
v.
V´o

.
i mˆo
˜
i cung (v
µ
i
, v
µ
j
) ∈ E
µ
1
, d¯ˇa
.
t c
µ
ij
:= c
ij
.
• v´o
.
i mˆo
˜
i cung (v
µ
j
, v
µ
i

.
i chi ph´ı nho
˙’
nhˆa
´
t nˆe
´
u v`a chı
˙’
nˆe
´
u khˆong tˆo
`
n ta
.
i ma
.
ch
Φ trong G
µ
(F ) sao cho tˆo
˙’
ng cu
˙’
a c´ac chi ph´ı cu
˙’
a c´ac cung thuˆo
.
c Φ ˆam.
Ch´u

ng ´u
.
ng v´o
.
i d¯ˆo
`
thi
.
G
µ
(F ).
D
-
iˆe
`
u kiˆe
.
n cˆa
`
n. Gia
˙’
su
.
˙’
c[Φ|G
µ
(F )] < 0 v´o
.
i ma
.

.
o
.
.
c
F + 1 ◦ (Φ) c´o gi´a tri
.
v. Chi ph´ı cu
˙’
a luˆo
`
ng F + 1 ◦ (Φ) bˇa
`
ng c[F ] + c[Φ|G
µ
(F )] < c[F ]-mˆau
thuˆa
˜
n v´o
.
i gia
˙’
thiˆe
´
t F l`a luˆo
`
ng v´o
.
i gi´a tri
.

(= F ) l`a
luˆo
`
ng gi´a tri
.
v c´o chi ph´ı nho
˙’
nhˆa
´
t.
Ta k´y hiˆe
.
u F
∗
− F l`a luˆo
`
ng m`a gi´a tri
.
trˆen cung (v
i
, v
j
) bˇa
`
ng f
∗
ij
− f
ij
.

unitary G
e
trong Phˆa
`
n 7.2.3 d¯ˆo
´
i v´o
.
i luˆo
`
ng F
∗
−F,
suy ra v´o
.
i mo
.
i d¯ı
˙’
nh v
i
∈ V ta c´o
d
+
G
∗
(v
i
) = d
−

∗
= F + 1 ◦ (Φ
1
) + 1 ◦ (Φ
2
) + · · · + 1 ◦ (Φ
κ
) l`a chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c nˆen tˆo
˙’
ng
F + 1 ◦ (Φ
1
) + 1 ◦ (Φ
2
) + · · · + 1 ◦ (Φ
l
) chˆa
´
p nhˆa
.
n d¯u

1
))] ≥ c[Φ
l
|G
µ
(F )]
v´o
.
i mo
.
i l = 1, 2, . . . , k.
Vˆa
.
y chi ph´ı cu
˙’
a luˆo
`
ng F + 1 ◦ (Φ
1
) + 1 ◦ (Φ
2
) l`a
c[F + 1 ◦ (Φ
1
) + 1 ◦ (Φ
2
)] = c[F + 1 ◦ (Φ
1
)] + c[Φ
2

-
iˆe
`
u n`ay mˆau thuˆa
˜
n v´o
.
i gia
˙’
thiˆe
´
t F
∗
l`a luˆo
`
ng
c´o chi ph´ı nho
˙’
nhˆa
´
t. 
Do d¯´o theo D
-
i
.
nh l´y 7.4.2, d¯ˆe
˙’
t`ım luˆo
`
ng chˆa

o
.
.
c c´o gi´a tri
.
v, thiˆe
´
t lˆa
.
p d¯ˆo
`
thi
.
G
µ
(F ) v`a kiˆe
˙’
m tra
c´o tˆo
`
n ta
.
i ma
.
ch c´o d¯ˆo
.
d`ai ˆam khˆong. Nˆe
´
u khˆong c´o th`ı luˆo
`

`
ng m´o
.
i vˆa
˜
n c´o gi´a tri
.
v v`a c´o chi ph´ı gia
˙’
m mˆo
.
t lu
.
o
.
.
ng δ.c(Φ), trong d¯´o c(Φ) l`a chi ph´ı
cu
˙’
a ma
.
ch c´o dˆo
`
d`ai ˆam Φ. Hiˆe
˙’
n nhiˆen δ cˆa
`
n d¯u
.
o

Theo c´ach cho
.
n ban d¯ˆa
`
u cu
˙’
a c´ac kha
˙’
nˇang cu
˙’
a d¯ˆo
`
thi
.
G
µ
(F ) luˆo
`
ng m´o
.
i nhˆa
.
n d¯u
.
o
.
.
c t`u
.
luˆo

.
p la
.
i v´o
.
i luˆo
`
ng m´o
.
i v`a vˆan vˆan. Chi tiˆe
´
t cu
˙’
a thuˆa
.
t to´an nhu
.
sau.
Thuˆa
.
t to´an t`ım luˆo
`
ng c´o chi ph´ı nho
˙’
nhˆa
´
t
1. Su
.
˙’

t
E
µ
1
:= {(v
µ
i
, v
µ
j
) | f
ij
< q
ij
, (v
i
, v
j
) ∈ E},
E
µ
2
:= {(v
µ
j
, v
µ
i
) | f
ij

1
∪ E
µ
2
,
• V´o
.
i mˆo
˜
i cung (v
µ
i
, v
µ
j
) ∈ E
µ
1
, d¯ˇa
.
t c
µ
ij
:= c
ij
.
• V´o
.
i mˆo
˜

.
G
µ
(F ) c´o tro
.
ng sˆo
´
W := (w
ij
), chuyˆe
˙’
n
sang Bu
.
´o
.
c 5. Ngu
.
o
.
.
c la
.
i, F l`a luˆo
`
ng v´o
.
i chi ph´ı nho
˙’
nhˆa

µ
ij
< 0 thay d¯ˆo
˙’
i luˆo
`
ng f
ji
trˆen cung (v
j
, v
i
) ∈ E
bo
.
˙’
i f
ji
− δ.
188
http://www.ebook.edu.vn
• V´o
.
i mo
.
i cung (v
µ
i
, v
µ

.
´o
.
c 2.
7.5 Cˇa
.
p gh´ep
7.5.1 C´ac b`ai to´an vˆe
`
cˇa
.
p gh´ep
C´ac b`ai to´an vˆe
`
cˇa
.
p gh´ep trong c´ac d¯ˆo
`
thi
.
(n´oi chung khˆong pha
˙’
i d¯ˆo
`
thi
.
hai phˆa
`
n) d¯u
.

`
thi
.
: c´ac b`ai
to´an t`ım h`anh tr`ınh tˆo
´
i u
.
u (nhu
.
b`ai to´an ngu
.
`o
.
i d¯u
.
a thu
.
Trung Hoa), x´ac d¯i
.
nh dˆay chuyˆe
`
n
ngˇa
´
n nhˆa
´
t trong d¯ˆo
`
thi

˙’
i bˇa
`
ng thuˆa
.
t to´an v´o
.
i d¯ˆo
.
ph´u
.
c ta
.
p d¯a th´u
.
c theo m v`a n (sˆo
´
c´ac
ca
.
nh v`a c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
).
X´et b`ai to´an sau xˆay du

˙’
a d¯ˆo
`
thi
.
G
p
thoa
˙’
m˜an t´ınh chˆa
´
t cho tru
.
´o
.
c.
B`ai to´an 7.5.1 (B`ai to´an d¯ˆo
`
thi
.
bˆo
.
phˆa
.
n c´o r`ang buˆo
.
c vˆe
`
d¯ı
˙’

j
∈ E. Ngo`ai ra, cho tru
.
´o
.
c c´ac sˆo
´
nguyˆen du
.
o
.
ng δ
i
, i = 1, 2, . . . , n. Vˆa
´
n d¯ˆe
`
d¯ˇa
.
t ra l`a t`ım mˆo
.
t d¯ˆo
`
thi
.
bˆo
.
phˆa
.
n G

, v`a tˆo
˙’
ng cu
˙’
a c´ac ca
.
nh trong G
∗
p
l´o
.
n nhˆa
´
t
(hoˇa
.
c nho
˙’
nhˆa
´
t).
Hiˆe
˙’
n nhiˆen, v´o
.
i d¯ˆo
`
thi
.
G v`a c´ac sˆo

d¯ı
˙’
nh. Hai d¯iˆe
`
u kiˆe
.
n cˆa
`
n (nhu
.
ng khˆong d¯u
˙’
-ta
.
i sao?) d¯ˆe
˙’
tˆo
`
n
ta
.
i d¯ˆo
`
thi
.
bˆo
.
phˆa
.
n chˆa

chˇa
˜
n.
D
-
iˆe
`
u kiˆe
.
n sau suy tru
.
.
c tiˆe
´
p t`u
.
t´ınh chˆa
´
t: tˆo
˙’
ng c´ac bˆa
.
c cu
˙’
a c´ac d¯ı
˙’
nh bˇa
`
ng hai lˆa
`

.
nh ngh˜ıa bo
.
˙’
i
c(M) =

e
j
∈M
c
j
.
Ta c´o b`ai to´an sau:
B`ai to´an 7.5.2 (B`ai to´an d¯ˆo
´
i s´anh v´o
.
i chi ph´ı l´o
.
n nhˆa
´
t) T`ım cˇa
.
p gh´ep M
∗
c´o chi ph´ı l´o
.
n
nhˆa


m
j=1
b
ij
x
j
≤ 1, i = 1, 2, . . . , n,
x
j
∈ {0, 1},
trong d¯´o b
ij
l`a ma trˆa
.
n liˆen thuˆo
.
c cu
˙’
a G v`a x
j
= 1 (hoˇa
.
c 0) phu
.
thuˆo
.
c v`ao e
j
c´o d¯u

tru
.
`o
.
ng ho
.
.
p d¯ˇa
.
c biˆe
.
t cu
˙’
a b`ai to´an c´o r`ang buˆo
.
c vˆe
`
bˆa
.
c cu
˙’
a c´ac d¯ı
˙’
nh. Nˆe
´
u sˆo
´
c´ac d¯ı
˙’
nh cu

G.
Khi d¯´o b`ai to´an d¯u
.
a vˆe
`
B`ai to´an 7.5.1 trˆen d¯ˆo
`
thi
.
G trong d¯´o tˆa
´
t ca
˙’
c´ac δ
i
= 1. Nghiˆe
.
m cu
˙’
a
b`ai to´an ban d¯ˆa
`
u dˆe
˜
d`ang suy ra t`u
.
b`ai to´an sau bˇa
`
ng c´ach bo
˙’

.
´o
.
c khi xˆay
du
.
.
ng d¯ˆo
`
thi
.
G v`a ´ap du
.
ng l´y luˆa
.
n trˆen.
Tu
.
o
.
ng ´u
.
ng v´o
.
i b`ai to´an t`ım cˇa
.
p gh´ep c´o chi ph´ı l´o
.
n nhˆa
´

c´o thˆe
˙’
ph´at biˆe
˙’
u da
.
ng quy hoa
.
ch nguyˆen nhu
.
sau:
z =
m

j=1
c
j
x
j
→ min
sao cho


m
j=1
b
ij
x
j
≥ 1, i = 1, 2, . . . , n,

v
3
v
4
v
5
v
6
v
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• •
• •
•
v
1
v
2
v
3
v
4
v
5
v
6
v
7

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

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

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

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

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

.

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

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.

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

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

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

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

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

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
H`ınh 7.4: (a) Cˇa
.
p gh´ep. (b) Phu
˙’
.

.
c v˜e bˇa
`
ng d¯oa
.
n n´et d¯´u
.
t trong c`ung d¯ˆo
`
thi
.
.
Trong tru
.
`o
.
ng ho
.
.
p tˆa
´
t ca
˙’
c´ac ca
.
nh c´o chi ph´ı bˇa
`
ng nhau (chˇa
˙’
ng ha

.
c l`a t`ım cˇa
.
p gh´ep c´o sˆo
´
ca
.
nh nhiˆe
`
u nhˆa
´
t v`a b`ai to´an t`ım phu
˙’
nho
˙’
nhˆa
´
t
tu
.
o
.
ng ´u
.
ng. Nˆe
´
u d¯ˆo
`
thi
.

.
o
.
.
c; chˇa
˙’
ng ha
.
n, d¯ˆo
`
thi
.
“h`ınh
sao” trong H`ınh 7.5 c´o cˇa
.
p gh´ep l´o
.
n nhˆa
´
t v´o
.
i sˆo
´
phˆa
`
n tu
.
˙’
1.
Tru

`
b`ai to´an phˆan cˆong cˆong viˆe
.
c, mˆo
.
t b`ai to´an quen
thuˆo
.
c cu
˙’
a Vˆa
.
n tr`u ho
.
c. V´o
.
i cˆa
´
u tr´uc d¯ˆo
`
thi
.
d¯ˇa
.
c biˆe
.
t n`ay, B`ai to´an 7.5.1 tro
.
˙’
th`anh b`ai to´an

.
v´o
.
i b`ai to´an luˆo
`
ng l´o
.
n nhˆa
´
t. Vˆe
`
c´ac thuˆa
.
t to´an gia
˙’
i quyˆe
´
t c´ac
b`ai to´an cˇa
.
p gh´ep trong tru
.
`o
.
ng ho
.
.
p tˆo
˙’
ng qu´at c´o thˆe

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

`
thi
.
h`ınh sao.
7.5.2 Cˇa
.
p gh´ep l´o
.
n nhˆa
´
t trong d¯ˆo
`
thi
.
hai phˆa
`
n
Tru
.
´o
.
c hˆe
´
t ta bˇa
´
t d¯ˆa
`
u bˇa
`
ng mˆo

su
.
˙’
G = (V, E) l`a d¯ˆo
`
thi
.
hai phˆa
`
n m`a c´ac d¯ı
˙’
nh l`a
V = V
1
∪ V
2
, v´o
.
i V
1
= {1, 2, . . . , p} v`a V
2
= {1, 2, . . . , q} v`a c´o mˆo
.
t ca
.
nh liˆen thuˆo
.
c (i, j) nˆe
´

˙’
thu
.
.
c hiˆe
.
n. D
-
iˆe
`
u d¯´o c´o ngh˜ıa rˇa
`
ng, t`ım trong G mˆo
.
t cˇa
.
p gh´ep c´o sˆo
´
phˆa
`
n tu
.
˙’
bˇa
`
ng p.
B`ai to´an cˇa
.
p gh´ep c´o thˆe
˙’

.
c tˆa
.
p V
1
v`a t`u
.
c´ac d¯ı
˙’
nh thuˆo
.
c tˆa
.
p
V
2
d¯ˆe
´
n t. G´an mˆo
˜
i cung trong d¯ˆo
`
thi
.
thu d¯u
.
o
.
.
c, k´y hiˆe

thi
.
hai phˆa
`
n d¯i
.
nh hu
.
´o
.
ng v´o
.
i c´ac tˆa
.
p d¯ı
˙’
nh r`o
.
i nhau V
1
v`a
V
2
m`a trong d¯´o c´ac ca
.
nh d¯u
.
o
.
.

n ta
˙’
i G
M
cho ta mˆo
.
t cˇa
.
p gh´ep trong G. D
-
ı
˙’
nh v
i
∈ V
1
d¯u
.
o
.
.
c d¯ˆo
´
i
s´anh v´o
.
i d¯ı
˙’
nh v
j

.
i cˇa
.
p gh´ep l´o
.
n nhˆa
´
t.
3. Luˆo
`
ng c´o gi´a tri
.
bˇa
`
ng #V
1
tu
.
o
.
ng ´u
.
ng v´o
.
i cˇa
.
p gh´ep ho`an ha
˙’
o.
Ch´u

`
ng 1. Do luˆo
`
ng ra kho
˙’
i d¯ı
˙’
nh v
i
bˇa
`
ng 1 nˆen c´o d¯´ung mˆo
.
t cung c´o da
.
ng
192
http://www.ebook.edu.vn
(v
i
, x) c´o f
ix
= 1 l`a (v
i
, v
j
). Tu
.
o
.

= 1 th`ı hai ca
.
nh bˆa
´
t k`y trong M khˆong kˆe
`
nhau.
N´oi c´ach kh´ac M l`a cˇa
.
p gh´ep cu
˙’
a G.
C´ac phˆa
`
n c`on la
.
i suy t`u
.
sˆo
´
c´ac d¯ı
˙’
nh cu
˙’
a V
1
d¯u
.
o
.

.
ng thuˆa
.
t to´an t`ım luˆo
`
ng l´o
.
n nhˆa
´
t d¯ˆe
˙’
x´ac d¯i
.
nh
cˇa
.
p gh´ep l´o
.
n nhˆa
´
t cu
˙’
a d¯ˆo
`
thi
.
hai phˆa
`
n.
7.5.3 Cˇa

2
, E) l`a cˇa
.
p gh´ep
m`a mˆo
˜
i d¯ı
˙’
nh a ∈ V
1
tˆo
`
n ta
.
i b ∈ V
2
sao cho (a, b) ∈ E.
Nˆe
´
u S ⊂ V
1
, ta d¯ˇa
.
t
Γ(S) := {v
j
∈ V
2
| tˆo
`

ng nˆe
´
u #S ≤ #Γ(S) v´o
.
i mo
.
i tˆa
.
p con S cu
˙’
a V
1
th`ı G c´o mˆo
.
t cˇa
.
p gh´ep ho`an
ha
˙’
o. Kˆe
´
t qua
˙’
n`ay d¯u
.
o
.
.
c ch´u
.

p nh˜u
.
ng ngu
.
`o
.
i d¯`an b`a v`a tˆo
`
n ta
.
i ca
.
nh nˆo
´
i v
i
∈ V
1
d¯ˆe
´
n
v
j
∈ V
2
nˆe
´
u v
i
v`a v

i
.
nh l´y 7.5.6 Tˆo
`
n ta
.
i cˇa
.
p gh´ep ho`an ha
˙’
o nˆe
´
u v`a chı
˙’
nˆe
´
u
#S ≤ #Γ(S) (7.2)
v´o
.
i mo
.
i tˆa
.
p con S cu
˙’
a V
1
.
Ch´u

v`a (P,
˜
P ) l`a thiˆe
´
t diˆe
.
n nho
˙’
nhˆa
´
t trong ma
.
ng vˆa
.
n ta
˙’
i. Nˆe
´
u ta ch´u
.
ng
minh rˇa
`
ng kha
˙’
nˇang cu
˙’
a thiˆe
´
t diˆe

ng l´o
.
n nhˆa
´
t s˜e l`a cˇa
.
p gh´ep ho`an ha
˙’
o.
193
http://www.ebook.edu.vn
Ch´u
.
ng minh bˇa
`
ng pha
˙’
n ch´u
.
ng. Gia
˙’
su
.
˙’
ngu
.
o
.
.
c la

a thiˆe
´
t diˆe
.
n n`ay bˇa
`
ng sˆo
´
c´ac ca
.
nh trong tˆa
.
p
M = {(x, y) | x ∈ P, y ∈
˜
P }.
Mˆo
.
t phˆa
`
n tu
.
˙’
cu
˙’
a M c´o mˆo
.
t trong ba da
.
ng:

∈ V
2
.
Ch´ung ta s˜e d¯ˆe
´
m sˆo
´
c´ac ca
.
nh trong mˆo
˜
i loa
.
i.
Nˆe
´
u V
1
∈
˜
P th`ı kha
˙’
nˇang cu
˙’
a thiˆe
´
t diˆe
.
n l`a n
1

p ho
.
.
p
X = R(V
∗
1
) ∩ P v`a Y = R(V
∗
1
) ∩
˜
P .
Khi d¯´o tˆo
`
n ta
.
i ´ıt nhˆa
´
t #V
∗
1
ca
.
nh loa
.
i 3 trong E. Do d¯´o tˆo
`
n ta
.

´
t mˆo
.
t ca
.
nh loa
.
i 2, nˆen
#Y < # V
∗
1
− #X.
Vˆa
.
y
#R(V
∗
1
) = #X + #Y < #V
∗
1
.
D
-
iˆe
`
u n`ay mˆau thuˆa
˜
n v´o
.

.
ng th´ıch v´o
.
i m m´ay t´ınh. C´o thˆe
˙’
gh´ep mˆo
˜
i m´ay t´ınh v´o
.
i mˆo
.
t ˆo
˙’
d¯˜ıa m`a n´o tu
.
o
.
ng
th´ıch?
D
-
ˇa
.
t V
1
l`a tˆa
.
p c´ac m´ay t´ınh v`a V
2
l`a tˆa

d¯˜ıa v
j
∈ V
2
. Ch´u ´y rˇa
`
ng mo
.
i d¯ı
˙’
nh c´o bˆa
.
c bˇa
`
ng m. D
-
ˇa
.
t
194
http://www.ebook.edu.vn
S = {v
1
, v
2
, . . . , v
k
} ⊂ V
1
. Khi d¯´o c´o km ca

´o
.
i Hall, tˆo
`
n ta
.
i cˇa
.
p gh´ep ho`an ha
˙’
o. Vˆa
.
y c´o thˆe
˙’
gh´ep mˆo
˜
i m´ay t´ınh v´o
.
i
mˆo
.
t ˆo
˙’
d¯˜ıa tu
.
o
.
ng th´ıch.
195