Lí thuyết đồ thị part 9

Chia sẻ: ágffq ằefgsd | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

86
lượt xem 10
download

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

Danh sách liên thuộc (Incidence list) - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng (có thể cài đặt bằng mảng (array) hoặc danh sách liên kết động (linked list)), trong đó mỗi phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các...

Chủ đề:

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

Lưu

Nội dung Text: Lí thuyết đồ thị part 9

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ˆ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 ım 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 . 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 . ` n d iˆu chınh. ` ˙ ’ goi l` dˆy chuyˆ ¯ e .aa 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 . 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 . 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 }. 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 . 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 ◦ (Φκ ), 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 . . . 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 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 . 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 a a 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 . . 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 )] 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 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ˆt d` thi bˆ phˆn G∗ cu a G sao cho ´ e. ˙ ’ e a ¯ˆ ¯a a ım 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. . 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` cˇp gh´p M ∗ c´ chi ph´ l´.n ´ ´ a a a a ¯ˆ a o ıo a ım 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 . . . . 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 . . 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. . 192
(vi , x) c´ fix = 1 l` (vi , vj ). Tu.o.ng tu. chı c´ mˆt cung dang (x, vj ) c´ fxj = 1 l` (vi , vj ). Vˆy . ˙o o ’ o a o a a . . . ´ ´ ` nˆu M l` tˆp c´c cung (vi , vj ) sao cho fij = 1 th` hai canh bˆ t k` trong M khˆng kˆ nhau. e aa a ı ay o e . . e˙ ’ N´i c´ch kh´c M l` cˇp gh´p cua G. oa a aa . C´c phˆn c`n lai suy t`. sˆ c´c d ınh cua V1 d u.o.c d oi s´nh bˇ ng gi´ tri cua luˆng tu.o.ng ` `o. ´ ´ ` u o a ¯˙ ’ ˙ ’ a.˙ ’ a a ¯ . ¯ˆ a a o u.ng. ´ Dinh l´ trˆn chı ra rˇ ng c´ thˆ’ ´p dung thuˆt to´n t` luˆng l´.n nhˆ t dˆ’ x´c d .nh -. ˙ ´˙ ` a ım ` ˙ ’ ye a o ea a o o a ¯e a ¯i . . .n nhˆ t cua d` thi hai phˆn. ´’o ` a ˙ ¯ˆ . cˇp gh´p l´ a eo a . Cˇp gh´p ho`n ha o trong d` thi hai phˆn ` ˙ ’ 7.5.3 a e a ¯ˆ . o a . Ta c´ d inh ngh˜ sau o ¯. ıa -. Dinh ngh˜ 7.5.5 Cˇp gh´p ho`n hao trong d` thi hai phˆn G = (V1 ∪ V2 , E ) l` cˇp gh´p ` ˙’ ıa a e a ¯ˆ . o a aa e . . ˜i d ınh a ∈ V1 tˆn tai b ∈ V2 sao cho (a, b) ∈ E. `. m` mˆ ¯˙ ao’ o ´ Nˆu S ⊂ V1 , ta d at e ¯ˇ. `. Γ(S ) := {vj ∈ V2 | tˆn tai vi ∈ S sao cho (vi , vj ) ∈ E }. o Gia su. G c´ cˇp gh´p ho`n hao. Nˆu S ⊂ V1 ta cˆn c´ ´ `o ˙˙ ’’ ˙ ’ oa e a e a . #S ≤ #Γ(S ). Ta s˜ chı ra rˇ ng nˆu #S ≤ #Γ(S ) v´.i moi tˆp con S cua V1 th` G c´ mˆt cˇp gh´p ho`n ` ´ e˙ ’ ˙ ’ a e o .a ı ooa e a . .. ˙ o. Kˆt qua n`y d u.o.c ch´.ng minh bo.i Hall v` goi l` D. nh l´ d ´m cu.´.i cua Hall do V1 l` -i ´ ’ ˙a¯. ’ ˙’ ˙ ’ ha e u a.a y ¯a o a tˆp nh˜.ng ngu.`.i d an ˆng v` V2 l` tˆp nh˜.ng ngu.`.i d `n b` v` tˆn tai canh nˆi vi ∈ V1 dˆn o ¯a a a ` . . ´ ´ a u o ¯` o a aa u o o ¯e . . vj ∈ V2 nˆu vi v` vj u.ng th´ nhau; d inh l´ cho mˆt d iˆu kiˆn dˆ’ ngu.`.i d `n ˆng c´ thˆ’ ˙ ˙ ´ o ¯` e a ıch ¯. y e e ¯e o ¯a o oe . . .´.i ngu.`.i m` th´ cu o o ınh ıch. -. `.a ´ ´ Dinh l´ 7.5.6 Tˆn tai cˇp gh´p ho`n ha o nˆu v` chı’ nˆu ˙ ’ e a ˙e y o e a . #S ≤ #Γ(S ) (7.2) v´.i moi tˆp con S cu a V1 . ˙ ’ o .a . Ch´.ng minh. Ta chı cˆn ch´.ng minh nˆu d iˆu kiˆn (7.2) d ung th` tˆn tai cˇp gh´p ho`n ˙` e ¯` ´ ı` . a ’a u u e e ¯´ o e a . . - ˇt n1 = #V1 v` (P, P ) l` thiˆt diˆn nho nhˆ t trong mang vˆn tai. Nˆu ta ch´.ng ˜a ´ ´ ´ ˙ ’ ˙ ’ a˙ ’ hao. Da a e e a e u . . . . minh rˇ ng kha nˇng cua thiˆt diˆn n`y bˇ ng n1 th` luˆng l´.n nhˆ t c´ gi´ tri bˇ ng n1 . Cˇp ` ´ea` a oa.` ı` ´ ˙a ’ ˙ ’ a e a o o a a . . .o.ng u.ng v´.i luˆng l´.n nhˆ t s˜ l` cˇp gh´p ho`n hao. o` ´ ˙ ’ gh´p tu e ´ o o a eaa e a . 193
Ch´.ng minh bˇ ng phan ch´.ng. Gia su. ngu.o.c lai, kha nˇng cua thiˆt diˆn nho nhˆ t ` ´e ´ ˙ ’ ˙˙ ’’ ˙a ’ ˙ ’ ˙ ’a u a u e .. . .n n . Nhˆn x´t rˇ ng kha nˇng cua thiˆt diˆn n`y bˇ ng sˆ c´c canh trong tˆp ˜ ae` ´ea` ´ ˙ ’ ˙a ’ ˙ ’ (P, P ) nho ho a e a oa . a . . . 1 ˜ M = {(x, y ) | x ∈ P, y ∈ P }. Mˆt phˆn tu. cua M c´ mˆt trong ba dang: ` a˙˙ ’’ o oo . . . Loai 1: (s, vi ), vi ∈ V1 . . Loai 2: (vi , vj ), vi ∈ V1 , vj ∈ V2 . . Loai 3: (vj , t), vj ∈ V2 . . ˜ ´ oa . ´ Ch´ng ta s˜ dˆm sˆ c´c canh trong mˆ i loai. u e ¯e o. ˜ı ´ ´ea ˙a ’ ˙ ’ Nˆu V1 ∈ P th` kha nˇng cua thiˆt diˆn l` n1 ; do d o e e ¯´ . V1∗ = V1 ∩ P ´ `. kh´c trˆng. Suy ra tˆn tai n1 − #V1∗ canh loai 1 trong E . a o o . . Ta phˆn hoach R(V1∗ ) th`nh c´c tˆp ho.p a a aa . . . ˜ X = R(V1∗ ) ∩ P Y = R(V1∗ ) ∩ P . v` a Khi d o tˆn tai ´ nhˆ t #V1∗ canh loai 3 trong E. Do d o tˆn tai ´ ho.n ¯´ ` . ıt a ´ ¯´ ` . ıt o o . . n1 − (n1 − #V1∗ ) − #X = #V1∗ − #X canh loai 2 trong E. M` mˆ i phˆn tu. cua Y d ong g´p nhiˆu nhˆ t mˆt canh loai 2, nˆn ˜ ` ` ´o. a˙˙ ’’ ao ¯´ o e a e . . . . #Y < #V1∗ − #X. Vˆy a . #R(V1∗ ) = #X + #Y < #V1∗ . Diˆu n`y mˆu thuˆn v´.i (7.2). Do d o tˆn tai cˇp gh´p ho`n hao. -` ˜ ¯´ ` . a ˙ ’ ea a ao o e a . V´ du 7.5.7 C´ n m´y t´ v` n ˆ’ d˜ Mˆ i m´y t´ tu.o.ng th´ v´.i m ˆ’ d˜ v` mˆi ˆ’ ˙ ˙ ˜˙ ˜ ı. o a ınh a o ¯ıa. o a ınh ıch o o ¯ıa a o o .o.ng th´ v´.i m m´y t´ .i mˆt ˆ’ d˜ m` n´ tu.o.ng a ınh. C´ thˆ’ gh´p mˆ i m´y t´ v´ ˙ .˙ ˜ d˜ tu ¯ıa ıch o oee o a ınh o o o ¯ıa a o th´ ıch? Dˇt V1 l` tˆp c´c m´y t´ v` V2 l` tˆp c´c ˆ’ d˜ Ta cho tu.o.ng u.ng canh (vi , vj ) nˆu -a ˙ ´ aa a a ınh a a a a o ¯ıa. ´ e . . . . .o.ng th´ v´.i ˆ d˜ v ∈ V . Ch´ y rˇ ng moi d ınh c´ bˆc bˇ ng m. Dˇt -a ˜ u´ ` oa ` . ¯˙ ’ m´y t´ vi ∈ V1 tu a ınh ıch o o ¯ıa j a .a . 2 194
S = {v1 , v2 , . . . , vk } ⊂ V1 . Khi d ´ c´ km canh xuˆ t ph´t t`. S. Nˆu l := #Γ(S ) th` Γ(S ) ´ ´ ¯o o a au e ı . . S. Do d ´ ` ´ ´ nhˆn nhiˆu nhˆ t lm canh dˆn t` a e a ¯e u ¯o . . km ≤ lm. Nˆn e #S = k ≤ l = #Γ(S ). Theo Dinh l´ d am cu.´.i Hall, tˆn tai cˇp gh´p ho`n hao. Vˆy c´ thˆ’ gh´p mˆ i m´y t´ v´.i -. ˙ ˜ `.a ˙ ’ y ¯´ o o e a aoee o a ınh o . . .o.ng th´ mˆt ˆ’ d˜ tu .˙ o o ¯ıa ıch. 195
196