Đồ thị và các thuật toán - Chương 7

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

74
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 7 Mạng vận tải

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ thị và các thuật toán - Chương 7

Chu.o.ng 7 ˙ ’ Mang vˆn tai a . . Mo. d` u ˙ ¯ˆ ’a 7.1 Mˆt trong nh˜.ng b`i to´n l´ th´ v` quan trong cua l´ thuyˆt d` thi l` x´c d inh gi´ tri l´.n ´o ˙y ’ o u a a y ua e ¯ˆ . a a ¯. a .o . . ´t cua luˆng d u.o.c truyˆn t`. mˆt d ınh nguˆn s cua d` thi dˆn mˆt d ınh d´ t. Trong ` ` u o ¯˙ ` ´ ˙ ’ ’ ˙ ¯o . ¯e ’ ˙ ’ nhˆ a o ¯. e o ˆ o¯ ¯ıch . . khung canh d o, mˆ i cung (vi , vj ) cua d` thi G d u.o.c gˇn v´.i mˆt kha nˇng thˆng qua qij l` ˜ ´ ˙ ’ ˙ ¯o . ’ˆ ˙a ’ ¯´ o ¯. a o o o a . .o.ng luˆng l´.n nhˆ t c´ thˆ’ tai qua cung n`y. B`i to´n n`y v` nh˜.ng cai biˆn cua n´ ˙˙ ´ ` ´ ao e’ ˙ ’ ˙o ’ sˆ lu . o o o a a aaau e ´t nhiˆu u.ng dung trong thu.c tˆ, chˇng han, x´c d .nh mˆt d o giao thˆng l´.n nhˆ t gi˜.a ˙ ’ `´ ´a ´u c´ rˆ oa e .e a ¯i a ¯ˆ o o a . . .. hai v`ng trong ban d` giao thˆng d u.o.c biˆ’u diˆn bo.i mˆt d` thi. Trong v´ du n`y, l`.i giai ˙ ˜ ˙ ¯ˆ ’ ˙ ’ ˙’ u o o ¯. e e o ¯ˆ . o ı.ao . ` ng l´.n nhˆ t c˜ng chı ra nh˜.ng no.i “bao ho`” trˆn mang giao thˆng v` tao ´u ˙aa ’ ˙ ’ ˙ ’ cua b`i to´n luˆ o o a u a e o a. . mˆt “tˇc ngh˜n” khi luˆng tˆp trung v`o gi˜.a hai vi tr´ n`o d o. ´ ` o a e o a a u ı a ¯´ . . . Phu.o.ng ph´p giai b`i to´n luˆng l´.n nhˆ t t`. s dˆn t d u.a ra lˆn d` u tiˆn bo.i Ford ` ´ ´ ` ¯ˆ ˙a ’ ˙ ’ a a o o a u ¯e ¯ a a e ˙ a ho l` co. so. cho nh˜.ng thuˆt to´n kh´c giai ’ ˙ ’ ˙ ’ v` Fulkerson [27] v` k˜ thuˆt “g´n nh˜n” cu a ay a a a .a u a a a . . .ng vˆ n d` liˆn quan. C´ mˆt sˆ cai biˆn cua b`i to´n luˆng l´.n nhˆ t: ´ ´e . ´’ e ˙ a a ` ´ ooo˙ ’ quyˆt nh˜ e u a ¯ˆ e o o a 1. Gia su. rˇ ng mˆ i cung cua d` thi khˆng chı d u.o.c gˇn v´.i kha nˇng qij cho biˆt cˆn trˆn ˙˙` ˜ ´ ´. ’’a ˙ ¯o . o ’ˆ ˙¯ . a o ’ ˙a ’ o ea e .´.i cua luˆng trˆn cung ` ` cua luˆng trˆn cung (vi , vj ) m` c`n “kha nˇng” rij cho cˆn du o ˙ ˙ ’ ˙a ’ ’ o e ao a o e . .`.ng ho.p nhu. vˆy, khˆng phai l´c n`o mˆt tˆp chˆ p nhˆn d u.o.c c´c gi´ ´ ˙u a ’ n`y. Trong tru o a a o oa a a¯. a a . . .. . ` ` ˙ ’ ˙au ’ tri cua luˆng c˜ng thoa m˜n c`ng l´c hai r`ng buˆc n`y. Tuy nhiˆn-n´i chung-nhiˆu o u u a oa eo e . . luˆng thoa d iˆu kiˆn n`y, v` nˆu ngo`i c´c kha nˇng c`n c´ c´c chi ph´ cij tu.o.ng u.ng ` ˙ ¯` ´ ’e ˙a ’ o ea ae aa o oa ı ´ . mˆt d o.n vi luˆng doc theo c´c cung, th` b`i to´n tro. th`nh t` luˆng chˆ p nhˆn d u.o.c ` ım ` ´ ˙a ’ o¯ o a ıa a o a a¯. . . . . v´.i chi ph´ nho nhˆ t t`. s dˆn t. ´ ´ ˙ ’ a u ¯e o ı 2. X´t tru.`.ng ho.p d `i hoi luˆng l´.n nhˆ t gi˜.a moi cˇp d ınh. Mˇc d` b`i to´n n`y c´ . ¯o ˙ ` ´u ’ . a ¯˙ ’ e o o o a a ua aao . . thˆ’ giai bˇ ng n(n − 1)/2 lˆn lˇp c´c b`i to´n luˆng l´.n nhˆ t t`. s dˆn t nhu.ng c´ch ˙’a e˙` `aaa ` ´ ´ a. a o o a u ¯e a .o.ng tu. v´.i t` tˆ t ca c´c d u.`.ng d i ngˇn nhˆ t, o. d ˆy c˜ng cˆn ´ ´’ ´’ ` . o ım a ˙ a ¯ o a ˙ ¯a u l`m n`y qu´ thˆ! Tu a a ao ¯ a a http://www.ebook.edu.vn 173
mˆt thuˆt to´n chuyˆn dung dˆ’ giai n´-v` trong tru.`.ng ho.p d` thi vˆ hu.´.ng, phu.o.ng ˙’ ¯e ˙ o a o a a e o . ¯ˆ . o o o . . . ph´p giai quyˆt n´ khˆng liˆn quan dˆn l`.i giai cua b`i to´n luˆng l´.n nhˆ t gi˜.a hai ´ ´ ` ´u ˙ ’ ˙˙aa ’’ a eoo e ¯e o o o a ¯˙’ d ınh s v` t. a ´ ` a o ¯˙ ¯ıch, .´ ` aoo .´ o ¯˙ .’ .’ ˙a ’ 3. Nˆu thay cho mˆt d ınh nguˆn v` mˆt d ınh d´ ta khao s´t mˆt sˆ nguˆn v` mˆt sˆ e o oo o .i c´c h`ng ho´ kh´c nhau gi˜.a hai tˆ’ ho.p nguˆn-d´ kh´c nhau, th` b`i to´n ˙. ` ¯ıch a d´ v´ a a ¯ıch, o aa u o o ıa a cu.c d ai tˆ’ng sˆ tˆ t ca c´c luˆng t`. c´c nguˆn dˆn c´c d´ l` b`i to´n luˆng d a-h`ng ˙ oa ˙a ` ´´ ’ ` ¯e a ¯ıch a a a o´ ` ¯. o o ua o¯a . ho´. Trong b`i to´n n`y, kha nˇng qij cua cung (vi , vj ) l` cˆn trˆn cua tˆ’ng c´c luˆng ˙ a` ˙a ’ ˙ ’ e˙o ’ a aaa aa o . .i c´c loai h`ng ho´ trˆn cung d ´. v´ a o .a ae ¯o 4. Gia thiˆt (ˆ’n) trong tˆ t ca c´c tru.`.ng ho.p trˆn l` sˆ lu.o.ng luˆng dˆn bˇ ng sˆ lu.o.ng ´˙ o ¯e ` ´’ ´ ` ´a ´ ˙’ a ˙a ea o e ao . o. . .`.ng ho.p luˆng ra khoi mˆt cung bˇ ng ` ` ´ ´ ` ˙˙ ’’ ˙ ’ luˆng ra. Nˆu ta bo gia thiˆt n`y v` x´t tru o o e e a ae o o a . . .i mˆt sˆ nguyˆn khˆng ˆm n`o d o, th` b`i to´n luˆng l´.n nhˆ t (t`. ` ´ .´ ` ´ luˆng dˆn nhˆn v´ o o o ¯e ao e oa a ¯´ ıa a o o au ´n t) d u.o.c xem nhu. b`i to´n trong c´c d` thi v´.i c´c lo.i nhuˆn. Trong dang n`y, s dˆ ¯e ¯. aa a ¯ˆ . o a . o a a . . c´c luˆng c´ thˆ’ “d u.o.c sinh ra” hoˇc “bi hˆ p thu” bo.i d` thi, v` do vˆy luˆng v`o s ˙ a` ´ ` ˙ ¯o . a ’ˆ o o e¯. a a a o a . . . . v` luˆng ra khoi t c´ thˆ’ thay d ˆ’i ho`n to`n d oc lˆp. ˙ ˙ a` ˙ ’ o oe ¯o a a ¯ˆ a.. C´c b`i to´n vˆ luˆng d u.o.c nghiˆn c´.u nhiˆu v` c´ nh˜.ng u.ng dung thu.c tiˆn. Muc ˜ aaa`` ` e o ¯. eu e ao u ´ e . . . .o.ng n`y tr` b`y ngˇn gon c´c b`i to´n thu.`.ng gˇp, chı ra mˆi liˆn hˆ gi˜.a ´.aaa ´e eu ¯ıch ˙’ ˙ ’ d´ cua chu a ınh a a o a o . . ch´ng v` xˆy du.ng mˆt sˆ thuˆt to´n giai quyˆt. .´ ´ ˙ ’ u aa oo a a e . . Chu.o.ng n`y s˜ thao luˆn b`i to´n luˆng l´.n nhˆ t t`. s dˆn t v` c´c tˆ’ng qu´t ho´ cua ˙ ` ´ ´ ae˙ ’ a˙ ’ aaa o o a u ¯e aa o a . ` ´ ˙ i b`i to´n luˆng d a-h`ng ho´ rˆ t kh´c biˆt ’aa n´ (1), (2), (3) v` (4) trˆn. Do c´c thuˆt to´n gia o a e a a a o¯a aa a e . . vˆ ban chˆ t, v` khˆng phai d` u hiˆu qua nhu. phu.o.ng ph´p g´n nh˜n, nˆn s˜ khˆng d u.o.c `˙ ´ao e’ ˙ ¯ˆ ’e ˙ ’ a e aa a e e o ¯. . d` cˆp o. d ay. Ban d oc quan tˆm c´ thˆ’ xem [30] v` c´c t`i liˆu dˆ n k`m theo. ˙ ˜ ¯ˆ a ˙ ¯ˆ e.’ . ¯. a oe aa a e a e . B`i to´n luˆng l´.n nhˆ t ` ´ 7.2 a a o o a Luˆng l´.n nhˆ t trˆn mang vˆn tai G l` mˆt luˆng v´.i gi´ tri l´.n nhˆ t. N´i chung c´ mˆt ` ´e ao` ´ a˙ ’ o o a o o a .o a o oo . . . . .i c`ng gi´ tri l´.n nhˆ t. Phˆn n`y tr` b`y thuˆt to´n t` luˆng l´.n nhˆ t. Y a´ a` ´ ` a ım ` ´ v`i luˆng v´ u o o a .o a aa ınh a a o o . tu.o.ng cua thuˆt to´n l`: kho.i d` u v´.i luˆng n`o d o v` tˇng gi´ tri cua luˆng cho dˆn khi ˙ ¯a o ` ` ´ ˙ ’ ˙ ’ ’ˆ a.˙ ’ a aa o a ¯´ a a o ¯e . .o.c n˜.a. Kˆt qua ta c´ luˆng l´.n nhˆ t. khˆng thˆ’ tˇng d u . u ˙ ´ o` ´ ˙ ’ o ea ¯ e o o a V´ du 7.2.1 D` thi c´ hu.´.ng trong H` 7.1 biˆ’u diˆn so. d` mang dˆn dˆu. Dˆu d u.o.c -ˆ . o o ˙ ˜ ˜a a` ` ¯. ı. o ınh e e ¯ˆ . o a . t`u s v` d u.o.c bo.m thˆng qua mang dˆn nh` m´y loc dˆu t. C´c d ınh b, c, d v` e l` ˜ ´ aa.` a ¯˙ ’ dˆn t` a au a¯ . o ¯e a aa . .m trung gian. C´c cung biˆ’u thi c´c ˆng dˆ n dˆu v` hu.´.ng di chuyˆ’n cua hˆ ˙ ˙˙e ˜` ´ ’ c´c tram bo a a e .ao aaao e . . ˜ ´ ´ ’´ ˙a ’ o¯ ˙o thˆng. C´c nh˜n trˆn c´c cung l` kha nˇng thˆng qua tˆi d a cua ˆng dˆn. B`i to´n d at ra o a a ea a o a a a ¯ˇ . l` t` c´ch chuyˆ’n nhiˆu nhˆ t lu.o.ng dˆu t`. t`u dˆn nh` m´y v` t´ gi´ tri n`y. H` 7.1 ˙ ` ´ ` u a ¯e ´ a ım a e e a a a a a ınh a . a ınh . l` mˆt v´ du cua mˆt “mang vˆn tai”. Tru.´.c hˆt ta c´: ´ aoı.˙ ’ a˙ ’ o oe o . . . . http://www.ebook.edu.vn 174
c 2 b • • ..................................................... ...................................................... ... . ................................................................................................................ .. .. ... . . ... ... ... .... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... .. 3 4 . . ... ... ... ... ... ... .. . . ... ... ... ... ... .... .. . . ... .. .... ... ... ... .... .. . .. .... . .... ... ... ... . .. ... .. . . .... ... ... ... ... ... .. . ... . ... ... ... ... ... ... .. . ... . ... ... ... ... ... ... .. . . 2 ... ... ... ... ... ... .. . . ... ... ... ... ... ... .. . . ... s• •t ... ... ... ... ... ...... . .. . ... . ... ... .... ... . .. ... . ... ... ... ... ... ... .. ... . . ... ... ... ... ... ... .. . . ... ... ... ... ... ... ... .. ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. ... ... ..... ... ... ... .. . .. . .... ... .... ... ... . ... ... ... ... . ... ... ... ... ... ... 5 4 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 2 ... ... ... ... ... .. . . ... ... ... ... ... ... ... ...... ... ......... ... • • ............................................................................................................ .. . ............................................................................................................. .. e d ı.` . a˙ ’ H` 7.1: V´ du vˆ mang vˆn tai. ınh e . Dinh ngh˜ 7.2.2 Mang vˆn tai l` mˆt d o.n d` thi c´ hu.´.ng, c´ trong sˆ G sao cho -. ´ a ˙a o¯ ’ ıa ¯o . o o ˆ o. o . . . ` o o a ˙ o ¯˙ ’.’ . a ¯˙ ’ a ¯˙ ’ ˙ ’ (a) c´ mˆt v` chı mˆt d ınh s, goi l` d ınh v`o (hoˇc d ınh nguˆn) cua mang, khˆng c´ cung a o o o . . . ´ dˆn n´. ¯e o o o a ˙ o ¯˙’.’ . a ¯˙ ’ a ¯˙ ¯ıch) cua mang, khˆng c´ cung d i ’ ˙ ’ (b) c´ mˆt v` chı mˆt d ınh t, goi l` d ınh ra (hoˇc d ınh d´ o o ¯ . . . ˙o ’ ra khoi n´. (c) mˆ i cung u := (vi , vj ) ∈ E d u.o.c g´n mˆt sˆ nguyˆn khˆng ˆm qij , goi l` kha nˇng cua ˜ .´ ˙a ’ ˙ ’ o ¯. a oo e oa .a cung u. (d) d` thi vˆ hu.´.ng nhˆn d u.o.c t`. G bˇ ng c´ch bo d i c´c hu.´.ng l` liˆn thˆng. ` ˙¯ a ’ ¯ˆ . o o o a¯. u a a o ae o . V´ du 7.2.3 D` thi c´ hu.´.ng trong H` 7.1 l` mang vˆn tai. Lˆi v`o l` d ınh s v` lˆi ra -ˆ . o o ´ ´ a˙ ’ o a a ¯˙ ’ ı. o ınh a. ao . a ¯˙’ ˙a ’ a˙’ l` d ınh t. Kha nˇng cung (s, b) l` qsb = 3 v` cua cung (b, c) l` qbc = 2. a a Trong chu.o.ng n`y, nˆu G l` mang vˆn tai ch´ng ta s˜ k´ hiˆu d ınh v`o l` s v` d ınh ´ a˙ ’ e y e ¯˙ ’ a ¯˙’ a e a. u aa . . ra l` t. a Dinh ngh˜ 7.2.4 Gia su. G l` mang vˆn tai v´.i kha nˇng cung (vi , vj ) l` qij . Luˆng (chˆ p -. ` ´ ˙˙ ’’ a˙o ’ ˙a ’ ıa a. a o a . .o.c) F trong G g´n mˆi cung (v , v ) mˆt sˆ khˆng ˆm f sao cho ˜ .´ nhˆn d u . a¯ a o oooa . ij ij (a) 0 ≤ fij ≤ qij ; v` a (b) v´.i mˆi d ınh vj = s, t, ta c´ ˜’ o o ¯˙ o fij = fji . (7.1) i i http://www.ebook.edu.vn 175
(Tˆ’ng trong (7.1) lˆ y trˆn tˆ t ca c´c gi´ tri i; nˆu khˆng c´ cung (vi , vj ), ta d ˇt fij = 0). ˙ ´ ´’ ´ e a ˙a o a a. e o o ¯a. Ta n´i fij l` luˆng trˆn cung (vi , vj ). V´.i mˆ i j, ta goi ˜ a` o o e oo . fij i a` ´’ o ¯e ¯˙ l` luˆng dˆn d ınh vj v` a fij i a` ˙ ¯˙ ’’ l` luˆng ra khoi d ınh vj . o -` ˜a˙ ` ı.a ` ` .a˙ ’ ’ ˙ ’ Diˆu kiˆn (7.1) goi l` bao to`n luˆng. Trong v´ du dˆn dˆu cua H` 7.1, bao to`n luˆng c´ e e a o ınh a o o . .o.c su. dung v` c˜ng khˆng d u.o.c cˆ p thˆm tai c´c tram bo.m b, c, d v` e. ıa ` ´ ngh˜ dˆu khˆng d u . ˙ . ’ a o¯ au o ¯. a e a a . . V´ du 7.2.5 C´c ph´p g´n ı. a ea fsb = 2, fbc = 2, fcz = 3, fsd = 3, fdc = 1, fde = 2, fez = 2, ˙ ’ ` ` ´’ a˙˙ ’’ o ¯e ¯ ˙ x´c d .nh luˆng trˆn mang vˆn tai cua H` 7.1. Chˇng han, luˆng dˆn d ınh d l` a ¯i o e ınh a a . . . fsd = 2, ` ` ˙ ¯˙ ’’ bˇ ng luˆng ra khoi d ınh d : a o fdc + fde = 1 + 2 = 3. Luˆng F d u.o.c v˜ trong H` 7.2, trong d o cung e d u.o.c g´n nh˜n x, y nˆu kha nˇng cua e ` ´ ˙a ’ ˙ ’ o ¯. e ınh ¯´ ¯. a a e ` ng trˆn e l` y. l` x v` luˆ a ao e a c 2, 2 b • • ............................................................................................................. ............................................................................................................... .. .. .. ... . . .. . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... 3, 2 4, 3 . .. . ... ... ... ... ... ... . .. . ... ... ... ... ... ... . .... .. . ... ... .... ... ... ... .... . . .. . . .... ... .... ... ... ... . .. . .... .... ... ... ... ... .. . . ... ... ... ... ... ... .. ... . . ... ... ... ... ... ... .. . ... 2, 1 . ... ... ... ... ... ... .. . . ... ... ... ... ... ... .. . . ... ... ... ... ... s• •t ... .. . . ...... ..... . ... ... ... . ... .. . ... . ... ... ... ... . .. .. . ... ... ... ... ... ... .. ... . . ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. ... ... ... ..... ... ... .. . ... ... ... ... ... ... . ... . ... .... ... .... ... ... ... ... ... 5, 3 4, 2 ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... 2, 2 ... ... ... ... ... ... . .. ... . ... ... ... ... ... ... ... ... ...... ... ......... • • .............................................................................................................. ............................................................................................................ . .. .. e d ` a˙˙ ’’ H` 7.2: Luˆng trˆn mang vˆn tai cua H` 7.1. ınh o e ınh . . http://www.ebook.edu.vn 176
u´ ` ` ˙ ¯˙ ’’ Ch´ y rˇ ng trong v´ du n`y, luˆng ra khoi d ınh s l` a ı.a o a fsb + fsd ` ` ´’ o ¯e ¯˙ bˇ ng luˆng dˆn d ınh t : a fct + fet ` v` bˇ ng 5. Thˆt vˆy, ta c´ aa aa o .. Dinh l´ 7.2.6 Gia su. F l` luˆng trˆn mang vˆn ta i G := (V, E ). Khi d ´ luˆng ra kho i -. a` ¯o ` ˙˙ ’’ a˙’ ˙ ’ y o e o . . .c l` ` ` ¯e ¯ ˙ ´ d ı’nh s bˇ ng luˆng dˆn d ı’nh t; t´ a ¯˙ a o u fsi = fit . i i Ch´.ng minh. Ta c´ u o fij = fji j ∈V i∈V j ∈V i∈V oe` ˜ ´a do mˆ i vˆ bˇ ng fe . V` vˆy ıa . e∈E 0= ( i∈V fij − i∈V fji ) j ∈V =( i∈V fit − i∈V fti ) + ( i∈V fis − fsi ) + ( fij − fji ) i∈V j ∈V,j =s,t i∈V i∈V = i∈V fit − i∈V fsi do fti = 0 = fis v´.i moi vi ∈ V, v` (7.1). o a . Dinh ngh˜ 7.2.7 Gia su. F l` luˆng trˆn mang vˆn tai G. Dai lu.o.ng -. -. a` ˙˙ ’’ a˙ ’ ıa o e . . . fsi = fit i i ` .aa.˙ ’ goi l` gi´ tri cua luˆng F. o B`i to´n trˆn mang vˆn tai G c´ thˆ’ ph´t biˆ’u: ˙ ˙ a˙ ’ aa e oea e . . B`i to´n 7.2.8 T`m mˆt luˆng chˆ p nhˆn d u.o.c l´.n nhˆ t trˆn d` thi G; t´.c l` trong sˆ tˆ t o` ´ ´ ´´ a a ı o a a¯. o a e ¯ˆ . o ua oa . . .n nhˆ t. ˙a ` ` ´ ’ ca c´c luˆng trˆn G, t`m luˆng F c´ gi´ tri l´ o e ı o o a .o a Thuˆt to´n g´n nh˜n cua Ford v` Fulkerson [27] giai b`i to´n n`y du.a trˆn Dinh l´ e -. ˙ ’ ˙a ’ a aa a a aa y . . .´.c hˆt ta c´ mˆt sˆ kh´i niˆm ´ .´ 7.2.10. Tru o e oooae . http://www.ebook.edu.vn 177
Dinh ngh˜ 7.2.9 Nˆu c´c d ınh cua d` thi G = (V, E ) d u.o.c phˆn hoach th`nh hai tˆp con -. ´ e a ¯˙ ’ ˙ ¯o . ’ˆ ıa ¯. a a a . . V0 v` V0 (trong d o V0 ⊂ V v` V0 l` phˆn b` cua V0 trong V ), th` tˆp c´c cung cua G v´.i a˜ a˜ a ` a u˙ ’ ˙ ’ ¯´ ıa a o . ˜0 goi l` thiˆt diˆn cua G. Tˆp c´c cung ´ ´ ´e ¯˙’ a ¯˙’ ˙ ’ d ınh xuˆ t ph´t thuˆc V0 v` d ınh kˆt th´c thuˆc V . a a a o e u o e aa . . . . ˙ a thiˆt diˆn thu.`.ng d u.o.c k´ hiˆu bo.i (V0 → V0 ). ˜ ´e ’ ˙ ’ cu e o ¯. y e . . Gia su. G l` mang vˆn tai. Thiˆt diˆn (V0 → V0 ) t´ch s khoi t nˆu s ∈ V0 v` t ∈ V0 . ˜a ˜ ´e ´ ˙˙ ’’ a˙ ’ ˙ ’ a. e e a . . Kha nˇng thˆng qua hay gi´ tri cua thiˆt diˆn l` tˆ’ng cua tˆ t ca c´c kha nˇng cua tˆ t ca ˙ ´ e ao ’´’ ’´’ ˙a ’ a.˙ ’ ˙ a ˙a ˙a ’ ˙a˙ o e . .i d ınh xuˆ t ph´t thuˆc V v` d ınh kˆt th´c thuˆc V ; t´.c l` o ˜0 u a ´ ´ c´c cung cua G v´ ¯˙ ˙ ’ o’ o 0 a ¯˙ ’ a a a e u . . ˜ v (V0 → V0 ) := qij . ˜ (vi ,vj )∈(V0 →V0 ) ´e ´ ´eo ´ ˙ ’ aa ˙a ’ ˙ ’a Thiˆt diˆn nho nhˆ t l` thiˆt diˆn c´ kha nˇng thˆng qua nho nhˆ t. e e o . . Dinh l´ 7.2.10 (Dinh l´ thiˆt diˆn nho nhˆ t-luˆng l´.n nhˆ t) Gi´ tri cu a luˆng l´.n nhˆ t -. -. ´e ’a` ´o ´ ` ´ ˙ a.˙ ’ y y e o a o o a . . s dˆn t bˇ ng kha nˇng thˆng qua cu a thiˆt diˆn nho nhˆ t (V → V ) t´ch s kho i t. ˜m a ` ´ ´e ´ ˙a ’ ˙ ’ ˙ ’a ˙’ t` ¯e u a o e . m Ch´.ng minh. Hiˆ’n nhiˆn rˇ ng, luˆng l´.n nhˆ t t`. s dˆn t khˆng thˆ’ l´.n ho.n v (Vm → Vm )˜ ˙ ˙ e` ` ´ ´ u e a o o a u ¯e o eo .`.ng d i t`. s dˆn t d` u su. dung ´ nhˆ t mˆt cung cua thiˆt diˆn n`y. Do d o ´’ ´ ´o ´ea a ˙a¯ ¯ˆ ˙ . ıt a e’ ˙ ’ do tˆ t ca c´c d u o ¯ u ¯e e ¯´ . . ˙ cˆn ch´.ng minh rˇ ng tˆn tai mˆt luˆng d at gi´ tri n`y. Ta xem luˆng d a cho F tu.o.ng ` ’` `. ` ` chı a u a o o o ¯. a.a o ¯˜ . u.ng v´.i mˆt vector m chiˆu v` d .nh ngh˜ thiˆt diˆn (V0 → V0 ) bˇ ng dˆ quy theo thu tuc ˜ ` ` ´e ˙. ’ ´ o o e a ¯i ıa e a ¯e . . . sau: 1. Kho.i tao, d ˇt V0 = {s}. ˙ . ¯a ’ . ´ 2. Nˆu vi ∈ V0 , v` hoˇc fij < qij hoˇc fij > 0 th` d ˇt vj v`o trong tˆp V0 . e aa a ı ¯a a a . . . . 3. Lˇp lai Bu.´.c 2 cho dˆn khi khˆng thˆ’ thˆm d ınh n`o v`o V0 . ˙ ´ e e ¯˙ ’ a. o ¯e o aa . C´ hai tru.`.ng ho.p xay ra: hoˇc t ∈ V0 hoˇc t ∈ V0 . ˙ ’ o o a a / . . . Tru.`.ng ho.p 1. t ∈ V0 . o . Theo Bu.´.c 2 trˆn, tˆn tai mˆt dˆy chuyˆn t`. s dˆn t sao cho moi cung (vi , vj ) d u.o.c su. dung e`.oa ` u ¯e ´ ¯. ˙ .’ o o e . . ˙.i dˆy chuyˆn theo hu.´.ng thuˆn (c´c cung d inh hu.´.ng thuˆn) thoa fij < qij v` c´c cung ` ’a ˙ ’ bo e o a a ¯. o a aa . . (vk , vl ) d u.o.c d .nh hu.´.ng ngu.o.c, t´.c l` hu.´.ng t`. vl dˆn vk thoa flk > 0. Dˆy chuyˆn n`y ´ ` ˙ ’ ¯ . ¯i o ua o u ¯e a ea . ` ¯` ˙ ’ goi l` dˆy chuyˆn d iˆu chınh. .aa e e -a Dˇt . (vi , vj ) thuˆn hu.´.ng, δf = min(vi ,vj ) [qij − fij ]; a o . (vk , vl ) ngu.o.c hu.´.ng δb = min(vk ,vi ) [fkl ]; o . http://www.ebook.edu.vn 178
v` a δ = min[δf , δb ]. Nˆu ta cˆng thˆm δ v`o luˆng trˆn tˆ t ca c´c cung d inh hu.´.ng thuˆn v` tr`. d i δ trˆn ´ a` ´’ e a ˙a e o e o ¯. o a a u¯ e . . ´t ca c´c cung d inh hu.´.ng ngu.o.c trong dˆy chuyˆn d iˆu chınh th` luˆng thu d u.o.c vˆn l` ` ¯` ` `a ˙a ’ ˙ ’ tˆ a ¯. o a e e ıo ¯. a . luˆng chˆ p nhˆn d u.o.c c´ gi´ tri nho ho.n luˆng ban d` u mˆt lu.o.ng δ. Diˆu n`y l` hiˆ’n nhiˆn -` ˙ ` ´ ` a¯. o a . ˙ ’ o a o ¯ˆ a o eaae e . . . .o.ng δ v`o c´c cung theo chiˆu thuˆn khˆng vu.o.t qu´ kha nˇng cua c´c cung ` a ˙a ’ ˙a ’ v` thˆm mˆt lu . ıe o aa e a o . . . . d i mˆt lu.o.ng δ v`o c´c cung theo chiˆu ngu.o.c th` luˆng vˆ n khˆng ˜ ` ` n`y (do δ < δf ) v` tr` ¯ o a au aa e ıo a o . . . ˆm (do δ < δb ). a Ap dung lai v´.i luˆng m´.i theo c´c Bu.´.c 1-3 trˆn ta lai thu d u.o.c mˆt thiˆt diˆn m´.i ´ .o` ´e o o a o e ¯. o e o . . . . ˜ (V0 → V0 ). Tru.`.ng ho.p 2. t ∈ V0 . o / . Theo Bu.´.c 2, fij = qij v´.i moi cung (vi , vj ) ∈ (V0 → V0 ) v` fkl = 0 v´.i moi cung (vk , vl ) ∈ ˜ o o a o . . ˜0 → V0 ). (V Do d o ¯´ fij = qij ˜ ˜ (vi ,vj )∈(V0 →V0 ) (vi ,vj )∈(V0 →V0 ) v` a fkl = 0; ˜ (vk ,vl )∈(V0 →V0 ) t´.c l` gi´ tri cua luˆng bˇ ng ` ` uaa.˙ ’ o a fij − fkl ˜ ˜ (vi ,vj )∈(V0 →V0 ) (vk ,vl )∈(V0 →V0 ) ˜ ` ´e ˙a ’ ˙ ’ v` bˇ ng kha nˇng thˆng qua cua thiˆt diˆn (V0 → V0 ). aa o e . Do Tru.`.ng ho.p 1, luˆng tˇng ´ nhˆ t mˆt d o.n vi, nˆn nˆu gia thiˆt tˆ t ca c´c kha ` ´ ´ ´´’ ˙ ’ ea ˙a ˙ ’ o o a ıt a o¯ .ee . . .ng sˆ nguyˆn th` luˆng l´.n nhˆ t c´ thˆ’ nhˆn d u.o.c sau mˆt sˆ h˜.u han bu.´.c ˙. ´ ` ´ o e a¯. ´u nˇng qij l` nh˜ a au o e ıo o a oo o . . khi Tru.`.ng ho.p 2 xay ra. Luˆng n`y c´ gi´ tri bˇ ng kha nˇng thˆng qua cua thiˆt diˆn hiˆn a oa.` ` ´e ˙ ’ ˙a ’ ˙ ’ o o a o e e . . . ˜0 ) nˆn l` luˆng l´.n nhˆ t v` thiˆt diˆn tu.o.ng u.ng c´ kha nˇng thˆng qua nho ea` ´ ´e ˙a ’ ˙ ’ h`nh (V0 → V a o o aa e ´ o o . ´t. nhˆa Phu.o.ng ph´p xˆy du.ng d u.o.c su. dung dˆ’ ch´.ng minh d inh l´ trˆn cho ch´ng ta thuˆt ˙ ¯. ˙ . ’ aa ¯e u ¯. ye u a . . ˙ t` luˆng l´.n nhˆ t t`. s dˆn t. Thuˆt to´n n`y s˜ d u.o.c tr` b`y du.´.i d ay. ’ ım ` ´ u ¯e ´ to´n dˆ a ¯e o o a a a a e¯ . ınh a o ¯ˆ . Xuˆ t ph´t t`. luˆng chˆ p nhˆn d u.o.c tu` y (c´ thˆ’ su. dung luˆng c´ gi´ tri bˇ ng khˆng) ˙’ oa.` ´ au` ´ ` y´ o e ˙ . a o a a¯. o a o . . s dˆn t. Viˆc t` ` ` ` ¯` ` ´ ˙ ’ v` sau d ´ tˇng luˆng bˇ ng c´ch t` c´c dˆy chuyˆn d iˆu chınh luˆng t` ¯e a ¯o a o a a ım a a e e o u e ım . http://www.ebook.edu.vn 179
mˆt dˆy chuyˆn d iˆu chınh luˆng d u.o.c thu.c hiˆn bˇ ng c´ch g´n nh˜n. Khi t` d u.o.c mˆt e` ` ¯` ` ˙ ’ oa e e o ¯. a a a a ım ¯ . o . . . . ` ¯` ` ` ´’ ˙ ’ a.˙ ’ ¯´ a a ˙ a dˆy chuyˆn d iˆu chınh luˆng, ta s˜ tˇng gi´ tri cua luˆng. Sau d o xo´ tˆ t ca c´c nh˜n v` a e e o ea o aa luˆng m´.i d u.o.c su. dung dˆ’ g´n nh˜n lai. Nˆu khˆng tˆn tai dˆy chuyˆn d iˆu chınh luˆng ˙ ` ´ `.a ` ¯` ` o¯. ˙ . ’ ˙ ’ o ¯e a a. e o o e e o ´t th´c, luˆng chˆ p nhˆn d u.o.c l` l´.n nhˆ t. Thuˆt to´n cu thˆ’ nhu. sau: ˙ ` ´ ´ th` thuˆt to´n kˆ ı a ae u o a a ¯. ao a a a.e . . . Thuˆt to´n g´n nh˜n d e’ t` luˆng l´.n nhˆ t ˙ a ¯ˆ ım ` ´ 7.2.1 a a a o o a . A. Qu´ tr` g´n nh˜n a ınh a a Mˆi d ınh chı c´ thˆ’ c´ mˆt trong ba kha nˇng: ˙ ˜’ o ¯˙ ˙o eo o ’ ˙a ’ . 1. d u.o.c g´n nh˜n v` d u.o.c kiˆ’m tra (t´.c l` n´ d u.o.c g´n nh˜n v` tˆ t ca c´c d ınh liˆn ˙ ´’ a a a ˙ a ¯˙ ’ ¯. a a a¯ . e u a o¯ . a e .i n´ d ˜ d u.o.c xu. l´); hoˇc ˙y ’ thuˆc v´ o ¯a ¯ . oo a . . 2. d u.o.c g´n nh˜n v` chu.a d u.o.c kiˆ’m tra (t´.c l` n´ d u.o.c g´n nh˜n v` tˆn tai d ınh liˆn ˙ a a ` . ¯˙ ’ ¯. a aa ¯. e u a o¯ . a o e .i n´ chu.a d u.o.c xu. l´); hoˇc ˙y ’ thuˆc v´ o oo ¯. a . . 3. chu.a d u.o.c g´n nh˜n. ¯. a a ` ` ao o a ˙ ¯˙ ’’ Nh˜n cua d ınh vi gˆm hai th`nh phˆn v` c´ mˆt trong hai dang hoˇc (+vj , δ ) hoˇc (−vj , δ ). o a a a a . . . . .`.ng ho.p d` u, c´ thˆ’ tˇng luˆng doc theo cung (v , v ); trong tru.`.ng ho.p th´. hai, ˙a ` Trong tru o . ¯ˆ a oe o o u . . ij c´ thˆ’ giam luˆng doc theo cung (vi , vj ). Dai lu.o.ng δ trong ca hai tru.`.ng ho.p l` lu.o.ng h`ng -. ˙’ ` oe˙ ˙ ’ o o a. a . . . ˙ thˆm hoˇc b´.t gi´ tri cua luˆng trˆn c´c cung thuˆc dˆy chuyˆn d iˆu ’e ` ´ ` ` ¯` a.˙ ’ nhiˆu nhˆ t c´ thˆ e aoe ao o ea oa e e . . chınh (trong qu´ tr` xˆy du.ng) t`. s dˆn vi . Nh˜n cua d ınh vi cho ph´p x´c d inh dˆy ´ ˙ ’ ˙ ¯˙ ’ ’ a ınh a u ¯e a e a ¯. a . chuyˆn d iˆu chınh luˆng t`. s dˆn vi . ` ¯` ` ´ ˙ ’ e e o u ¯e Kho.i tao tˆ t ca c´c d ınh chu.a d u.o.c g´n nh˜n v` fij = 0 v´.i moi cung (vi , vj ) ∈ E. ´’ ˙ . a ˙ a ¯˙ ’ ’ ¯. a aa o . 1. G´n nh˜n cua d ınh s l` (+s, δ (s) = ∞). Dınh s d u.o.c g´n nh˜n v` chu.a d u.o.c kiˆ’m -˙ ˙ ˙ ¯˙ ’ ’ ’ a a a ¯. a aa ¯. e .a d u.o.c g´n nh˜n. ´’ a ˙ a ¯˙ ’ tra; tˆ t ca c´c d ınh kh´c chu ¯ . a a a 2. Chon d ınh vi ∈ V d a d u.o.c g´n nh˜n v` chu.a d u.o.c kiˆ’m tra. Nˆu khˆng tˆn tai, thuˆt ˙ ´ `. . ¯˙ ’ ¯˜ ¯ . a aa ¯. e e o o a. .ng, luˆng F = (f ) l` l´.n nhˆ t. Ngu.o.c lai, gia su. (±v , δ (v )) l` nh˜n cua ` ´ ˙˙ ’’ ˙ ’ to´n d` au o ao a aa .. ij k i ¯˙’ d ınh vi . • G´n nh˜n (+vi , δ (vj )) cho tˆ t ca c´c d ınh vj ∈ Γ(vi ) chu.a d u.o.c g´n nh˜n sao cho ´’ a ˙ a ¯˙ ’ a a ¯. a a fij < qij , trong d o ¯´ δ (vj ) := min{δ (vi ), qij − fij }. http://www.ebook.edu.vn 180
• G´n nh˜n (−vi , δ (vj )) cho tˆ t ca c´c d ınh vj ∈ Γ−1 (vi ) chu.a d u.o.c g´n nh˜n sao ´’ a ˙ a ¯˙ ’ a a ¯. a a cho fji > 0, trong d o ¯´ δ (vj ) := min{δ (vi ), fji }. (Dınh vi d a d u.o.c g´n nh˜n v` d ˜ d u.o.c kiˆ’m tra; c´c d ınh vj x´c d inh trˆn d ˜ d u.o.c -˙ ˙ ’ a ¯˙ ’ ¯˜ ¯ . a a a ¯a ¯ . e a ¯. e ¯a ¯ . .a d u.o.c kiˆ’m tra). ˙ g´n nh˜n v` chu ¯ . a aa e 3. Nˆu d ınh t d u.o.c g´n nh˜n, chuyˆ’n sang Bu.´.c 4; ngu.o.c lai chuyˆ’n sang Bu.´.c 2. Cˆn ˙ ˙ ´’ ` e ¯˙ ¯. a a e o e o a .. .o.c g´n nh˜n v` V l` tˆp c´c d ınh chu.a d u.o.c ˜0 a a a ¯˙ ` ´ a a a ¯ ˙ ¯a ¯’ ’ ch´ y rˇ ng, nˆu V0 l` tˆp c´c d ınh d ˜ d u . a u´ a e aa ¯. . . ˜0 ) l` thiˆt diˆn nho nhˆ t. ´e ´ ˙ ’a g´n nh˜n th` (V0 → V a a a ı e . ` B. Qu´ tr` tˇng luˆng a ınh a o 4. Dˇt c = t v` chuyˆ’n sang Bu.´.c 5. -a ˙ a e o . • Nˆu nh˜n cua d ınh c c´ dang (+z, δ (c)) th` thay luˆng trˆn cung (z, c) l` fzc bo.i ´ ` a ˙ ¯˙ ’’ ˙ ’ e o. ı o e a fzc + δ (t); • Nˆu nh˜n cua d ınh c c´ dang (−z, δ (c)) th` thay luˆng trˆn cung (x, z ) l` fcz bo.i ´ ` a ˙ ¯˙ ’’ ˙ ’ e o. ı o e a fcz − δ (t); 5. Nˆu z = s th` xo´ tˆ t ca c´c nh˜n t`. c´c d ınh v` chuyˆ’n sang Bu.´.c 1; ngu.o.c lai (t´.c ˙ ´ ´’ ı aa ˙a a u a ¯˙ ’ e a e o ..u . lai Bu.´.c 5. a˙ ’ l` z = c) d at c = z v` tro . a ¯ˇ o . - ˆ . ¯iˆ D` thi d ` u chınh luˆng ` ˙ ’ 7.2.2 o e o Qu´ tr` t` mˆt dˆy chuyˆn dˆ’ tˇng gi´ tri cua luˆng F trong d` thi G = (V, E ) c´ ˙ ` ¯e a ` a.˙ ’ a ınh ım o a e o ¯o . ˆ o . .a vˆ t` mˆt d u.`.ng d i t`. s dˆn t trˆn d` thi d iˆu chınh luˆng Gµ (F ) = (V µ , E µ ), thˆ’ d u ` ım o ¯ o ˙ ´ e ¯o . ¯ ` ` ˙ ’ e¯ e ¯ u ¯e ˆ e o . µ µ µ µ V = V, E = E1 ∪ E2 , trong d o ¯´ µ µµ E1 := {(vi , vj ) | fij < qij , (vi , vj ) ∈ E }, v´.i kha nˇng cua mˆ i cung (vi , vj ) ∈ E1 l` qij = qij − fij , v` µµ µ aµ ˜ ˙a ’ ˙ ’ o o a µ µµ E2 := {(vj , vi ) | fij > 0, (vi , vj ) ∈ E } v´.i kha nˇng cua mˆ i cung (vj , vi ) ∈ E2 l` qji = fij . µµ µ aµ ˜ ˙a ’ ˙ ’ o o Khi d o thu tuc g´n nh˜n cua thuˆt to´n t` luˆng l´.n nhˆ t trong Phˆn 7.2.1 ch´ l` a ım ` ´ ` ¯´ ˙ . a ’ a˙ ’ a o o a a ınh a . ` thi d iˆu chınh luˆng Gµ (F ). Nˆu t ∈ R(s), ` ` ´ ˙ ’ thuˆt to´n x´c d .nh tˆp pham vi R(s) trong d ˆ . ¯ e a a a ¯i a ¯o o e . . . t´.c l` nˆu d ınh t d u.o.c g´n nh˜n, th` c´ thˆ’ x´c d inh mˆt d u.`.ng d i t`. s dˆn t trong d` thi ˙ ´’ ´ u a e ¯˙ ¯. a a ı o e a ¯. o ¯o ¯ u ¯e ¯ˆ . o . .`.ng ho.p n`y, dˆy chuyˆn d iˆu chınh luˆng cua G l` d u.`.ng d i P m` c´c ` ¯` ` µ ˙’ ˙ ’ G (F ). Trong tru o a a e e o a¯ o ¯ aa . cung cua P thuˆc E1 tu.o.ng u.ng cung d inh hu.´.ng thuˆn v` c´c cung cua P thuˆc E2 d u.o.c µ µ ˙ ’ ˙’ o ´ ¯. o a aa o ¯. . . . .´.ng ngu.o.c. d .nh hu o ¯i . http://www.ebook.edu.vn 181
a ıch ` 7.2.3 Phˆn t´ luˆng o Trong mˆt sˆ tru.`.ng ho.p ta muˆn phˆn t´ mˆt luˆng ph´.c tap th`nh tˆ’ng cua nh˜.ng ˙ .´ ´ a ıch o ` ˙ ’ oo o o o u. a o u . . .n gian ho.n. Diˆu n`y khˆng nh˜.ng c´ y ngh˜ thu.c tiˆn m` c`n g´p phˆn hiˆ’u tˆt -` ˙o ˜ ` ` e´ ˙ ’ luˆng d o o¯ ea o u o´ ıa . e ao o a .n ban chˆ t cua luˆng trˆn mang vˆn tai, v` ngo`i ra phuc vu mˆt sˆ thuˆt to´n vˆ luˆng. ´˙ ` ´ `` ˙ ’ ’ ˙a ’ ho a o e a a .oo a aeo . . . . . K´ hiˆu h ◦ (S ) l` luˆng trong d` thi G m` c´c cung (vi , vj ) ∈ S c´ fij = h v` c´c cung a` ye o ¯ˆ . o aa o aa . ` ng h ◦ (S ) khˆng nhˆ t thiˆt l` mˆt luˆng v´.i tˆp S tu` y. ´ ´ao ` (vi , vj ) ∈ S c´ fij = 0. Ch´ y rˇ / o u´ a o a e o oa y´ . . Hiˆ’n nhiˆn rˇ ng h ◦ (S ) l` mˆt luˆng th` tˆp S c´c cung hoˇc tao th`nh mˆt d u.`.ng d i t`. s ˙ e` ao` e a o ıa a a. a o ¯o ¯u . . . . ´ dˆn t hoˇc l` mˆt mach trong G. ¯e aao . . . V´.i hai luˆng F v` H ta k´ hiˆu F + H l` luˆng m` luˆng trˆn cung (vi , vj ) l` fij + hij . ` a` a` o o a ye o o e a . Dinh l´ 7.2.11 Nˆu F l` luˆng t`. s dˆn t c´ gi´ tri nguyˆn v trong G th` F c´ thˆ’ phˆn -. ˙ ´ a` ´ y e o u ¯e oa. e ı oea t´ch th`nh ı a F = 1 ◦ (P1 ) + 1 ◦ (P2 ) + · · · + 1 ◦ (Pv ) + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ), trong d ´ P1 , P2 , Pv l` c´c d u.`.ng d i so. cˆ p t`. s dˆn t v` Φ1 , Φ2 , . . . , Φκ l` c´c mach so. cˆ p ´ ´ ´ ¯o aa ¯o ¯ a u ¯e a aa a . ´ ´ ˙ ’ cu a G. (Pi v` Φi khˆng nhˆ t thiˆt phˆn biˆt). a o a e a e . Ch´.ng minh. T`. G = (V, E ) v´.i luˆng F cho tru.´.c ta xˆy du.ng d` thi unitary Ge = (V e , E e ) o` u u o o a. ¯o . ˆ . sau: Tˆp V e c´c d ınh cua Ge ch´ l` tˆp V c´c d ınh cua G. Nˆu f l` luˆng trˆn cung e ij a ` ´ a ¯˙’ ˙ ’ a ¯˙’ ˙ ’ nhu a ınh a a o e . . .a c´c d ınh tu.o.ng u.ng v e v` v e cua Ge . ` (vi , vj ) cua G th` ta thay bˇ ng fij cung song song gi˜ a ¯˙ ˙ ’ ’ ˙ ’ ı a u ´ iaj ´u fij = 0 th` khˆng c´ cung n`o d u.o.c d ˇt gi˜.a vi v` vj . Ta d u.o.c Ge l` d a d` thi trong e e Nˆe ıo o a ¯ . ¯a u a ¯. a ¯ ¯ˆ .o . d o mˆ i cung cua n´ tu.o.ng u.ng v´.i mˆt d o.n vi luˆng trˆn cung tu.o.ng u.ng trong G; n´i c´ch ˜ ` ˙o ’ ¯´ o ´ o o¯ o e ´ oa . . ˙u diˆn luˆng F trong G. ’ ˜ ` e kh´c, G biˆ a e e o T`. d iˆu kiˆn vˆ luˆng F suy ra c´c d ınh cua d` thi Ge cˆn thoa m˜n u ¯` e`` ` a ¯˙ ’ ˙ ¯ˆ . ’o ˙a ’ e .eo a v´.i moi vi = se hoˇc te , d+ (vi ) = d− (vi ), e e e o a . . +e −e d (s ) = d ( ) = v. Suy ra nˆu ta tra lai v cung d u.o.c thˆm v`o Ge t`. d ınh te dˆn d ınh se th` d` thi Ge ´ ´’ ˙. ’ u ¯˙’ ¯e ¯ ˙ e ¯. e a ı ¯o . ˆ s˜ c´ mˆt mach Euler (xem Phˆn 5.1). Loai bo v cung n`y khoi mach Euler, ta d u.o.c v ` .˙ ’ ˙ ’ eo o a a ¯. . . . d u.`.ng d i t`. se dˆn te qua mˆi cung cua Ge d ung mˆt lˆn. K´ hiˆu c´c d u.`.ng d i n`y l` ˜ ´ o` ˙ ’ ¯o ¯u ¯e o ¯´ a y e a ¯o ¯aa . . P1 , P2 , . . . , Pv . C´c d u.`.ng d i Pi khˆng nhˆ t thiˆt so. cˆ p (mˇc d` ch´ng l` d o.n gian). Tuy ´ ´ ´ ˙ ’ a ¯o ¯ o a e a auu a¯ . ˜i d u.`.ng d i khˆng so. cˆ p c´ thˆ’ xem nhu. tˆ’ng cua mˆt d u.`.ng d i so. cˆ p t`. se dˆn ˙ ˙ ´oe ´u ´ ˙ ’ nhiˆn, mˆ ¯ o e o ¯ o a o o¯o ¯ a ¯e . . cˆ p r`.i nhau. Do vˆy, .´ ´ e t v` mˆt sˆ c´c mach so a o a o oa a . . F = 1 ◦ (P1 ) + 1 ◦ (P2 ) + · · · + 1 ◦ (Pv ) + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ), http://www.ebook.edu.vn 182
trong d o Pi l` c´c d u.`.ng d i so. cˆ p t`. se dˆn te v` Φi l` c´c mach so. cˆ p. ´ ´ ´ ¯´ aa ¯o ¯ au ¯e a aa a . N´i chung, c´c d u.`.ng d i v` c´c chu tr` c´ thˆ’ tr`ng nhau. Nˆu chı c´ v d u.`.ng d i v` ˙ ´ ˙o ¯o ¯ a ’ o a ¯o ¯ aa ınh o e u e .i d u.`.ng d i P xuˆ t hiˆn h lˆn trong danh s´ch P , P , . . . , P κ mach d` u tiˆn kh´c nhau, v´ ¯ o ¯ i a ´ e i` . ¯a e ˆ a o a a . 1 2 v ´t hiˆn li lˆn trong danh s´ch Φ1 , Φ2 , . . . , Φκ th` F c´ thˆ’ viˆt du.´.i dang ˙e ` ´ v` mach Φi xuˆ a. a e a a ı oe o. . v κ F= hi ◦ (Pi ) + li ◦ (Φi ). i=1 i=1 N´i chung hai luˆng F v` H l` th´ u.ng nˆn fij .hij = 0 v´.i moi cung (vi , vj ). ` ´ o o a a ıch ´ e o . V´ du 7.2.12 Luˆng F trong H` 7.3 d u.o.c phˆn t´ th`nh c´c d u.`.ng d i (t`. s dˆn t) ` ´ ı. o ınh ¯. a ıch a a ¯o ¯ u ¯e . cˆ p: ´ v` c´c mach so a aa . F = 2 ◦ P1 + 1 ◦ P2 + 1 ◦ Φ1 + 1 ◦ Φ2 + 1 ◦ Φ3 , trong d o ¯´ P1 = {s, v2 , v4 , t}, P2 = {s, v1 , v3 , v2 , v4 , t}, Φ1 = {v1 , v3 , v2 , v1 }, Φ2 = {v2 , v4 , v5 , v6 , v2 }, Φ3 = {v5 , v6 , v7 , v5 }. C´c ca i biˆn d .n gia n cu a b`i to´n luˆng l´.n nhˆ t ` ´ a˙ ’ ˙ ’ ˙ ’ 7.3 e ¯o a a o o a Phˆn n`y ch´ng ta nˆu mˆt sˆ kˆt qua nhˆn d u.o.c t`. b`i to´n luˆng l´.n nhˆ t. ` . ´´ ` ´ ˙ ’ a¯. ua a aa u e ooe o o a . C´c d` thi c´ nhiˆu nguˆn v` nhiˆu d ıch ` ` ` ¯´ 7.3.1 a ¯ˆ . o o e o a e X´t d` thi v´.i ns d ınh v`o v` nt d ınh ra v` gia su. luˆng c´ thˆ’ chuyˆ’n t`. nguˆn dˆn d´ ˙ ˙ a˙˙` ` ¯e ¯ıch o´ ¯˙ ’ ¯˙ ’ ’’ o e ¯o . o ˆ aa oe eu .n nhˆ t t`. tˆ t ca c´c nguˆn dˆn tˆ t ca c´c d´ c´ thˆ’ d u.a vˆ ˙ ` ng l´ ´ ua ˙a ´’ ` ¯e a ˙ a ¯ıch o e ¯ ´´’ ` tu` y. B`i to´n t` luˆ y ´ a a ım o o a o e .n nhˆ t bˇ ng c´ch thˆm mˆt d ınh nguˆn nhˆn tao s v` mˆt d ınh ra nhˆn a` ` ´a ` o ¯˙ ’ a o ¯˙ ’ b`i to´n luˆng l´ aa o o a e o a. a . . tao t v´.i c´c cung d u.o.c thˆm t`. s dˆn c´c d ınh v`o ban d` u v` t`. c´c d ınh ra thu.c tˆ dˆn ´ ´´ u ¯e a ¯˙ ’ ¯ˆ a u a ¯˙ ’ oa ¯. e a a . e ¯e . . s dˆn c´c nguˆn c´ thˆ’ d ˇt bˇ ng vˆ c`ng, hoˇc ˙. a ` o e ¯a ` ´ ¯˙’ ˙a ’ ˙a ’ d ınh t. Kha nˇng cua c´c cung thˆm v`o t` ¯e a e au o ou a . .`.ng ho.p lu.o.ng h`ng cung cˆ p tai mˆt nguˆn s tˆi d a l` a th` kha nˇng cua cung ´ ` ko¯ ak ı ˙ a ´ ’ ˙ ’ trong tru o a a.o o . . . http://www.ebook.edu.vn 183
v7 •..................... .. . . . . . . . . .... .... . . .... .... . . .... .... . . .... .... . . .... . .... . .... . .... . .... . .... . . .... .... ... .... . . .. . .... ... .... ... .... .... . .... . .... . . .... .... . . .... . .... . .... . .... . .... . .... . ... . v6 • • v5 . ......................................................................... . . ....................................................................... ..... . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .. . .. . . . . . . . . .. .. . . ... . . . . . . . . . . . . . . . . . . . . . v2 . . . . . . . . . . . s• . • • •t . . .................................................................................................................................................... ........................................................................ ...................................... ................................... . .. .. .................................. .................................. .. . . . .. .. ... . . . . .. .... ... ... .. ... ... v4 ... ... ... ... . ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... .... ... .. ... ... ..... .... .. . . ... ... ... ... ... ... ... .. ... . .... ... ... ... . .. ... ... . ... ... ... ... ... ... ... . ... ... ... ... ... ... ... . ... ... ... ... ... ... ... . . ... .... ... ... .... ... .. .. ... ... • • ...... ................................ ....................................... ......................................................................... .. . . . . v1 v3 ` H` 7.3: Luˆng F. ınh o (s, sk ) c´ thˆ’ d ˇt bˇ ng gi´ tri n`y. Tu.o.ng tu., kha nˇng cua c´c cung dˆ n t´.i d ınh ra t c´ ˙. a o e ¯a ` ˜ ˙a ’ ˙a ’ a o ¯˙ ’ a.a o . ˙ d ˇt bˇ ng nhu cˆu tai c´c d ınh ra tk hoˇc bˇ ng vˆ han nˆu c´ nhu cˆu l` vˆ han. ’ ¯a ` ` ` . a ¯˙ ´o ` ao. ’ thˆ . a e a aa o. e a . Nˆu b`i to´n d ˇt ra o. d ´ c´ d ınh ra chı d u.o.c cung cˆ p bo.i nh˜.ng nguˆn n`o d ´ v` ´ ´ ` ˙ ¯o o ¯ ˙ ’ ’ ˙¯ . ’ ˙ ’ ea a ¯a a u o a ¯o a . .o.c lai, th` b`i to´n khˆng phai l` cai biˆn d o.n gian cua b`i to´n luˆng l´.n nhˆ t t`. s ` ´ ˙a˙ ’ ’ ˙ ’ ˙ ’a ngu . . ıa a o e¯ a o o au dˆn t m` c´ thˆ’ d u.a vˆ b`i to´n d a luˆng nhu. d a d` cˆp trong phˆn mo. d` u. ˙ ´ `a a¯ ` ` ˙ ¯a ’ˆ ¯e a o e¯ e o ¯˜ ¯ˆ ae. a C´c d` thi v´.i r`ng buˆc tai c´c cung v` d ˙nh ’ 7.3.2 a ¯ˆ . o a o o.a a ¯ı . ´ ˙a ’ ˙a ’ ˙a ’ ˙ a ¯˙ ’ ’ Nˆu ngo`i kha nˇng qij cua c´c cung, ta thˆm kha nˇng cua c´c d ınh wj , j = 1, 2, . . . , n, sao e a e .o.ng h`ng d i dˆn d ınh v nho ho.n w , t´.c l` cho tˆ’ng sˆ lu . ˙ ´ ´’ a ¯ ¯e ¯˙ ˙ ’ o o ua j j fij ≤ wij vi ∈Γ−1 (vj ) v´.i moi vj . o . Ta cˆn t` luˆng l´.n nhˆ t t`. s dˆn t v´.i gia thiˆt thˆm tai c´c d ınh. X´t d` thi G0 ` ım ` ´ ´ ´ ˙ ’ . a ¯˙ ’ a o o a u ¯e o e e e ¯o . ˆ .o.ng u.ng hai d ınh v + v` v − trong d` thi G sao cho sao cho moi d ınh vj cua d` thi G tu . ¯˙’ ˙ ¯o . ’ ¯˙ ’ ˆ ´ aj ¯o . 0 ˆ j ˙ a G dˆn d ınh vj tu.o.ng u.ng mˆt cung (vi , vj ) dˆn d ınh vj , v` moi cung −+ + ´ ¯˙ ´ ¯˙ ’ ’ ’ moi cung (vi , vj ) cu ¯e ´ o ¯e a. . . (vj , vk ) cua G xuˆ t ph´t t`. vj tu.o.ng u.ng mˆt cung (vj , vk ) cua G0 xuˆ t ph´t t`. vj . Ngo`i −+ au− ´ ´ ˙ ’ ˙ ’ a au ´ o a a . .a v + v` v − v´.i kha nˇng thˆng qua w , t´.c l` bˇ ng kha nˇng cua ` ˙a ’ ˙a ’ ˙ ’ ra ta thˆm mˆt cung gi˜ j a j o e o u o uaa . j ¯˙’ d ınh vj . V` tˆ’ng sˆ lu.o.ng h`ng dˆn d ınh vj phai d u.o.c chuyˆ’n doc theo cung (vj , vj ) v´.i kha ˙ ˙. + +− ´ ´’ a ¯e ¯˙ ˙¯. ’ ˙ ’ ıo o. e o http://www.ebook.edu.vn 184
nˇng thˆng qua wj nˆn luˆng l´.n nhˆ t trong d` thi G v´.i r`ng buˆc tai c´c d ınh bˇ ng luˆng ` ` ´ ` o . a ¯˙ ’ a o e o o a ¯ˆ . o oa a o . .n nhˆ t trong d` thi G v´.i r`ng buˆc chı tai c´c cung. Cˆn ch´ y rˇ ng nˆu thiˆt diˆn nho u´ ` ´ ` ´ ´e ˙. a ’ ˙ ’ l´ o a ¯o . 0 o a ˆ o a a e e . . .a c´c cung dang (v + , v − ) th` r`ng buˆc tai d ınh v tng ng trong G ´’ a˙ o . ¯˙ ’ nhˆ t cua G0 khˆng ch´ a o u ıa . . j j j .c” v` tro. th`nh vˆ dung; nˆu ngu.o.c lai, thiˆt diˆn nho nhˆ t cua G ch´.a c´c ´ ´e ´’ ˙a ’ ˙a˙ ’ khˆng “t´ cu o ıch . a o. e e ua .. . 0 cung loai n`y th` c´c d ınh tu.o.ng u.ng cua G l` bao ho` bo.i luˆng l´.n nhˆ t. a˙ ` ´ ı a ¯˙ ’ ˙ ’ a˙ ’ ’ a ´ o o a . C´c d` thi c´ cˆn trˆn v` cˆn du.´.i vˆ luˆng o`` 7.3.3 a ¯ˆ . o a o e aa eo . . X´t d` thi G trong d ´ c´c cung (vi , vj ) ngo`i cˆn trˆn qij c`n c´ cˆn du.´.i vˆ luˆng l` rij . o`` e ¯ˆ . o ¯o a aa e o oa eo a . . . ta muˆn biˆt c´ tˆn tai mˆt luˆng chˆ p nhˆn gi˜.a s v` t sao cho r ≤ f ≤ q v´.i ´ e o` . ´ o` ´ ˙˙ ’’ Gia su o o o a a u a ij o . . ij ij moi cung (vi , vj ). . T`. G, ta thˆm mˆt d ınh v`o nhˆn tao sa v` d ınh ra nhˆn tao ta dˆ’ nhˆn d u.o.c Ga . ˙ o ¯˙ .’ a ¯˙ ’ u e a a. a. ¯e a ¯ . . ˜i cung (vi , vj ) m` rij = 0 ta thˆm mˆt cung (sa , vj ) v´.i kha nˇng rij v` cˆn du.´.i bˇ ng ` ˙a ’ Mˆ o a e o o aa oa . . . hai (v , t ) v´.i kha nˇng r v` cˆn du.´.i bˇ ng khˆng. Thay o` ˙a ’ khˆng, v` c˜ng thˆm cung th´ o au e u o ij a a a o . ia .i q − r v` r bˇ ng 0. Ngo`i ra thˆm cung (t, s) v´.i q = ∞, r = 0. ij a ij ` ˙ ’ qij bo ij a a e o ts ts Bˆy gi`. ta t` luˆng l´.n nhˆ t t`. sa dˆn ta trong d` thi Ga . Nˆu gi´ tri cua luˆng l´.n ım ` ´ ´ ´ ` a.˙ ’ a o o o au ¯e ¯o . ˆ e o o .c l`, nˆu tˆ t ca c´c cung d i ra t`. s v` tˆ t ca c´c cung d i dˆn t bao ´` ´´’ ´’ ´ nhˆ t bˇ ng rij =0 rij (t´ a e a ˙ a uaaa ˙a ¯ ¯e a ˙ ’ aa u ¯ .o.ng h`ng trˆn cung (t, s) l` f th` tˆn tai luˆng chˆ p nhˆn d u.o.c v´.i gia `.` ´ ho`) v` k´ hiˆu lu . a ay e a e a ts ı o o a a¯. o . . tri fts trong d` thi ban d` u. Thˆt vˆy, nˆu ta tr`. rij lu.o.ng h`ng trˆn c´c cung (vi , ta ) v` ´ ¯o . ˆ ¯a ˆ aa e u a ea a . .. . .o.ng h`ng trˆn cung (v , v ) th` tˆ’ng lu.o.ng h`ng t`. s dˆn t ˙ ´ (sa , vj ) v` cˆng thˆm rij v`o lu . ao e a a e ıo a u a ¯e a . . ij ˙ m mˆt lu.o.ng l` rij , luˆng trˆn c´c cung (vi , ta ) v` (sa , vj ) giam xuˆng khˆng, c`n luˆng ` ´ ` ’ ˙ ’ gia o a o ea a o o o o . . ` trˆn cung (vi , vj ) l` fij ∈ [rij , qij ]. (Gi´ tri cuˆi cua fij bˇ ng rij nˆu gi´ tri ban d` u cua fij ´’ ´ a.o˙ ˙ ’ e a a e a. ¯a ˆ tu.o.ng u.ng luˆng l´.n nhˆ t bˇ ng khˆng, v` gi´ tri cuˆi cua fij bˇ ng qij nˆu gi´ tri ban d` u a` ` ` ´a ´’ ´ aa.o˙ ´ o o o a e a. ¯ˆ a .´.c tr`. luˆng l´.n nhˆ t ngu.o.c v´.i bu.´.c d iˆu chınh luˆng trong ` u` ´ o ¯` ` ˙ ’ ˙’ cua fij bˇ ng qij − rij ). Bu o a o o a o e o . thuˆt to´n t` luˆng l´.n nhˆ t. V` ta gia thiˆt gi´ tri cua luˆng l´.n nhˆ t bˇ ng rij =0 rij ´` a ım ` ´ ´ a.˙ ` ˙ ’ ’ a o o a ı e o o aa . . luˆng s˜ cho luˆng t`. s dˆn t c´ gi´ tri bˇ ng khˆng (do d o u a ¯e a o a . ` nˆn cuˆi c`ng, tiˆn tr` tr` ` ´ ´ ` ´ e ou e ınh u o e o a o ¯´ ´n hai d ınh nhˆn tao v` c´c cung liˆn thuˆc ch´ng tro. th`nh vˆ dung), v` luˆng trˆn ` ˙ ’ ˙a ’ s˜ khiˆ e e ¯ a . aa e o u o. ao e . tˆ t ca c´c cung v´.i rij = 0 s˜ thay d o’i trong pham vi [rij , qij ]. Kˆt qua l` ta c´ mˆt luˆng ˙ ´’ ´ oo` a ˙a ˙a ’ o e ¯ˆ e o . . “lu.u thˆng” trong d` thi v´.i gi´ tri bˇ ng fts . ¯o . o a . ` o ˆ a Mˇt kh´c ta c´ a a o . Dinh l´ 7.3.1 Nˆu gi´ tri cu a luˆng l´.n nhˆ t t`. sa dˆn ta trong d` thi Ga kh´c -. ´ ` ´ ´ a.˙ ’ y e o o au ¯e ¯ˆ . o a rij =0 rij .o.c trong G. `.` ´ th` khˆng tˆn tai luˆng chˆ p nhˆn d u . ıo o o a a¯ . Ch´.ng minh. B`i tˆp. u aa . http://www.ebook.edu.vn 185
Luˆng v´.i chi ph´ nho nhˆ t ` ´ ˙ ’ 7.4 o o ı a Trong Phˆn 7.2 ch´ng ta d a x´t b`i to´n t` luˆng l´.n nhˆ t t`. s dˆn t m` khˆng d` cˆp ` a ım ` ´ ´ a u ¯˜ e a o o a u ¯e a o ¯ˆ a e. .o.c gˇn trˆn mˆ i cung. Phˆn n`y khao s´t b`i to´n t` luˆng v´.i gi´ tri v ´ ˜ ´ ` a ım ` ˙aa ’ dˆn chi ph´ d u . a ¯e ı¯ e o aa o o a. cho tru.´.c t`. s dˆn t sao cho chi ph´ cua luˆng l` nho nhˆ t. Cu thˆ’ l`: ˙ ´ ` ´ ı˙ ’ ˙ ’a o u ¯e o a . ea B`i to´n 7.4.1 Cho mang vˆn ta i G := (V, E ) v´.i d ı’nh v`o s, d ı’nh ra t, kha nˇng thˆng a˙ ’ o ¯˙ ¯˙ ˙a ’ a a a o . . qua cu a cung (i, j ) ∈ E l` qij . Gia su. cij l` chi ph´ vˆn chuyˆ’n mˆt d o.n vi h`ng trˆn cung ˙ ˙ ’ ˙˙ ’’ a a ıa e o¯ a e . . . (i, j ) ∈ E. T`m luˆng F := (fij ) c´ gi´ tri v trˆn G v´.i chi ph´ nho nhˆ t; t´.c l` gia i b`i ` ´ ˙ ’ aua˙a ’ ı o oa. e o ı to´n a fij cij → min (vi ,vj )∈E v´.i d iˆu kiˆn o ¯` e e . fij = v, (vi ,vj )∈E 0≤ fij ≤ qij . Hiˆ’n nhiˆn, b`i to´n khˆng c´ l`.i giai nˆu v l´.n ho.n gi´ tri l´.n nhˆ t cua luˆng t`. s ˙ ’´ ´’ ` ˙e a˙ e e aa o oo o a .o o u dˆn t. Tuy nhiˆn, nˆu v nho ho.n hoˇc bˇ ng gi´ tri n`y th` s˜ c´ mˆt sˆ luˆng c´ gi´ tri v a` ´ ´ ıeo o o ` ´o ˙ ’ ¯e e e a a.a oa. . . v` b`i to´n c´ l`.i giai. Ford v` Fulkerson [27] d a xˆy du.ng mˆt thuˆt to´n “khˆng c´ th´. ˙ ’ a a a oo a ¯˜ a o a a o ou . . . .” dˆ’ t` luˆng v´.i chi ph´ nho nhˆ t. C´c thuˆt to´n tr` b`y du.´.i d ay du.a theo nh˜.ng ˙ ım ` ´ ˙a ’ tu ¯e o o ı a a a ınh a o ¯ˆ u . . . kˆt qua cua Klein [38], Busacker v` Gowen [10]. C´c thuˆt to´n n`y d o.n gian ho.n phu.o.ng ´ ˙˙ ’’ ˙’ e a a a a a¯ . ph´p cua Ford-Fulkerson v` su. dung nh˜.ng k˜ thuˆt d ˜ gi´.i thiˆu trˆn. a˙ ’ a˙ . ’ u y a ¯a o e e . . 7.4.1 Thuˆt to´n Klein, Busacker, Gowen a a . Thuˆt to´n n`y du.a v`o viˆc x´c d .nh mach c´ d o d`i ˆm. Ch´ng ta h˜y gia thiˆt rˇ ng tˆn e` ´a ` ˙ ’ a aa .a e a ¯i o ¯ˆ a a u a o . . . . ` ng chˆ p nhˆn d u.o.c F v´.i gi´ tri v v` F d a d u.o.c x´c d inh. Luˆng n`y c´ thˆ’ nhˆn ˙a ´ ` tai luˆ o a a ¯. o a. a ¯˜ ¯ . a ¯. o aoe . . . d u.o.c bˇ ng c´ch ´p dung thuˆt to´n t` luˆng l´.n nhˆ t v` ch´ng ta tˇng luˆng cho dˆn khi ¯. ` a ım ` ´ ` ´ a aa a o o aau a o ¯e . . nhˆn d u.o.c luˆng c´ gi´ tri v. ` a¯. o oa. . V´.i luˆng chˆ p nhˆn n`y, ta d .nh ngh˜ d` thi Gµ (F ) := (V µ , E µ ) nhu. d ˜ giai th´ o` ´ ¯a ˙ ’ o a aa ¯i ıa ¯ˆ . o ıch . . sau: ` trong Phˆn 7.2 v` c´ chi ph´ trˆn c´c cung nhu a ao ıea • v´.i mˆ i cung (vi , vj ) ∈ E1 , d at cµ := cij . µµ µ ˜ oo ¯ˇ ij . • v´.i mˆ i cung (vj , vi ) ∈ E2 , d at cµ := −cij . µµ µ ˜ oo ¯ˇ ji . Thuˆt to´n du.a trˆn d inh l´ sau: a a e ¯. y . . http://www.ebook.edu.vn 186
Dinh l´ 7.4.2 F l` luˆng gi´ tri v v´.i chi ph´ nho nhˆ t nˆu v` chı’ nˆu khˆng tˆn tai mach -. a` ´´ ´ `. ı ˙ a e a ˙e ’ y o a. o o o . Φ trong G (F ) sao cho tˆ’ng cu a c´c chi ph´ cu a c´c cung thuˆc Φ ˆm. ˙ µ ˙a ’ ı˙ a’ o o a . Ch´.ng minh. Dˇt c[F ] l` chi ph´ cua luˆng F trong d` thi G v` c[Φ|Gµ (F )] l` tˆ’ng cua c´c -a ˙ ` ı˙ ’ ˙a ’ u a o ¯o . ˆ a ao . .o.ng u.ng v´.i d` thi Gµ (F ). ı˙ a ’ chi ph´ cua c´c cung thuˆc mach Φ tu o ´ o ¯o . ˆ . . Diˆu kiˆn cˆn. Gia su. c[Φ|Gµ (F )] < 0 v´.i mach Φ n`o d o trong Gµ (F ). Thˆm mˆt -` e` ˙˙ ’’ e .a o a ¯´ e o . . .n vi v`o luˆng trˆn mˆ i cung thuˆc mach Φ s˜ tao ra mˆt luˆng m´.i chˆ p nhˆn d u.o.c ˜ ` o` ´ do ¯ a o e o o e. o o a a ¯. . . . . . ` ` F + 1 ◦ (Φ) c´ gi´ tri v. Chi ph´ cua luˆng F + 1 ◦ (Φ) bˇ ng c[F ] + c[Φ|Gµ (F )] < c[F ]-mˆu ı˙ ’ oa. o a a thuˆn v´.i gia thiˆt F l` luˆng v´.i gi´ tri v v` c´ chi ph´ nho nhˆ t. ˜ ´ a` ´ ˙ ’ ˙ ’a ao e o o a. ao ı Diˆu kiˆn d u. Gia su. c[Φ|Gµ (F )] ≥ 0 v´.i moi mach Φ trong Gµ (F ) v` F ∗ (= F ) l` -` e ¯˙ ’ ˙˙ ’’ e o a a . . . ` ´ ˙ ’a luˆng gi´ tri v c´ chi ph´ nho nhˆ t. o a. o ı ` a` Ta k´ hiˆu F ∗ − F l` luˆng m` gi´ tri trˆn cung (vi , vj ) bˇ ng fij − fij . ∗ ye o aa.e a . V` F ∗ v` F c´ thˆ’ phˆn t´ th`nh tˆ’ng cua c´c luˆng doc theo (t`. s dˆn t) c´c d u.`.ng ˙ ˙ ˙a` ´ ’ ı a o e a ıch a o o u ¯e a ¯o . .ng cua d` thi unitary Ge trong Phˆn 7.2.3 d oi v´.i luˆng F ∗ − F, ` ´o ` ˙ ¯ˆ . ’o d i trong G, theo c´ch xˆy du ¯ a a. a ¯ˆ o suy ra v´.i moi d ınh vi ∈ V ta c´ ¯˙ ’ o o . d+∗ (vi ) = d−∗ (vi ). G G Do d o theo Phˆn 7.2.3, dˆ d`ng kiˆ’m tra rˇ ng ˙ ˜a ` ` ¯´ a e e a F ∗ − F = 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ). Ho.n n˜.a, luˆng F ∗ = F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ) l` chˆ p nhˆn d u.o.c nˆn tˆ’ng ˙ ` ´ u o aa a ¯. e o . .o.c v´.i moi 1 ≤ l ≤ κ. Do d ´ v´.i luˆng ´ ¯o o ` F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φl ) chˆ p nhˆn d u . o a a¯ o . . F ta c´ o c[F + 1 ◦ (Φ1 )] = c[F ] + c[Φ1 |Gµ (F )] ≥ c[F ]. Mˇt kh´c a a . c[Φl |Gµ (F + 1 ◦ (Φ1 ))] ≥ c[Φl |Gµ (F )] v´.i moi l = 1, 2, . . . , k. o . ` ı˙ ’ Vˆy chi ph´ cua luˆng F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) l` a o a . c[F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 )] = c[F + 1 ◦ (Φ1 )] + c[Φ2 |Gµ (F + 1 ◦ (Φ1 ))] ≥ c[F + 1 ◦ (Φ1 )] + c[Φ2 |Gµ (F )] ≥ c[F + 1 ◦ (Φ1 )] http://www.ebook.edu.vn 187
≥ c[F ]. Tiˆp tuc qu´ tr` trˆn ta d u.o.c c[F ∗ ] ≥ c[F ]. Diˆu n`y mˆu thuˆn v´.i gia thiˆt F ∗ l` luˆng -` ˜ ´ ´ a` ˙ ’ e. a ınh e ¯. ea a ao e o ´ ˙ ’a c´ chi ph´ nho nhˆ t. o ı Do d o theo Dinh l´ 7.4.2, dˆ’ t` luˆng chˆ p nhˆn d u.o.c c´ gi´ tri v v´.i chi ph´ nho -. ˙ ¯e ım ` ´ ˙ ’ ¯´ y o a a ¯. o a . o ı . ´t ta bˇt d` u t`. luˆng chˆ p nhˆn d u.o.c c´ gi´ tri v, thiˆt lˆp d` thi Gµ (F ) v` kiˆ’m tra ˙ ´ ¯a u ` ´ ´ a ¯o . nhˆ a aˆ o a a ¯. o a . e. ˆ ae . c´ tˆn tai mach c´ d ˆ d`i ˆm khˆng. Nˆu khˆng c´ th` luˆng nhˆn d u.o.c c´ chi ph´ nho o` ´ oı` ˙ ’ o. o ¯o a a o e o o a ¯. o ı . . . .o.c lai nˆu Φ l` mach c´ d o d`i ˆm th` ta thˆm δ v`o luˆng trˆn mach n`y. Khi ´ ´ ` nhˆ t. Ngu . . e a a. o ¯ˆ a a ı e a o e a . . ` ng m´.i vˆ n c´ gi´ tri v v` c´ chi ph´ giam mˆt lu.o.ng δ.c(Φ), trong d o c(Φ) l` chi ph´ ˜oa. ˙ ’ d o luˆ ¯´ o oa ao ı o ¯´ a ı . . cua mach c´ dˆ d`i ˆm Φ. Hiˆ’n nhiˆn δ cˆn d u.o.c chon sao cho c´c kha nˇng thˆng qua cua ˙ o` aa ` ¯. ˙ ’ ˙a ’ ˙ ’ o e e a a o . . c´c cung trong Gµ (F ) khˆng bi vi pham; t´.c l` a o ua . . µ δ = min qij . µµ (vi ,vj ) Theo c´ch chon ban d` u cua c´c kha nˇng cua d` thi Gµ (F ) luˆng m´.i nhˆn d u.o.c t`. luˆng ` a¯. u ` ¯a ˙ a’ ˙a ’ ˙ ¯o . ’ˆ a ˆ o o o . . .o.c. Qu´ tr` lai ` ` ´ c˜ (bˇ ng c´ch cˆng δ v`o luˆng trˆn mach d o d`i ˆm) l` chˆ p nhˆn d u . ua a o a o e ¯ˆ a a aa a¯ a ınh . . . . . .o.c lˇp lai v´.i luˆng m´.i v` vˆn vˆn. Chi tiˆt cua thuˆt to´n nhu. sau. ` ´˙ ’ du . a . o o ¯ o aa a e a a . . a ım ` ´ ˙ ’ Thuˆt to´n t` luˆng c´ chi ph´ nho nhˆ t a o o ı a . 1. Su. dung thuˆt to´n luˆng l´.n nhˆ t, t` luˆng chˆ p nhˆn d u.o.c F v´.i gi´ tri v. ` a ım ` ´ ´ ˙. ’ a a o o o a a¯. o a. . . -a 2. Dˇt . µ µµ E1 := {(vi , vj ) | fij < qij , (vi , vj ) ∈ E }, µ µµ E2 := {(vj , vi ) | fij > 0, (vi , vj ) ∈ E }. Xˆy du.ng d` thi c´ trong sˆ Gµ (F ) := (V µ , E µ ), trong d o ´ a ¯o . o . ˆ o ¯´ . V µ := V, µ µ E µ := E1 ∪ E2 , • V´.i mˆ i cung (vi , vj ) ∈ E1 , d at cµ := cij . µµ µ ˜ oo ¯ˇ ij . .i mˆ i cung (v µ , v µ ) ∈ E µ , d at cµ := −c . ˜ • V´ o o 2 ¯ˇ . ji ij j i d ˆ d`i ˆm Φ trˆn d` thi Gµ (F ) c´ trong sˆ W := (wij ), chuyˆ’n ˙ e`. ´o ´ 3. Nˆu tˆn tai mach c´ o ¯o a a e ¯ˆ .o o. o e . . .´.c 5. Ngu.o.c .i chi ph´ nho nhˆ t; thuˆt to´n d`.ng. a` ´ ˙ ’a sang Bu o lai, F l` luˆng v´ o o ı a au .. . 4. T´ δ theo cˆng th´.c sau: ınh o u µ µµ δ := min{qij | (vi , vj ) ∈ Φ}. • V´.i moi cung (vi , vj ) ∈ Φ sao cho cµ < 0 thay d ˆ’i luˆng fji trˆn cung (vj , vi ) ∈ E µµ ˙o ¯o ` o e . ij .i f − δ. ˙ ’ bo ji http://www.ebook.edu.vn 188
• V´.i moi cung (vi , vj ) ∈ Φ sao cho cµ > 0 thay d ˆ’i luˆng fij trˆn cung (vi , vj ) ∈ E µµ ˙o ¯o ` o e . ij .i f + δ. ˙ ’ bo ij 5. V´.i luˆng m´.i F, chuyˆ’n sang Bu.´.c 2. ˙ o` o o e o 7.5 Cˇp gh´p a e . a `a 7.5.1 C´c b`i to´n vˆ cˇp gh´p a a e. e C´c b`i to´n vˆ cˇp gh´p trong c´c d` thi (n´i chung khˆng phai d` thi hai phˆn) d u.o.c a `a ` ˙ ¯o . ’ˆ aa e. e a ¯o . o ˆ o a ¯. . nhˆ t, c´ thˆ’ dˆn dˆn c´c b`i to´n n`y t`. viˆc tˆ’ng qu´t ho´ ˙ a ¯e a a ˙ ˜ ´ ´ quan tˆm v` hai l´ do. Th´ a ı y u aoe aaueo a a . b`i to´n phˆn cˆng, v` ch´ng l` mˆt phˆn trong nh˜.ng b`i to´n kh´c cua d` thi: c´c b`i ` a ˙ ¯ˆ . a a ’o a a ao au ao a u a a . to´n t` h`nh tr` tˆi u.u (nhu. b`i to´n ngu.`.i d u.a thu. Trung Hoa), x´c d inh dˆy chuyˆn ´ ` a ım a ınh o aa o¯ a ¯. a e ´n nhˆ t trong d` thi vˆ hu.´.ng, v.v. ´ ngˇa a ¯ˆ . o o o Mˆi quan tˆm th´. hai vˆ kh´ canh l´ thuyˆt, do mˆi liˆn hˆ v´.i l´.p c´c b`i to´n quy ´ ` ´ ´ o a u e ıa . y e o e eoo a a a . ˙ giai bˇ ng thuˆt to´n v´.i d o ph´.c tap d a th´.c theo m v` n (sˆ c´c ’˙` ´ hoach nguyˆn m` c´ thˆ ’ a e ao e a a o ¯ˆ u . ¯ u a oa . . . canh v` c´c d ınh cua d` thi). a a ¯˙ ’ ˙ ¯o . ’ˆ . X´t b`i to´n sau xˆy du.ng d` thi con bˆ phˆn Gp cua d` thi vˆ hu.´.ng G trong d o bˆc ˙ ¯ˆ . o o ’o eaa a ¯o . ˆ oa ¯´ a . . . . ˙ a c´c d ınh cua d` thi Gp thoa m˜n t´ chˆ t cho tru.´.c. ´ ’ a ¯˙ ’ ˙ ¯o . ’ˆ ˙ a ınh a ’ cu o B`i to´n 7.5.1 (B`i to´n d` thi bˆ phˆn c´ r`ng buˆc vˆ d ınh) Gia su. G = (V, E ) l` d` o ` ¯˙ . e’ ˙˙ ’’ a a a a ¯o . o a o a ˆ a ¯ˆo . . .´.ng v´.i chi ph´ c tu.o.ng u.ng v´.i mˆ i canh e ∈ E. Ngo`i ra, cho tru.´.c c´c sˆ ˜. ´ thi vˆ hu o .o o ıj ´ o o a oao j nguyˆn du.o.ng δi , i = 1, 2, . . . , n. Vˆ n d` d ˇt ra l` t`m mˆt d` thi bˆ phˆn G∗ cu a G sao cho ´ e. ˙ ’ e a ¯ˆ ¯a aı o ¯ˆ . o a o . . . p bˆc cu a c´c d ı’nh vi tu.o.ng u.ng d` thi G∗ bˇ ng δi , v` tˆ’ng cu a c´c canh trong G∗ l´.n nhˆ t ˙ ¯ˆ . p ` ´ a ˙ a ¯˙ ’ ˙a. ’ ´ o a ao po a . ´ ˙ nhˆ t). ’a (hoˇc nho a . Hiˆ’n nhiˆn, v´.i d` thi G v` c´c sˆ δi cho tru.´.c, c´ thˆ’ khˆng tˆn tai d` thi bˆ phˆn ˙ ˙ ´ ` . ¯ˆ . o a e e o ¯o . ˆ aa o o oeo o o . . ˙ m˜n c´c r`ng buˆc vˆ d ınh. Hai d iˆu kiˆn cˆn (nhu.ng khˆng d u-tai sao?) dˆ’ tˆn˙o ` ¯˙ ` ` ¯e ` ’aaa ’ ˙. ’ Gp thoa oe ¯e ea o¯ . . tai d` thi bˆ phˆn chˆ p nhˆn d u.o.c l` ´ . ¯ˆ . o a o a a¯. a . . . δi ≤ dG (vi ), v´.i moi d ınh vi ∈ V . ¯˙ ’ o v` a n ˜ δi chˇn. a i=1 Diˆu kiˆn sau suy tru.c tiˆp t`. t´ chˆ t: tˆ’ng c´c bˆc cua c´c d ınh bˇ ng hai lˆn sˆ c´c -` ˙ ` ´ ´ ` oa a´ a a ˙ a ¯˙ ’ ’ e e e u ınh a o a . . . canh. . http://www.ebook.edu.vn 189
´ ´ ` Tˆp con M ⊂ E goi l` mˆt cˇp gh´p nˆu hai canh bˆ t k` trong M khˆng kˆ nhau. a .aoa ee ay o e . .. . .i ı˙ a ’. ıa ˙ ’ Chi ph´ cua cˇp gh´p M d .nh ngh˜ bo e ¯i c(M ) = cj . ej ∈M Ta c´ b`i to´n sau: oa a B`i to´n 7.5.2 (B`i to´n d oi s´nh v´.i chi ph´ l´.n nhˆ t) T`m cˇp gh´p M ∗ c´ chi ph´ l´.n ´ ´ a a a a ¯ˆ a o ıo a ı a e o ıo . ´ nhˆ t. a B`i to´n d ˆi s´nh v´.i chi ph´ l´.n nhˆ t c´ thˆ’ ph´t biˆ’u dang b`i to´n quy hoach nguyˆn: ˙ ˙. ´ ´ a a ¯o a o ıo aoea e aa e . m z= cj xj → max j =1 sao cho m j =1 bij xj ≤ 1, i = 1, 2, . . . , n, xj ∈ {0, 1}, trong d o bij l` ma trˆn liˆn thuˆc cua G v` xj = 1 (hoˇc 0) phu thuˆc v`o ej c´ d u.o.c gh´p o˙ ’ ¯´ a ae a a oa o¯ . e . . . . . cˇp hay khˆng. a o . Hiˆ’n nhiˆn rˇ ng, b`i to´n d ˆi s´nh v´.i chi ph´ l´.n nhˆ t d oi v´.i d` thi G n`o d o l` a ¯ˆ o ¯o . ˆ a ¯´ a ˙ e` ´ ´´ e a a a ¯o a o ıo ˆ .`.ng ho.p d ac biˆt cua b`i to´n c´ r`ng buˆc vˆ bˆc cua c´c d ınh. Nˆu sˆ c´c d ınh cua o ` a ˙ a ¯˙ ´´ e˙a ’ ’ ’ e o a ¯˙ ’ ˙ ’ tru o ¯ˇ a oa e. . . . . ˆ chˇn, ta thˆm c´c canh v´.i chi ph´ bˇ ng −∞ v`o G dˆ’ thu d u.o.c mˆt d` thi d` y d u G. ˆ ¯e ˜ ˙ ` o ¯o . ¯ˆ ¯ ˙ ’ Ga e a. o ıa a ¯. .ˆ a Khi d ´ b`i to´n d u.a vˆ B`i to´n 7.5.1 trˆn d` thi G trong d o tˆ t ca c´c δi = 1. Nghiˆm cua `aa ´’ ¯´ a ˙ a ˙ ’ ¯o a a ¯ e e ¯o . ˆ e. . b`i to´n sau bˇ ng c´ch bo qua tˆ t ca c´c canh c´ chi ¯a ˜ a ` b`i to´n ban d` u dˆ d`ng suy ra t` a a ´’ ˙’ a ˙a . aa ˆe u a a o ` ng −∞. Nˆu sˆ c´c d ınh cua G le th` ta thˆm mˆt d ınh cˆ lˆp v`o G tru.´.c khi xˆy ˆ˙ ı ˆ ´ o a ¯˙ ´ ’ ˙ ’ ’ o ¯˙ .’ ph´ bˇ ıa e e oa a o a . du.ng d` thi G v` ´p dung l´ luˆn trˆn. ¯o . ˆ aa ya e . . . Tu.o.ng u.ng v´.i b`i to´n t` cˇp gh´p c´ chi ph´ l´.n nhˆ t l` b`i to´n phu c´ chi ph´ ´ ˙o ’ ´ oa a ım a eo ıo aaa a ı . ˙ nhˆ t, t´.c l`: T` phu E ∗ cua G sao cho tˆ’ng chi ph´ ej ∈E ∗ cj nho nhˆ t. B`i to´n n`y ˙ ´ ´ ’ a u a ım ˙ ’ ˙ ’ ˙a ’ nho o ı aaa ˙ ph´t biˆ’u dang quy hoach nguyˆn nhu. sau: ’a ˙. c´ thˆ oe e e . m z= cj xj → min j =1 sao cho m j =1 bij xj≥ 1, i = 1, 2, . . . , n, xj ∈ {0, 1}, trong d o xj = 1 (hoˇc 0) phu thuˆc v`o ej c´ thuˆc phu E ∗ hay khˆng. ˙ ’ ¯´ a oa o o o . . . . http://www.ebook.edu.vn 190
v3 v5 • • .......................................................................... ......................................................................... .. . .. . ... . ....... ... . ....... . . . ... . ... . . .... .... . ... . . ... .... . .... . . . ... .... . ... .... . . . . .... . .... . ... ... . .... .... . . . ... ... .... . .... . . . . .... . .... ... . ... . . .... . .... . . ... ... . .... .... . . . . ... .... . ... .... . . . . .... . .... . ... ... . .... .... . . . ... ... .... . .... . . . . .... . .... ... . ... . . .... . .... . .... . ... ... . .... . . v1 • • v6 . . .. • .................................... ....................................................................... . ............................................................................................................ .. .... .. . . .. . . . ... . . . . . . v2 . . . ... . ... . . . . . . . ... . ... . . . . . . . . ... . ... . . . . . . . . . . . ... ... . . . . . . . . . ... . . ... . . . . . . . ... . . ... . . . . . . . . ... . ... . . . .. . . • • . ........................................................................ . ...................................................................... . . v4 v7 v3 v5 •..................................................................................................................................................• . .. . . .......... ........... . . . . . .. .. . .... . .. .... .. . . . . .... .... . . . . .... . .... ... . ... . .... .... . . . .... .... . . . ... . ... . .... .... . . . .... .... . . . .... . .... . ... .. . . . .... . .... . . . . .... .... . .. . . .... .. .... .. . . . .... .... . . . ... . .... .. .... . . . . .... . .... . . . .... .... . ... . . ... . .... . .... . v1 • • v6 . • .... . .... .... .... .... .... ............................................................................ . ...................................................................... .... ... ... ... ... ... . .. . .. . . . . . . v2 . . ... . ... . . . . . . . . ... ... . . . . . . . . . ... . ... . . . . . . . . . . ... ... . . . . . . . . . ... ... . . . . . . . . ... . . ... . . . . . . . . ... . . ... . . .. . • • . . ........................................................................ ......................................................................... . v4 v7 ˙ ’ H` 7.4: (a) Cˇp gh´p. (b) Phu. ınh a e . H` 7.4(a) minh hoa d` thi v´.i cˇp gh´p d u.o.c v˜ bˇ ng d oan n´t d u.t v` H` 7.4(b) e ¯. e ` ¯. ınh . ¯o . o a ˆ a e ¯´ a ınh . .o.c v˜ bˇ ng d oan n´t d u.t trong c`ng d` thi. ` ˙¯ ’ minh hoa phu d u . e a ¯. e ¯´ u ¯o . ˆ . Trong tru.`.ng ho.p tˆ t ca c´c canh c´ chi ph´ bˇ ng nhau (chˇng han 1) th` b`i to´n ı` ˙ ’ ´’ . a ˙a . o o a a ıa a . .i chi ph´ l´.n nhˆ t v` b`i to´n t` phu v´.i chi ph´ nho nhˆ t d u.a vˆ b`i to´n t` ´ ´ ´ ` a a ım ˙o ’ ˙ a¯ ’ d oi s´nh v´ ¯ˆ a o ıo a a a a ım ı e cˇp gh´p l´.n nhˆ t t´.c l` t` cˇp gh´p c´ sˆ canh nhiˆu nhˆ t v` b`i to´n t` phu nho nhˆ t ´ ´ ` ´ ´ ˙’ ˙a ’ a eo a u a ım a e oo. e a a a a ım . . tu.o.ng u.ng. Nˆu d` thi G c´ n d ınh, khi d o sˆ phˆn tu. cua cˇp gh´p l´.n nhˆ t khˆng vu.o.t ´o ¯´ o ` ´a˙˙a ´ o ¯˙ ’ ’’. ´ e ¯ˆ . eo a o . qu´ [n/2]. Tuy nhiˆn, sˆ n`y khˆng phai l´c n`o c˜ng d at d u.o.c; chˇng han, d` thi “h` ˙’ ´ ˙ u a u ¯. ¯ . ’ a e oa o a ¯ˆ . ınh o . sao” trong H` 7.5 c´ cˇp gh´p l´.n nhˆ t v´.i sˆ phˆn tu. 1. aoo` ´ ´a˙ ’ ınh oa eo . Tru.`.ng ho.p d ac biˆt khi c´c chi ph´ cj tu` y nhu.ng d` thi l` hai phˆn, th` b`i to´n ` o . ¯ˇ e a ı y´ ¯ˆ . a o a ıa a . . .a vˆ b`i to´n phˆn cˆng cˆng viˆc, mˆt b`i to´n quen t` cˇp gh´p c´ chi ph´ nho nhˆ t d u ` a a ´ ˙ ’ a¯ ım a eo ı e ao o e oaa . . . ˙ a Vˆn tr` hoc. V´.i cˆ u tr´c d` thi d ˇc biˆt n`y, B`i to´n 7.5.1 tro. th`nh b`i to´n ´ ’ ˙a ’ thuˆc cu o a u. oa u ¯o . ¯a ˆ ea aa aa . . . . a˙ ’ vˆn tai. . Muc d´ ch´ cua phˆn n`y l` tr` b`y b`i to´n vˆ cˇp gh´p l´.n nhˆ t cua d` thi ` a `a ´’ˆ . ¯ıch ınh ˙ ’ a ˙ ¯o . a a a ınh a a e. eo .i b`i to´n luˆng l´.n nhˆ t. Vˆ c´c thuˆt to´n giai quyˆt c´c ` ´ ` ´ `a ´ ˙ ’ hai phˆn trong mˆi liˆn hˆ v´ a a o e eo a o o a e a a ea . . .`.ng ho.p tˆ’ng qu´t c´ thˆ’ xem t`i liˆu dˆn [14], [30]. ˙ ˙ ˜ b`i to´n cˇp gh´p trong tru o aaa e .o aoe aea . . http://www.ebook.edu.vn 191
•............ • • .. . ... . .. . . .. .. . ... . ... . . ... ... ... ... . . ... ... . ... ... . . ... .. ... ... . . ... ... . ... ... . ... . ... ... . ... . ... ... . ... .. . ... . ... ... ... . . .. ... .. . ... . ... ... . ... ... . ... . ... . ... ... . ... ... . ... . ... ... . .... . ... . .... . ... . ... ... . ... .. . ... . ....... • • • ........................................................................ . ... ......................................................................... . .. ... . ... . ..... . ... . ..... .. ... . ... . .... ... . ... . ... . ... ... . . . . ... ... ... . ... . ... ... . ... ... . . . ... ... ... . ... . . ... . ... ... ... . . ... . ... . ... ... . . ... ... . . ... . ... ... . ... . . ... . ... ... ... . . . ... ... . ... ... . . . ... ... ... . ... . ... . . ... ... ... . . • • • ... ... . .. . .. . - ˆ . ınh H` 7.5: D` thi h` sao. ınh o Cˇp gh´p l´.n nhˆ t trong d` thi hai phˆn ´ ` 7.5.2 a eo a ¯ˆ . o a . Tru.´.c hˆt ta bˇt d` u bˇ ng mˆt v´ du. a ¯ˆ ` ´aa ´ oe oı. . V´ du 7.5.3 (Phˆn cˆng cˆng viˆc, cˇp gh´p trong d` thi hai phˆn) Mˆt nh` m´y c´ p ` ı. ao o e a e ¯ˆ . o a o aao . . . .c hiˆn. Gia su. G = (V, E ) l` d` thi hai phˆn m` c´c d ınh l` e` ` ˙˙ ’’ a a ¯˙ ’ m´y v` q cˆng viˆc cˆn thu aa o .a e a ¯ˆ . o a a . . V = V1 ∪ V2 , v´.i V1 = {1, 2, . . . , p} v` V2 = {1, 2, . . . , q } v` c´ mˆt canh liˆn thuˆc (i, j ) nˆu ´ o a ao o . e o e . . m´y i c´ thˆ’ thu.c hiˆn cˆng viˆc j. Vˆ n d` d ˇt ra l` sˇp xˆp mˆ i m´y v´.i mˆt cˆng viˆc ˙ ´´ ˜ ´ e. a oe. eo e a ¯ˆ ¯a aa e oao oo e . . . . ˙ thu.c hiˆn. Diˆu d o c´ ngh˜ rˇ ng, t` trong G mˆt cˇp gh´p c´ sˆ phˆn tu. - ` ¯´ o ’. ` ´` e oo a ˙ ’ m` n´ c´ thˆ aoo e e e ıa a ım oa . .. ` bˇ ng p. a B`i to´n cˇp gh´p c´ thˆ’ d u.a vˆ b`i to´n mang vˆn tai nhu. sau. Ta thˆm d ınh nguˆn ˙ `a a ` a˙ ’ e ¯˙ ’ aaa e o e¯ e o . . . . s dˆn c´c d ınh thuˆc tˆp V v` t`. c´c d ınh thuˆc tˆp ´ ´ v` d ınh ra nhˆn tao s, t sau d o nˆi t` ¯e a ¯˙ a ¯˙’ ’ o a 1 a u a ¯˙ ’ a. ¯´ o u oa .. .. V2 dˆn t. G´n mˆ i cung trong d` thi thu d u.o.c, k´ hiˆu GM , c´ kha nˇng thˆng qua bˇ ng 1. ˜ ` ´ o ˙a’ ¯e a o ¯o . ˆ ¯. ye o a . Ta c´ GM l` mˆt mang vˆn tai. a˙ ’ o ao . . . Dinh l´ 7.5.4 Gia su. G l` d` thi hai phˆn d. nh hu.´.ng v´.i c´c tˆp d ı’nh r`.i nhau V1 v` -. ` ¯i ˙˙ ’’ o a a ¯˙ y a ¯ˆ . o a o o a . .o.c d inh hu.´.ng t`. c´c d ı’nh trong tˆp V dˆn c´c d ı’nh trong tˆp ´ u a ¯˙ a 1 ¯e a ¯ ˙ V2 m` trong d ´ c´c canh d u . ¯. a ¯o a . ¯ o a . . V2 . 1. Luˆng F trong mang vˆn ta i GM cho ta mˆt cˇp gh´p trong G. Dı’nh vi ∈ V1 d u.o.c d ˆi -˙ ` ´ a˙ ’ o oa e ¯ . ¯o . . .. .i d ı’nh v trong V nˆu v` chı’ nˆu luˆng F trˆn cung (v , v ) bˇ ng 1. ` ´ a ˙e ´` s´nh v´ ¯ ˙ a o 2e o e a j ij 2. Luˆng l´.n nhˆ t tu.o.ng u.ng v´.i cˇp gh´p l´.n nhˆ t. ` ´ ´ o o a ´ oa eo a . 3. Luˆng c´ gi´ tri bˇ ng #V1 tu.o.ng u.ng v´.i cˇp gh´p ho`n ha o. oa.` ` ˙ ’ o a ´ oa e a . Ch´.ng minh. Gia su. fij = 1. C´ d ung mˆt cung dˆn d ınh vi l` (s, vi ). Do d o fsi = 1. Suy ra ´’ ˙˙ ’’ ¯e ¯˙ u o ¯´ o a ¯´ . ` ` ` ´’ ` o ¯e ¯ ˙ ˙ ¯˙ ’’ luˆng dˆn d ınh vi bˇ ng 1. Do luˆng ra khoi d ınh vi bˇ ng 1 nˆn c´ d ung mˆt cung c´ dang a o a e o ¯´ o o. . http://www.ebook.edu.vn 192