Đồ thị và các thuật toán – Chương 7: Mạng vận tải

Chia sẻ: Lão Lão | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

22
lượt xem 4
download

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

Đồ thị và các thuật toán – Chương 7: Mạng vận tải. Chương này cung cấp cho người học những kiến thức cơ bản về: Bài toán luồng lớn nhất, các cải biên đơn giản của bài toán luồng lớn nhất, luồng với chi phí nhỏ nhất, cặp ghép. Mời các bạn cùng tham khảo.

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: Mạng vận tải

Chu.o.ng 7 a.n ta˙’i Ma.ng vˆ 7.1 Mo˙’. d`au ¯ˆ Mˆo.t trong nh˜ u.ng b`ai to´an l´ y th´ u v`a quan tro.ng cu˙’a l´ y thuyˆe´t d¯`ˆo thi. l`a x´ac d¯i.nh gi´a tri. l´o.n nhˆa´t cu˙’a luˆ `ong d¯u.o..c truyˆ`en t` u. mˆo.t d¯ı˙’nh nguˆ`on s cu˙’a d¯`oˆ thi. d¯ˆe´n mˆo.t d¯ı˙’nh d¯´ıch t. Trong khung ca˙’nh d¯o´, mˆo˜i cung (vi , vj ) cu˙’a d¯`oˆ thi. G d¯u.o..c gˇa´n v´o.i mˆo.t kha˙’ nˇang thˆong qua qij l`a sˆo´ lu.o..ng luˆ `ong l´o.n nhˆa´t c´o thˆe˙’ ta˙’i qua cung n`ay. B`ai to´an n`ay v`a nh˜ u.ng ca˙’i biˆen cu˙’a n´o c´o rˆa´t nhiˆ`eu u´ ng du.ng trong thu. c tˆe´, chˇa˙’ng ha.n, x´ac d¯.inh mˆa.t d¯oˆ. giao thˆong l´o.n nhˆa´t gi˜ . . u.a hai v` ung trong ba˙’n d¯`ˆo giao thˆong d¯u.o..c biˆe˙’u diˆ˜en bo˙’.i mˆo.t d¯`ˆo thi.. Trong v´ı du. n`ay, l`o.i gia˙’i cu˙’a b`ai to´an luˆ `ong l´o.n nhˆa´t c˜ung chı˙’ ra nh˜ u.ng no.i “ba˙’o ho`a” trˆen ma.ng giao thˆong v`a ta.o mˆo.t “tˇa´c ngh˜en” khi luˆ `ong tˆa.p trung v`ao gi˜ u.a hai vi. tr´ı n`ao d¯o´. Phu.o.ng ph´ap gia˙’i b`ai to´an luˆ `ong l´o.n nhˆa´t t` u. s d¯ˆe´n t d¯u.a ra lˆ `an d¯`ˆau tiˆen bo˙’.i Ford v`a Fulkerson [27] v`a k˜ y thuˆa.t “g´an nh˜an” cu˙’a ho. l`a co. so˙’. cho nh˜ u.ng thuˆa.t to´an kh´ac gia˙’i quyˆe´t nh˜. `ong l´o.n nhˆa´t: u ng vˆa´n d¯`ˆe liˆen quan. C´o mˆo.t sˆo´ ca˙’i biˆen cu˙’a b`ai to´an luˆ 1. Gia˙’ su˙’. rˇ`a ng mˆo˜i cung cu˙’a d¯`oˆ thi. khˆong chı˙’ d¯u.o..c gˇa´n v´o.i kha˙’ nˇang qij cho biˆe´t cˆa.n trˆen cu˙’a luˆ `ong trˆen cung (vi , vj ) m`a c`on “kha˙’ nˇang” rij cho cˆa.n du.´o.i cu˙’a luˆ `ong trˆen cung . . . . n`ay. Trong tru `o ng ho. p nhu vˆa.y, khˆong phai l´ ˙ ’ uc n`ao mˆo.t tˆa.p chˆa p nhˆa.n d¯u.o..c c´ac gi´a ´ tri. cu˙’a luˆ `ong c˜ung thoa˙’ m˜an c` ung l´ uc hai r`ang buˆo.c n`ay. Tuy nhiˆen-n´oi chung-nhiˆ `eu ` ` ´ luˆong thoa˙’ d¯iˆeu kiˆe.n n`ay, v`a nˆeu ngo`ai c´ac kha˙’ nˇang c`on c´o c´ac chi ph´ı cij tu o ng u . . . ´ ng mˆo.t d¯o.n vi. luˆ `ong do.c theo c´ac cung, th`ı b`ai to´an tro˙’. th`anh t`ım luˆ `ong chˆa´p nhˆa.n d¯u.o..c v´o.i chi ph´ı nho˙’ nhˆa´t t` u. s d¯ˆe´n t. 2. X´et tru.`o.ng ho..p d¯`oi ho˙’i luˆ`ong l´o.n nhˆa´t gi˜ u.a mo.i cˇa.p d¯ı˙’nh. Mˇa.c d`u b`ai to´an n`ay c´o thˆe˙’ gia˙’i bˇ`a ng n(n − 1)/2 lˆ `ong l´o.n nhˆa´t t` `an lˇa.p c´ac b`ai to´an luˆ u. s d¯ˆe´n t nhu.ng c´ach l`am n`ay qu´a thˆo! Tu.o.ng tu.. v´o.i t`ım tˆa´t ca˙’ c´ac d¯u.`o.ng d¯i ngˇa´n nhˆa´t, o˙’. d¯ˆay c˜ `an ung cˆ 173 http://www.ebook.edu.vn
mˆo.t thuˆa.t to´an chuyˆen du.ng d¯ˆe˙’ gia˙’i n´o-v`a trong tru.`o.ng ho..p d¯`ˆo thi. vˆo hu.´o.ng, phu.o.ng ph´ap gia˙’i quyˆe´t n´o khˆong liˆen quan d¯ˆe´n l`o.i gia˙’i cu˙’a b`ai to´an luˆ `ong l´o.n nhˆa´t gi˜ u.a hai d¯ı˙’nh s v`a t. 3. Nˆe´u thay cho mˆo.t d¯ı˙’nh nguˆ `on v`a mˆo.t d¯ı˙’nh d¯´ıch, ta kha˙’o s´at mˆo.t sˆo´ nguˆ`on v`a mˆo.t sˆo´ . d¯´ıch, v´o i c´ac h`ang ho´a kh´ac nhau gi˜ . ˙ ’ . u a hai tˆo ho. p nguˆ `on-d¯´ıch kh´ac nhau, th`ı b`ai to´an cu..c d¯a.i tˆo˙’ng sˆo´ tˆa´t ca˙’ c´ac luˆ u. c´ac nguˆ `ong t` `on d¯ˆe´n c´ac d¯´ıch l`a b`ai to´an luˆ`ong d¯a-h`ang ho´a. Trong b`ai to´an n`ay, kha˙’ nˇang qij cu˙’a cung (vi , vj ) l`a cˆa.n trˆen cu˙’a tˆo˙’ng c´ac luˆ `ong . v´o i c´ac loa.i h`ang ho´a trˆen cung d¯´o. 4. Gia˙’ thiˆe´t (ˆa˙’n) trong tˆa´t ca˙’ c´ac tru.`o.ng ho..p trˆen l`a sˆo´ lu.o..ng luˆ `ong d¯ˆe´n bˇ`a ng sˆo´ lu.o..ng luˆ . . `ong ra. Nˆe´u ta bo˙’ gia˙’ thiˆe´t n`ay v`a x´et tru `o ng ho. p luˆ . `ong ra kho˙’i mˆo.t cung bˇ`a ng luˆ . `ong d¯ˆe´n nhˆan v´o i mˆo.t sˆo´ nguyˆen khˆong ˆam n`ao d¯o´, th`ı b`ai to´an luˆ `ong l´o.n nhˆa´t (t` u. s d¯ˆe´n t) d¯u.o..c xem nhu. b`ai to´an trong c´ac d¯`ˆo thi. v´o.i c´ac lo..i nhuˆa.n. Trong da.ng n`ay, c´ac luˆ `ong c´o thˆe˙’ “d¯u.o..c sinh ra” hoˇa.c “bi. hˆa´p thu.” bo˙’.i d¯`oˆ thi., v`a do vˆa.y luˆ `ong v`ao s v`a luˆ ˙ ’ ˙ ’ `ong ra kho˙’i t c´o thˆe thay d¯ˆo i ho`an to`an d¯oˆ. c lˆa.p. C´ac b`ai to´an vˆ `ong d¯u.o..c nghiˆen c´ `e luˆ u.u nhiˆ u.ng u `eu v`a c´o nh˜ ´.ng du.ng thu..c tiˆ˜en. Mu.c d¯´ıch cu˙’a chu.o.ng n`ay tr`ınh b`ay ngˇa´n go.n c´ac b`ai to´an thu.`o.ng gˇa.p, chı˙’ ra mˆo´i liˆen hˆe. gi˜ u.a ch´ . ung v`a xˆay du. ng mˆo.t sˆo´ thuˆa.t to´an gia˙’i quyˆe´t. Chu.o.ng n`ay s˜e tha˙’o luˆa.n b`ai to´an luˆ `ong l´o.n nhˆa´t t` u. s d¯ˆe´n t v`a c´ac tˆo˙’ng qu´at ho´a cu˙’a n´o (1), (2), (3) v`a (4) trˆen. Do c´ac thuˆa.t to´an gia˙’i b`ai to´an luˆ `ong d¯a-h`ang ho´a rˆa´t kh´ac biˆe.t vˆ`e ba˙’n chˆa´t, v`a khˆong pha˙’i d¯`ˆeu hiˆe.u qua˙’ nhu phu o ng ph´ap g´an nh˜an, nˆen s˜e khˆong d¯u.o..c . . . d¯`ˆe cˆa.p o˙’. d¯aˆy. Ba.n d¯o.c quan tˆam c´o thˆe˙’ xem [30] v`a c´ac t`ai liˆe.u dˆa˜n k`em theo. 7.2 B` ai to´ an luˆ o.n nhˆ `ong l´ a´t Luˆ`ong l´o.n nhˆa´t trˆen ma.ng vˆa.n ta˙’i G l`a mˆo.t luˆ `ong v´o.i gi´a tri. l´o.n nhˆa´t. N´oi chung c´o mˆo.t v`ai luˆ`ong v´o.i c`ung gi´a tri. l´o.n nhˆa´t. Phˆ `an n`ay tr`ınh b`ay thuˆa.t to´an t`ım luˆ `ong l´o.n nhˆa´t. Y ´ tu.o˙’.ng cu˙’a thuˆa.t to´an l`a: kho˙’.i d¯`aˆu v´o.i luˆ `ong n`ao d¯o´ v`a tˇang gi´a tri. cu˙’a luˆ`ong cho d¯ˆe´n khi . . khˆong thˆe˙’ tˇang d¯u o. c n˜ . u a. Kˆe´t qua˙’ ta c´o luˆ . `ong l´o n nhˆa´t. V´ı du. 7.2.1 D - `ˆo thi. c´o hu.´o.ng trong H`ınh 7.1 biˆe˙’u diˆ˜en so. d¯`ˆo ma.ng dˆa˜n dˆ `au. Dˆ `au d¯u.o..c dˆa˜n t`u. t`au s v`a d¯u.o..c bo.m thˆong qua ma.ng d¯ˆe´n nh`a m´ay lo.c dˆ `au t. C´ac d¯ı˙’nh b, c, d v`a e l`a c´ac tra.m bo m trung gian. C´ac cung biˆeu thi. c´ac ˆong dˆan dˆau v`a hu.´o.ng di chuyˆe˙’n cu˙’a hˆe. . ˙ ’ ´ ˜ ` thˆo´ng. C´ac nh˜an trˆen c´ac cung l`a kha˙’ nˇang thˆong qua tˆo´i d¯a cu˙’a ˆo´ng dˆa˜n. B`ai to´an d¯aˇ. t ra l`a t`ım c´ach chuyˆe˙’n nhiˆ `eu nhˆa´t lu.o..ng dˆ u. t`au d¯ˆe´n nh`a m´ay v`a t´ınh gi´a tri. n`ay. H`ınh 7.1 `au t` l`a mˆo.t v´ı du. cu˙’a mˆo.t “ma.ng vˆa.n ta˙’i”. Tru ´o.c hˆe´t ta c´o: . 174 http://www.ebook.edu.vn
b 2 c • ..... ..... . . ...... • ......................................................................................................................................................................................................................................... ..... ..... ..... ...... ..... . .. ...... ..... ...... ..... ..... ...... ..... 3 . .. . .... . .. . ... . . . ..... . ...... .. . ........ ..... ..... ....... ........ 4 .............. ... ...... ..... .. ...... ..... .. . ... ..... . .. .... ... ...... ..... ... . ... ......... ..... ..... .... .... .... ...... . . . 2 . ....... ........ .. ..... ..... ..... s• ... . ...... ..... ..... .... . . . . ...... . .... ..... .... ... . • t ..... ..... ... ..... . ........ ....... ..... ..... .... ..... .. ..... . .... ..... ...... ..... ..... ...... ..... ....... ...... ..... ......... ...... ..... ..... .... ....... . ..... .. . ...... ..... ...... ..... ..... ...... 5 ..... ..... ..... ...... ...... ...... ..... ..... ..... 4 ..... ..... ..... ........... . ..... .... 2 ........................................................................................................................................................................................................................................ ..... ........ • ... • d e `e ma.ng vˆa.n ta˙’i. H`ınh 7.1: V´ı du. vˆ - .inh ngh˜ıa 7.2.2 Ma.ng vˆa.n ta˙’i l`a mˆo.t d¯o.n d¯`oˆ thi. c´o hu.´o.ng, c´o tro.ng sˆo´ G sao cho D `on) cu˙’a ma.ng, khˆong c´o cung (a) c´o mˆo.t v`a chı˙’ mˆo.t d¯ı˙’nh s, go.i l`a d¯ı˙’nh v`ao (hoˇa.c d¯ı˙’nh nguˆ d¯ˆe´n n´o. (b) c´o mˆo.t v`a chı˙’ mˆo.t d¯ı˙’nh t, go.i l`a d¯ı˙’nh ra (hoˇa.c d¯ı˙’nh d¯´ıch) cu˙’a ma.ng, khˆong c´o cung d¯i ra kho˙’i n´o. (c) mˆo˜i cung u := (vi , vj ) ∈ E d¯u.o..c g´an mˆo.t sˆo´ nguyˆen khˆong ˆam qij , go.i l`a kha˙’ nˇang cu˙’a cung u. (d) d¯`ˆo thi. vˆo hu.´o.ng nhˆa.n d¯u.o..c t` u. G bˇ`a ng c´ach bo˙’ d¯i c´ac hu.´o.ng l`a liˆen thˆong. V´ı du. 7.2.3 D - `ˆo thi. c´o hu.´o.ng trong H`ınh 7.1 l`a ma.ng vˆa.n ta˙’i. Lˆo´i v`ao l`a d¯ı˙’nh s v`a lˆo´i ra l`a d¯ı˙’nh t. Kha˙’ nˇang cung (s, b) l`a qsb = 3 v`a cu˙’a cung (b, c) l`a qbc = 2. Trong chu.o.ng n`ay, nˆe´u G l`a ma.ng vˆa.n ta˙’i ch´ y hiˆe.u d¯ı˙’nh v`ao l`a s v`a d¯ı˙’nh ung ta s˜e k´ ra l`a t. - i.nh ngh˜ıa 7.2.4 Gia˙’ su˙’. G l`a ma.ng vˆa.n ta˙’i v´o.i kha˙’ nˇang cung (vi , vj ) l`a qij . Luˆ D `ong (chˆa´p . . nhˆa.n d¯u o. c) F trong G g´an mˆo˜i cung (vi , vj ) mˆo.t sˆo´ khˆong ˆam fij sao cho (a) 0 ≤ fij ≤ qij ; v`a (b) v´o.i mˆo˜i d¯ı˙’nh vj 6= s, t, ta c´o X X fij = fji . (7.1) i i 175 http://www.ebook.edu.vn
(Tˆo˙’ng trong (7.1) lˆa´y trˆen tˆa´t ca˙’ c´ac gi´a tri. i; nˆe´u khˆong c´o cung (vi , vj ), ta d¯ˇa.t fij = 0). `ong trˆen cung (vi , vj ). V´o.i mˆo˜i j, ta go.i Ta n´oi fij l`a luˆ X fij i `ong d¯ˆe´n d¯ı˙’nh vj v`a l`a luˆ X fij i `ong ra kho˙’i d¯ı˙’nh vj . l`a luˆ - iˆ D `ong. Trong v´ı du. dˆa˜n dˆ `eu kiˆe.n (7.1) go.i l`a ba˙’o to`an luˆ `au cu˙’a H`ınh 7.1, ba˙’o to`an luˆ `ong c´o . . . `au khˆong d¯u o. c su˙’ du.ng v`a c˜ ngh˜ıa dˆ ung khˆong d¯u.o..c cˆa´p thˆem ta.i c´ac tra.m bo.m b, c, d v`a e. V´ı du. 7.2.5 C´ac ph´ep g´an fsb = 2, fbc = 2, fcz = 3, fsd = 3, fdc = 1, fde = 2, fez = 2, `ong trˆen ma.ng vˆa.n ta˙’i cu˙’a H`ınh 7.1. Chˇa˙’ng ha.n, luˆ x´ac d¯.inh luˆ `ong d¯ˆe´n d¯ı˙’nh d l`a fsd = 2, bˇ`a ng luˆ `ong ra kho˙’i d¯ı˙’nh d : fdc + fde = 1 + 2 = 3. Luˆ `ong F d¯u.o..c v˜e trong H`ınh 7.2, trong d¯o´ cung e d¯u.o..c g´an nh˜an x, y nˆe´u kha˙’ nˇang cu˙’a e `ong trˆen e l`a y. l`a x v`a luˆ b 2, 2 c • ..... ..... ..... ................................................................................................................................................................................................................................... .... ........ ...... • ..... . .. ...... ..... . ....... . .......... ..... 3, 2 . ... . .......... . ..... .... ...... .......... . ...... ..... ..... ..... 4, 3 .............. .. .... .............. ...... .... ..... ..... . .. .... ..... ... .... . ........ ..... ....... .... ..... ..... ... .... ..... .......... . .. .. 2, 1 . . ....... ...... .... ..... ..... ..... s• . . ........ . ..... ..... . . ....... . . . . ......... ....... ... . • t .... ..... ..... .... ..... .. .. .. . ..... ...... .... ..... ...... ..... ..... ...... ..... ..... ...... ..... ....... . .... ....... .. ...... ........ .. ..... ..... ...... ......... ..... ...... ....... ..... ...... ..... 5, 3 ..... ..... ..... . ........ ...... ...... ... ........ 4, 2 ..... ..... ..... ........... ...... ...... 2, 2 ......................................................................................................................................................................................................................................... ..... ..... ..... • . . . • d e `ong trˆen ma.ng vˆa.n ta˙’i cu˙’a H`ınh 7.1. H`ınh 7.2: Luˆ 176 http://www.ebook.edu.vn
Ch´ uy´ rˇ`a ng trong v´ı du. n`ay, luˆ `ong ra kho˙’i d¯ı˙’nh s l`a fsb + fsd bˇ`a ng luˆ `ong d¯ˆe´n d¯ı˙’nh t : fct + fet v`a bˇa` ng 5. Thˆa.t vˆa.y, ta c´o D- i.nh l´y 7.2.6 Gia˙’ su˙’. F l`a luˆ `ong trˆen ma.ng vˆa.n ta˙’ i G := (V, E). Khi d¯´o luˆ `ong ra kho˙’ i d¯ı˙’nh s bˇ`a ng luˆ `ong d¯ˆe´n d¯ı˙’nh t; t´. u c l`a X X fsi = fit . i i u.ng minh. Ta c´o Ch´ Ã ! Ã ! X X X X fij = fji j∈V i∈V j∈V i∈V P do mˆo˜i vˆe´ bˇ`a ng e∈E fe . V`ı vˆa.y P P P 0 = j∈V ( i∈V fij − i∈V fji ) P P P P P P P = ( i∈V fit − i∈V fti ) + ( i∈V fis − i∈V fsi ) + j∈V,j6=s,t ( i∈V fij − i∈V fji ) P P = i∈V fit − i∈V fsi do fti = 0 = fis v´o.i mo.i vi ∈ V, v`a (7.1). - i.nh ngh˜ıa 7.2.7 Gia˙’ su˙’. F l`a luˆ D - a.i lu.o..ng `ong trˆen ma.ng vˆa.n ta˙’i G. D X X fsi = fit i i `ong F. go.i l`a gi´a tri. cu˙’a luˆ B`ai to´an trˆen ma.ng vˆa.n ta˙’i G c´o thˆe˙’ ph´at biˆe˙’u: B` ai to´an 7.2.8 T`ım mˆo.t luˆ `ong chˆa´p nhˆa.n d¯u.o..c l´o.n nhˆa´t trˆen d¯`ˆo thi. G; t´ u.c l`a trong sˆo´ tˆa´t `ong trˆen G, t`ım luˆ ca˙’ c´ac luˆ . `ong F c´o gi´a tri. l´o n nhˆa´t. Thuˆa.t to´an g´an nh˜an cu˙’a Ford v`a Fulkerson [27] gia˙’i b`ai to´an n`ay du..a trˆen D - i.nh l´ y . . 7.2.10. Tru ´o c hˆe´t ta c´o mˆo.t sˆo´ kh´ai niˆe.m 177 http://www.ebook.edu.vn
D- i.nh ngh˜ıa 7.2.9 Nˆe´u c´ac d¯ı˙’nh cu˙’a d¯`oˆ thi. G = (V, E) d¯u.o..c phˆan hoa.ch th`anh hai tˆa.p con V0 v`a V˜0 (trong d¯o´ V0 ⊂ V v`a V˜0 l`a phˆ `an b`u cu˙’a V0 trong V ), th`ı tˆa.p c´ac cung cu˙’a G v´o.i d¯ı˙’nh xuˆa´t ph´at thuˆo.c V0 v`a d¯ı˙’nh kˆe´t th´ uc thuˆo.c V˜0 go.i l`a thiˆe´t diˆe.n cu˙’a G. Tˆa.p c´ac cung cu˙’a thiˆe´t diˆe.n thu.`o.ng d¯u.o..c k´ y hiˆe.u bo˙’.i (V0 → V˜0 ). Gia˙’ su˙’. G l`a ma.ng vˆa.n ta˙’i. Thiˆe´t diˆe.n (V0 → V˜0 ) t´ach s kho˙’i t nˆe´u s ∈ V0 v`a t ∈ V˜0 . Kha˙’ nˇang thˆong qua hay gi´a tri. cu˙’a thiˆe´t diˆe.n l`a tˆo˙’ng cu˙’a tˆa´t ca˙’ c´ac kha˙’ nˇang cu˙’a tˆa´t ca˙’ c´ac cung cu˙’a G v´o.i d¯ı˙’nh xuˆa´t ph´at thuˆo.c V0 v`a d¯ı˙’nh kˆe´t th´ uc thuˆo.c V˜0 ; t´u.c l`a X v(V0 → V˜0 ) := qij . (vi ,vj )∈(V0 →V˜0 ) Thiˆe´t diˆe.n nho˙’ nhˆa´t l`a thiˆe´t diˆe.n c´o kha˙’ nˇang thˆong qua nho˙’ nhˆa´t. - i.nh l´ D y 7.2.10 (D - i.nh l´ `ong l´o.n nhˆa´t) Gi´a tri. cu˙’ a luˆ y thiˆe´t diˆe.n nho˙’ nhˆa´t-luˆ `ong l´o.n nhˆa´t . u s d¯ˆe´n t bˇ`a ng kha˙’ nˇang thˆong qua cu˙’ a thiˆe´t diˆe.n nho˙’ nhˆa´t (Vm → V˜m ) t´ach s kho˙’ i t. t` Ch´ u.ng minh. Hiˆe˙’n nhiˆen rˇ`a ng, luˆ `ong l´o.n nhˆa´t t` u. s d¯ˆe´n t khˆong thˆe˙’ l´o.n ho.n v(Vm → V˜m ) do tˆa´t ca˙’ c´ac d¯u.`o.ng d¯i t` u. s d¯ˆe´n t d¯`ˆeu su˙’. du.ng ´ıt nhˆa´t mˆo.t cung cu˙’a thiˆe´t diˆe.n n`ay. Do d¯o´ `an ch´ chı˙’ cˆ u.ng minh rˇa` ng tˆ `on ta.i mˆo.t luˆ `ong d¯a.t gi´a tri. n`ay. Ta xem luˆ `ong d¯a˜ cho F tu.o.ng u. . ´ ng v´o i mˆo.t vector m chiˆ ˜ `eu v`a d¯.inh ngh˜ıa thiˆe´t diˆe.n (V0 → V0 ) bˇ`a ng d¯ˆe. quy theo thu˙’ tu.c sau: 1. Kho˙’.i ta.o, d¯ˇa.t V0 = {s}. 2. Nˆe´u vi ∈ V0 , v`a hoˇa.c fij < qij hoˇa.c fij > 0 th`ı d¯ˇa.t vj v`ao trong tˆa.p V0 . 3. Lˇa.p la.i Bu.´o.c 2 cho d¯ˆe´n khi khˆong thˆe˙’ thˆem d¯ı˙’nh n`ao v`ao V0 . C´o hai tru.`o.ng ho..p xa˙’y ra: hoˇa.c t ∈ V0 hoˇa.c t ∈ / V0 . Tru.` o.ng ho..p 1. t ∈ V0 . Theo Bu.´o.c 2 trˆen, tˆ `on ta.i mˆo.t dˆay chuyˆ u. s d¯ˆe´n t sao cho mo.i cung (vi , vj ) d¯u.o..c su˙’. du.ng `en t` . bo˙’ i dˆay chuyˆ `en theo hu ´o ng thuˆa.n (c´ac cung d¯i.nh hu.´o.ng thuˆa.n) thoa˙’ fij < qij v`a c´ac cung . . (vk , vl ) d¯u.o..c d¯.inh hu.´o.ng ngu.o..c, t´ u.c l`a hu.´o.ng t` u. vl d¯ˆe´n vk thoa˙’ flk > 0. Dˆay chuyˆ `en n`ay go.i l`a dˆay chuyˆ `en d¯iˆ `eu chı˙’nh. - ˇa.t D δf = min(vi ,vj ) [qij − fij ]; (vi , vj ) thuˆa.n hu.´o.ng, δb = min(vk ,vi ) [fkl ]; (vk , vl ) ngu.o..c hu.´o.ng 178 http://www.ebook.edu.vn
v`a δ = min[δf , δb ]. Nˆe´u ta cˆo.ng thˆem δ v`ao luˆ `ong trˆen tˆa´t ca˙’ c´ac cung d¯i.nh hu.´o.ng thuˆa.n v`a tr` u. d¯i δ trˆen tˆa´t ca˙’ c´ac cung d¯i.nh hu.´o.ng ngu.o..c trong dˆay chuyˆ `en d¯iˆ `ong thu d¯u.o..c vˆ `eu chı˙’nh th`ı luˆ `an l`a luˆ . . . `ong chˆa´p nhˆa.n d¯u o. c c´o gi´a tri. nho˙’ ho n luˆ . . - iˆ `ong ban d¯`ˆau mˆo.t lu o. ng δ. D `eu n`ay l`a hiˆe˙’n nhiˆen . . v`ı thˆem mˆo.t lu o. ng δ v`ao c´ac cung theo chiˆ . . `eu thuˆa.n khˆong vu o. t qu´a kha˙’ nˇang cu˙’a c´ac cung n`ay (do δ < δf ) v`a tr` . . . u d¯i mˆo.t lu o. ng δ v`ao c´ac cung theo chiˆ `eu ngu.o..c th`ı luˆ`ong vˆa˜n khˆong ˆam (do δ < δb ). ´ du.ng la.i v´o.i luˆ Ap `ong m´o.i theo c´ac Bu.´o.c 1-3 trˆen ta la.i thu d¯u.o..c mˆo.t thiˆe´t diˆe.n m´o.i (V0 → V˜0 ). Tru.` o.ng ho..p 2. t ∈ / V0 . Theo Bu.´o.c 2, fij = qij v´o.i mo.i cung (vi , vj ) ∈ (V0 → V˜0 ) v`a fkl = 0 v´o.i mo.i cung (vk , vl ) ∈ (V˜0 → V0 ). Do d¯o´ X X fij = qij (vi ,vj )∈(V0 →V˜0 ) (vi ,vj )∈(V0 →V˜0 ) v`a X fkl = 0; (vk ,vl )∈(V˜0 →V0 ) u.c l`a gi´a tri. cu˙’a luˆ t´ `ong bˇ`a ng X X fij − fkl (vi ,vj )∈(V0 →V˜0 ) (vk ,vl )∈(V˜0 →V0 ) v`a bˇa` ng kha˙’ nˇang thˆong qua cu˙’a thiˆe´t diˆe.n (V0 → V˜0 ). Do Tru.`o.ng ho..p 1, luˆ`ong tˇang ´ıt nhˆa´t mˆo.t d¯o.n vi., nˆen nˆe´u gia˙’ thiˆe´t tˆa´t ca˙’ c´ac kha˙’ nˇang qij l`a nh˜u.ng sˆo´ nguyˆen th`ı luˆ `ong l´o.n nhˆa´t c´o thˆe˙’ nhˆa.n d¯u.o..c sau mˆo.t sˆo´ h˜ u.u ha.n bu.´o.c . . . khi Tru `o ng ho. p 2 xa˙’y ra. Luˆ`ong n`ay c´o gi´a tri. bˇ`a ng kha˙’ nˇang thˆong qua cu˙’a thiˆe´t diˆe.n hiˆe.n ˜ h`anh (V0 → V0 ) nˆen l`a luˆ `ong l´o.n nhˆa´t v`a thiˆe´t diˆe.n tu.o.ng u´.ng c´o kha˙’ nˇang thˆong qua nho˙’ nhˆa´t. / Phu.o.ng ph´ap xˆay du..ng d¯u.o..c su˙’. du.ng d¯ˆe˙’ ch´ u.ng minh d¯i.nh l´y trˆen cho ch´ ung ta thuˆa.t ˙ ’ ` . ´ . ´ . . . . u s d¯ˆen t. Thuˆa.t to´an n`ay s˜e d¯u o. c tr`ınh b`ay du ´o i d¯aˆy. to´an d¯ˆe t`ım luˆong l´o n nhˆa t t` Xuˆa´t ph´at t`u. luˆ `ong chˆa´p nhˆa.n d¯u.o..c tu` yy´ (c´o thˆe˙’ su˙’. du.ng luˆ `ong c´o gi´a tri. bˇ`a ng khˆong) `ong bˇa` ng c´ach t`ım c´ac dˆay chuyˆ v`a sau d¯´o tˇang luˆ `en d¯iˆ `eu chı˙’nh luˆ u. s d¯ˆe´n t. Viˆe.c t`ım `ong t` 179 http://www.ebook.edu.vn
mˆo.t dˆay chuyˆ `en d¯iˆ`eu chı˙’nh luˆ`ong d¯u.o..c thu..c hiˆe.n bˇ`a ng c´ach g´an nh˜an. Khi t`ım d¯u.o..c mˆo.t dˆay chuyˆ `en d¯iˆ`eu chı˙’nh luˆ`ong, ta s˜e tˇang gi´a tri. cu˙’a luˆ `ong. Sau d¯o´ xo´a tˆa´t ca˙’ c´ac nh˜an v`a luˆ . . . . `ong m´o i d¯u o. c su˙’ du.ng d¯ˆe˙’ g´an nh˜an la.i. Nˆe´u khˆong tˆ `on ta.i dˆay chuyˆ `en d¯iˆ `eu chı˙’nh luˆ`ong ´ th`ı thuˆa.t to´an kˆet th´ ` ´ . . . ´ ˙ ’ . uc, luˆong chˆa p nhˆa.n d¯u o. c l`a l´o n nhˆa t. Thuˆa.t to´an cu. thˆe nhu sau: 7.2.1 Thuˆ a.t to´ an g´ an nh˜ an d ¯ˆe˙’ t`ım luˆ o.n nhˆ `ong l´ a´t A. Qu´ a tr`ınh g´ an nh˜ an Mˆo˜i d¯ı˙’nh chı˙’ c´o thˆe˙’ c´o mˆo.t trong ba kha˙’ nˇang: 1. d¯u.o..c g´an nh˜an v`a d¯u.o..c kiˆe˙’m tra (t´ u.c l`a n´o d¯u.o..c g´an nh˜an v`a tˆa´t ca˙’ c´ac d¯ı˙’nh liˆen . . . . thuˆo.c v´o i n´o d¯˜a d¯u o. c xu˙’ l´ y); hoˇa.c 2. d¯u.o..c g´an nh˜an v`a chu.a d¯u.o..c kiˆe˙’m tra (t´ u.c l`a n´o d¯u.o..c g´an nh˜an v`a tˆ `on ta.i d¯ı˙’nh liˆen . . . . ˙ ’. thuˆo.c v´o i n´o chu a d¯u o. c xu l´ y); hoˇa.c 3. chu.a d¯u.o..c g´an nh˜an. Nh˜an cu˙’a d¯ı˙’nh vi gˆ `om hai th`anh phˆ `an v`a c´o mˆo.t trong hai da.ng hoˇa.c (+vj , δ) hoˇa.c (−vj , δ). . . . ` ˙ ’ Trong tru `o ng ho. p d¯ˆau, c´o thˆe tˇang luˆ `ong do.c theo cung (vi , vj ); trong tru.`o.ng ho..p th´ u. hai, c´o thˆe˙’ gia˙’m luˆ`ong do.c theo cung (vi , vj ). D . . . . . . . - a.i lu o. ng δ trong ca˙’ hai tru `o ng ho. p l`a lu o. ng h`ang nhiˆ ˙ ’ . `eu nhˆa´t c´o thˆe thˆem hoˇa.c b´o t gi´a tri. cu˙’a luˆ `ong trˆen c´ac cung thuˆo.c dˆay chuyˆ `en d¯iˆ `eu chı˙’nh (trong qu´a tr`ınh xˆay du..ng) t` u. s d¯ˆe´n vi . Nh˜an cu˙’a d¯ı˙’nh vi cho ph´ep x´ac d¯i.nh dˆay chuyˆ `en d¯iˆ `eu chı˙’nh luˆ u. s d¯ˆe´n vi . `ong t` Kho˙’.i ta.o tˆa´t ca˙’ c´ac d¯ı˙’nh chu.a d¯u.o..c g´an nh˜an v`a fij = 0 v´o.i mo.i cung (vi , vj ) ∈ E. 1. G´an nh˜an cu˙’a d¯ı˙’nh s l`a (+s, δ(s) = ∞). D - ı˙’nh s d¯u.o..c g´an nh˜an v`a chu.a d¯u.o..c kiˆe˙’m tra; tˆa´t ca˙’ c´ac d¯ı˙’nh kh´ac chu.a d¯u.o..c g´an nh˜an. 2. Cho.n d¯ı˙’nh vi ∈ V d¯a˜ d¯u.o..c g´an nh˜an v`a chu.a d¯u.o..c kiˆe˙’m tra. Nˆe´u khˆong tˆ `on ta.i, thuˆa.t to´an d` . u ng, luˆ . . . . `ong F = (fij ) l`a l´o n nhˆa´t. Ngu o. c la.i, gia˙’ su˙’ (±vk , δ(vi )) l`a nh˜an cu˙’a d¯ı˙’nh vi . • G´an nh˜an (+vi , δ(vj )) cho tˆa´t ca˙’ c´ac d¯ı˙’nh vj ∈ Γ(vi ) chu.a d¯u.o..c g´an nh˜an sao cho fij < qij , trong d¯o´ δ(vj ) := min{δ(vi ), qij − fij }. 180 http://www.ebook.edu.vn
• G´an nh˜an (−vi , δ(vj )) cho tˆa´t ca˙’ c´ac d¯ı˙’nh vj ∈ Γ−1 (vi ) chu.a d¯u.o..c g´an nh˜an sao cho fji > 0, trong d¯o´ δ(vj ) := min{δ(vi ), fji }. - ı˙’nh vi d¯a˜ d¯u.o..c g´an nh˜an v`a d¯˜a d¯u.o..c kiˆe˙’m tra; c´ac d¯ı˙’nh vj x´ac d¯i.nh trˆen d¯˜a d¯u.o..c (D g´an nh˜an v`a chu.a d¯u.o..c kiˆe˙’m tra). 3. Nˆe´u d¯ı˙’nh t d¯u.o..c g´an nh˜an, chuyˆe˙’n sang Bu.´o.c 4; ngu.o..c la.i chuyˆe˙’n sang Bu.´o.c 2. Cˆ `an ch´uy´ rˇa` ng, nˆe´u V0 l`a tˆa.p c´ac d¯ı˙’nh d¯˜a d¯u o. c g´an nh˜an v`a V0 l`a tˆa.p c´ac d¯ı˙’nh chu a d¯u o..c . . ˜ . . g´an nh˜an th`ı (V0 → V˜0 ) l`a thiˆe´t diˆe.n nho˙’ nhˆa´t. B. Qu´ a tr`ınh tˇ `ong ang luˆ - ˇa.t c = t v`a chuyˆe˙’n sang Bu.´o.c 5. 4. D • Nˆe´u nh˜an cu˙’a d¯ı˙’nh c c´o da.ng (+z, δ(c)) th`ı thay luˆ`ong trˆen cung (z, c) l`a fzc bo˙’.i fzc + δ(t); `ong trˆen cung (x, z) l`a fcz bo˙’.i • Nˆe´u nh˜an cu˙’a d¯ı˙’nh c c´o da.ng (−z, δ(c)) th`ı thay luˆ fcz − δ(t); 5. Nˆe´u z = s th`ı xo´a tˆa´t ca˙’ c´ac nh˜an t` u. c´ac d¯ı˙’nh v`a chuyˆe˙’n sang Bu.´o.c 1; ngu.o..c la.i (t´ u.c . . . l`a z 6= c) d¯aˇ. t c = z v`a tro˙’ la.i Bu ´o c 5. 7.2.2 - `ˆ D o thi. d `eu chı˙’nh luˆ ¯iˆ `ong Qu´a tr`ınh t`ım mˆo.t dˆay chuyˆ `en d¯ˆe˙’ tˇang gi´a tri. cu˙’a luˆ `ong F trong d¯`oˆ thi. G = (V, E) c´o . thˆe˙’ d¯u a vˆ . . `e t`ım mˆo.t d¯u `o ng d¯i t`. u s d¯ˆe´n t trˆen d¯`oˆ thi. d¯iˆ `eu chı˙’nh luˆ `ong Gµ (F ) = (V µ , E µ ), µ µ V µ = V, E µ = E1 ∪ E2 , trong d¯o´ E1µ := {(viµ , vjµ ) | fij < qij , (vi , vj ) ∈ E}, v´o.i kha˙’ nˇang cu˙’a mˆo˜i cung (viµ , vjµ ) ∈ E1µ l`a qijµ = qij − fij , v`a E2µ := {(vjµ , viµ ) | fij > 0, (vi , vj ) ∈ E} v´o.i kha˙’ nˇang cu˙’a mˆo˜i cung (vjµ , viµ ) ∈ E2µ l`a qji µ = fij . Khi d¯o´ thu˙’ tu.c g´an nh˜an cu˙’a thuˆa.t to´an t`ım luˆ `ong l´o.n nhˆa´t trong Phˆ `an 7.2.1 ch´ınh l`a thuˆa.t to´an x´ac d¯.inh tˆa.p pha.m vi R(s) trong d¯ˆo thi. d¯iˆeu chınh luˆong G (F ). Nˆe´u t ∈ R(s), ` ` ˙ ’ ` µ t´u.c l`a nˆe´u d¯ı˙’nh t d¯u.o..c g´an nh˜an, th`ı c´o thˆe˙’ x´ac d¯i.nh mˆo.t d¯u.`o.ng d¯i t` u. s d¯ˆe´n t trong d¯`ˆo thi. Gµ (F ). Trong tru.`o.ng ho..p n`ay, dˆay chuyˆ `en d¯iˆ `eu chı˙’nh luˆ `ong cu˙’a G l`a d¯u.`o.ng d¯i P m`a c´ac µ cung cu˙’a P thuˆo.c E1 tu o ng u . . ´ ng cung d¯i.nh hu ´o ng thuˆa.n v`a c´ac cung cu˙’a P thuˆo.c E2µ d¯u.o..c . . . d¯.inh hu.´o.ng ngu.o..c. 181 http://www.ebook.edu.vn
7.2.3 Phˆ `ong an t´ıch luˆ Trong mˆo.t sˆo´ tru.`o.ng ho..p ta muˆo´n phˆan t´ıch mˆo.t luˆ `ong ph´ u.c ta.p th`anh tˆo˙’ng cu˙’a nh˜ u.ng `ong d¯o.n gia˙’n ho.n. D luˆ - iˆ `eu n`ay khˆong nh˜ u.ng c´o y ´ ngh˜ıa thu..c tiˆ˜en m`a c`on g´op phˆ `an hiˆe˙’u tˆo´t . ho n ba˙’n chˆa´t cu˙’a luˆ `ong trˆen ma.ng vˆa.n ta˙’i, v`a ngo`ai ra phu.c vu. mˆo.t sˆo´ thuˆa.t to´an vˆ`e luˆ`ong. K´ `ong trong d¯`ˆo thi. G m`a c´ac cung (vi , vj ) ∈ S c´o fij = h v`a c´ac cung y hiˆe.u h ◦ (S) l`a luˆ (vi , vj ) ∈ / S c´o fij = 0. Ch´ ´ rˇ`a ng h ◦ (S) khˆong nhˆa´t thiˆe´t l`a mˆo.t luˆ uy `ong v´o.i tˆa.p S tu`yy ´. Hiˆe˙’n nhiˆen rˇ`a ng h ◦ (S) l`a mˆo.t luˆ `ong th`ı tˆa.p S c´ac cung hoˇa.c ta.o th`anh mˆo.t d¯u.`o.ng d¯i t` u. s d¯ˆe´n t hoˇa.c l`a mˆo.t ma.ch trong G. V´o.i hai luˆ `ong F v`a H ta k´ `ong m`a luˆ y hiˆe.u F + H l`a luˆ `ong trˆen cung (vi , vj ) l`a fij + hij . - i.nh l´ D y 7.2.11 Nˆe´u F l`a luˆ u. s d¯ˆe´n t c´o gi´a tri. nguyˆen v trong G th`ı F c´o thˆe˙’ phˆan `ong t` t´ıch th`anh F = 1 ◦ (P1 ) + 1 ◦ (P2 ) + · · · + 1 ◦ (Pv ) + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ), trong d¯´o P1 , P2 , Pv l`a c´ac d¯u.`o.ng d¯i so. cˆa´p t` u. s d¯ˆe´n t v`a Φ1 , Φ2 , . . . , Φκ l`a c´ac ma.ch so. cˆa´p cu˙’ a G. (Pi v`a Φi khˆong nhˆa´t thiˆe´t phˆan biˆe.t). Ch´ u.ng minh. T` u. G = (V, E) v´o.i luˆ `ong F cho tru.´o.c ta xˆay du..ng d¯`oˆ thi. unitary Ge = (V e , E e ) . nhu sau: Tˆa.p V c´ac d¯ı˙’nh cu˙’a G ch´ınh l`a tˆa.p V c´ac d¯ı˙’nh cu˙’a G. Nˆe´u fij l`a luˆ e e `ong trˆen cung (vi , vj ) cu˙’a G th`ı ta thay bˇa` ng fij cung song song gi˜ . . . u a c´ac d¯ı˙’nh tu o ng u . e ´ ng vi v`a vje cu˙’a Ge . . . Nˆe´u fij = 0 th`ı khˆong c´o cung n`ao d¯u o. c d¯ˇa.t gi˜ . . . u a vi v`a vj . Ta d¯u o. c Ge l`a d¯a d¯`ˆo thi. trong e e d¯o´ mˆo˜i cung cu˙’a n´o tu.o.ng u´.ng v´o.i mˆo.t d¯o.n vi. luˆ `ong trˆen cung tu.o.ng u ´.ng trong G; n´oi c´ach kh´ac, Ge biˆe˙’u diˆ˜en luˆ`ong F trong G. u. d¯iˆ T` `eu kiˆe.n vˆ `e luˆ `ong F suy ra c´ac d¯ı˙’nh cu˙’a d¯`ˆo thi. Ge cˆ `an thoa˙’ m˜an d+ (vie ) = d− (vie ), v´o.i mo.i vie 6= se hoˇa.c te , d+ (se ) = d− (e ) = v. Suy ra nˆe´u ta tra˙’ la.i v cung d¯u.o..c thˆem v`ao Ge t` u. d¯ı˙’nh te d¯ˆe´n d¯ı˙’nh se th`ı d¯`oˆ thi. Ge s˜e c´o mˆo.t ma.ch Euler (xem Phˆ `an 5.1). Loa.i bo˙’ v cung n`ay kho˙’i ma.ch Euler, ta d¯u.o..c v . . d¯u `o ng d¯i t` . u s d¯ˆe´n t qua mˆo˜i cung cu˙’a Ge d¯u e e ´ng mˆo.t lˆ `an. K´ y hiˆe.u c´ac d¯u.`o.ng d¯i n`ay l`a P10 , P20 , . . . , Pv0 . C´ac d¯u.`o.ng d¯i Pi0 khˆong nhˆa´t thiˆe´t so. cˆa´p (mˇa.c d` u ch´ ung l`a d¯o.n gia˙’n). Tuy nhiˆen, mˆo˜i d¯u.`o.ng d¯i khˆong so. cˆa´p c´o thˆe˙’ xem nhu. tˆo˙’ng cu˙’a mˆo.t d¯u.`o.ng d¯i so. cˆa´p t` u. se d¯ˆe´n . . t v`a mˆo.t sˆo´ c´ac ma.ch so cˆa´p r`o i nhau. Do vˆa.y, e F = 1 ◦ (P1 ) + 1 ◦ (P2 ) + · · · + 1 ◦ (Pv ) + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ), 182 http://www.ebook.edu.vn
trong d¯o´ Pi l`a c´ac d¯u.`o.ng d¯i so. cˆa´p t` u. se d¯ˆe´n te v`a Φi l`a c´ac ma.ch so. cˆa´p. / N´oi chung, c´ac d¯u.`o.ng d¯i v`a c´ac chu tr`ınh c´o thˆe˙’ tr`ung nhau. Nˆe´u chı˙’ c´o v 0 d¯u.`o.ng d¯i v`a κ0 ma.ch d¯`aˆu tiˆen kh´ac nhau, v´o.i d¯u.`o.ng d¯i Pi xuˆa´t hiˆe.n hi lˆ `an trong danh s´ach P1 , P2 , . . . , Pv v`a ma.ch Φi xuˆa t hiˆe.n li lˆan trong danh s´ach Φ1 , Φ2 , . . . , Φκ th`ı F c´o thˆe˙’ viˆe´t du.´o.i da.ng ´ ` v0 κ 0 X X F = hi ◦ (Pi ) + li ◦ (Φi ). i=1 i=1 ´.ng nˆe´n fij .hij = 0 v´o.i mo.i cung (vi , vj ). `ong F v`a H l`a th´ıch u N´oi chung hai luˆ V´ı du. 7.2.12 Luˆ `ong F trong H`ınh 7.3 d¯u.o..c phˆan t´ıch th`anh c´ac d¯u.`o.ng d¯i (t` u. s d¯ˆe´n t) v`a c´ac ma.ch so. cˆa´p: F = 2 ◦ 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 }. 7.3 ac ca˙’ i biˆ C´ ¯o.n gia˙’ n cu˙’ a b` en d ai to´ an luˆ o.n nhˆ `ong l´ a´t ung ta nˆeu mˆo.t sˆo´ kˆe´t qua˙’ nhˆa.n d¯u.o..c t` `an n`ay ch´ Phˆ u. b`ai to´an luˆ `ong l´o.n nhˆa´t. 7.3.1 C´ ac d`o thi. c´ ¯ˆ `eu nguˆ o nhiˆ `on v` `eu d a nhiˆ ¯´ıch X´et d¯`oˆ thi. v´o.i ns d¯ı˙’nh v`ao v`a nt d¯ı˙’nh ra v`a gia˙’ su˙’. luˆ `ong c´o thˆe˙’ chuyˆe˙’n t` u. nguˆ`on d¯ˆe´n d¯´ıch tu` yy ` . ´ ´. B`ai to´an t`ım luˆong l´o n nhˆa t t` u tˆa t ca c´ac nguˆon d¯ˆen tˆa t ca c´ac d¯´ıch c´o thˆe˙’ d¯u.a vˆ . ´ ˙ ’ ` ´ ´ ˙ ’ `e b`ai to´an luˆ . `ong l´o n nhˆa´t bˇ`a ng c´ach thˆem mˆo.t d¯ı˙’nh nguˆ `on nhˆan ta.o s v`a mˆo.t d¯ı˙’nh ra nhˆan . . . ta.o t v´o i c´ac cung d¯u o. c thˆem t` . u s d¯ˆen c´ac d¯ı˙’nh v`ao ban d¯`ˆau v`a t` ´ u. c´ac d¯ı˙’nh ra thu..c tˆe´ d¯ˆe´n d¯ı˙’nh t. Kha˙’ nˇang cu˙’a c´ac cung thˆem v`ao t` . u s d¯ˆe´n c´ac nguˆ `on c´o thˆe˙’ d¯ˇa.t bˇ`a ng vˆo c` ung, hoˇa.c . . . . . trong tru `o ng ho. p lu o. ng h`ang cung cˆa´p ta.i mˆo.t nguˆ `on sk tˆo´i d¯a l`a ak th`ı kha˙’ nˇang cu˙’a cung 183 http://www.ebook.edu.vn
v7 •.............................. . ........ .... ....... ....... ... ....... .. ....... ... ....... ....... .... ....... . ... ............ . ... . . ......... .. ....... ....... ... ....... ....... ... ....... ... ....... ....... ... .... v6 • • v5 ................................................................................................................................................................ ... ... ... ... ... ... ... ... ... ... .......... ... .. ... ... ....... . ... .... ... .... ... ... v2 ... ... ... ... s• ..... . . • . ... ....... . . . . . • • t .......................................................................................................................................................................................................................................................................................................................................................................................... . ..... ..... ..... ..... ..... ..... . .... . . ..... ..... ..... v4 ..... ..... ..... ..... ....... .. ...... . ..... ..... ......... ............ ..... ..... ... . ...... .. ........... ..... ..... .. ..... ..... ..... .. ..... ..... ..... .... ..... ..... .. . ..... ..... .. ..... ..... ..... .. ..... ..... ... ..... ..... ................................................................................................................................................................ • .. • v1 v3 `ong F. H`ınh 7.3: Luˆ (s, sk ) c´o thˆe˙’ d¯ˇa.t bˇ`a ng gi´a tri. n`ay. Tu.o.ng tu.., kha˙’ nˇang cu˙’a c´ac cung dˆa˜n t´o.i d¯ı˙’nh ra t c´o thˆe˙’ d¯ˇa.t bˇ`a ng nhu cˆ`au ta.i c´ac d¯ı˙’nh ra tk hoˇa.c bˇ`a ng vˆo ha.n nˆe´u c´o nhu cˆ `au l`a vˆo ha.n. Nˆe´u b`ai to´an d¯ˇa.t ra o˙’. d¯´o c´o d¯ı˙’nh ra chı˙’ d¯u.o..c cung cˆa´p bo˙’.i nh˜u.ng nguˆ `on n`ao d¯´o v`a . . . ngu o. c la.i, th`ı b`ai to´an khˆong pha˙’i l`a ca˙’i biˆen d¯o n gia˙’n cu˙’a b`ai to´an luˆ `ong l´o.n nhˆa´t t`u. s . d¯ˆe´n t m`a c´o thˆe˙’ d¯u a vˆ`e b`ai to´an d¯a luˆ . `ong nhu d¯a˜ d¯`ˆe cˆa.p trong phˆ . `an mo˙’ d¯`aˆu. 7.3.2 C´ ac d ¯ˆ o.i r` `o thi. v´ ang buˆ o.c ta.i c´ ac cung v` ad¯ı˙’nh Nˆe´u ngo`ai kha˙’ nˇang qij cu˙’a c´ac cung, ta thˆem kha˙’ nˇang cu˙’a c´ac d¯ı˙’nh wj , j = 1, 2, . . . , n, sao cho tˆo˙’ng sˆo´ lu.o..ng h`ang d¯i d¯ˆe´n d¯ı˙’nh vj nho˙’ ho.n wj , t´ u.c l`a X fij ≤ wij vi ∈Γ−1 (vj ) v´o.i mo.i vj . Ta cˆ `ong l´o.n nhˆa´t t` `an t`ım luˆ u. s d¯ˆe´n t v´o.i gia˙’ thiˆe´t thˆem ta.i c´ac d¯ı˙’nh. X´et d¯`oˆ thi. G0 sao cho mo.i d¯ı˙’nh vj cu˙’a d¯`oˆ thi. G tu.o.ng u ´.ng hai d¯ı˙’nh vj+ v`a vj− trong d¯`oˆ thi. G0 sao cho . . mo.i cung (vi , vj ) cu˙’a G d¯ˆe´n d¯ı˙’nh vj tu o ng u ´.ng mˆo.t cung (vi− , vj+ ) d¯ˆe´n d¯ı˙’nh vj+ , v`a mo.i cung (vj , vk ) cu˙’a G xuˆa´t ph´at t` u. vj tu.o.ng u´.ng mˆo.t cung (vj− , vk+ ) cu˙’a G0 xuˆa´t ph´at t` u. vj− . Ngo`ai ra ta thˆem mˆo.t cung gi˜ u.a vj v`a vj v´o.i kha˙’ nˇang thˆong qua wj , t´ + − u.c l`a bˇ`a ng kha˙’ nˇang cu˙’a d¯ı˙’nh vj . V`ı tˆo˙’ng sˆo´ lu.o..ng h`ang d¯ˆe´n d¯ı˙’nh vj+ pha˙’i d¯u.o..c chuyˆe˙’n do.c theo cung (vj+ , vj− ) v´o.i kha˙’ 184 http://www.ebook.edu.vn
nˇang thˆong qua wj nˆen luˆ `ong l´o.n nhˆa´t trong d¯`ˆo thi. G v´o.i r`ang buˆo.c ta.i c´ac d¯ı˙’nh bˇ`a ng luˆ`ong . . l´o n nhˆa´t trong d¯`oˆ thi. G0 v´o i r`ang buˆo.c chı˙’ ta.i c´ac cung. Cˆ `an ch´uy ´ rˇ`a ng nˆe´u thiˆe´t diˆe.n nho˙’ nhˆa´t cu˙’a G0 khˆong ch´ . + − u a c´ac cung da.ng (vj , vj ) th`ı r`ang buˆo.c ta.i d¯ı˙’nh vj tng ng trong G khˆong “t´ıch cu. c” v`a tro˙’. th`anh vˆo du.ng; nˆe´u ngu.o..c la.i, thiˆe´t diˆe.n nho˙’ nhˆa´t cu˙’a G0 ch´ . u.a c´ac . . cung loa.i n`ay th`ı c´ac d¯ı˙’nh tu o ng u . . ´ ng cu˙’a G l`a ba˙’o ho`a bo˙’ i luˆ . `ong l´o n nhˆa´t. 7.3.3 C´ ac d`o thi. c´ ¯ˆ o cˆ a.n trˆ en v` a.n du.´ a cˆ o.i vˆ `e luˆ `ong X´et d¯`ˆo thi. G trong d¯´o c´ac cung (vi , vj ) ngo`ai cˆa.n trˆen qij c`on c´o cˆa.n du.´o.i vˆ `e luˆ `ong l`a rij . . Gia˙’ su˙’ ta muˆo´n biˆe´t c´o tˆ `on ta.i mˆo.t luˆ u a s v`a t sao cho rij ≤ fij ≤ qij v´o.i `ong chˆa´p nhˆa.n gi˜. mo.i cung (vi , vj ). T` u. G, ta thˆem mˆo.t d¯ı˙’nh v`ao nhˆan ta.o sa v`a d¯ı˙’nh ra nhˆan ta.o ta d¯ˆe˙’ nhˆa.n d¯u.o..c Ga . Mˆo˜i cung (vi , vj ) m`a rij 6= 0 ta thˆem mˆo.t cung (sa , vj ) v´o.i kha˙’ nˇang rij v`a cˆa.n du.´o.i bˇa` ng khˆong, v`a c˜ ung thˆem cung th´ u. hai (vi , ta ) v´o.i kha˙’ nˇang rij v`a cˆa.n du.´o.i bˇ`a ng khˆong. Thay qij bo˙’.i qij − rij v`a rij bˇ`a ng 0. Ngo`ai ra thˆem cung (t, s) v´o.i qts = ∞, rts = 0. Bˆay gi`o. ta t`ım luˆ `ong l´o.n nhˆa´t t` u. sa d¯ˆe´n ta trong d¯`oˆ thi. Ga . Nˆe´u gi´a tri. cu˙’a luˆ `ong l´o.n P nhˆa´t bˇa` ng rij 6=0 rij (t´ u.c l`a, nˆe´u tˆa´t ca˙’ c´ac cung d¯i ra t` u. sa v`a tˆa´t ca˙’ c´ac cung d¯i d¯ˆe´n ta ba˙’o ho`a) v`a k´ y hiˆe.u lu.o..ng h`ang trˆen cung (t, s) l`a fts th`ı tˆ `on ta.i luˆ `ong chˆa´p nhˆa.n d¯u.o..c v´o.i gia tri. fts trong d¯`oˆ thi. ban d¯`aˆu. Thˆa.t vˆa.y, nˆe´u ta tr` . . . u rij lu o. ng h`ang trˆen c´ac cung (vi , ta ) v`a (sa , vj ) v`a cˆo.ng thˆem rij v`ao lu o. ng h`ang trˆen cung (vi , vj ) th`ı tˆo˙’ng lu.o..ng h`ang t` . . u. sa d¯ˆe´n ta gia˙’m mˆo.t lu.o..ng l`a rij , luˆ `ong trˆen c´ac cung (vi , ta ) v`a (sa , vj ) gia˙’m xuˆo´ng khˆong, c`on luˆ `ong trˆen cung (vi , vj ) l`a fij ∈ [rij , qij ]. (Gi´a tri. cuˆo´i cu˙’a fij bˇ`a ng rij nˆe´u gi´a tri. ban d¯`aˆu cu˙’a fij tu.o.ng u ´.ng luˆ`ong l´o.n nhˆa´t bˇ`a ng khˆong, v`a gi´a tri. cuˆo´i cu˙’a fij bˇ`a ng qij nˆe´u gi´a tri. ban d¯`ˆau cu˙’a fij bˇ`a ng qij − rij ). Bu.´o.c tr` u. luˆ `ong l´o.n nhˆa´t ngu.o..c v´o.i bu.´o.c d¯iˆ `eu chı˙’nh luˆ `ong trong . . P thuˆa.t to´an t`ım luˆ `ong l´o n nhˆa´t. V`ı ta gia˙’ thiˆe´t gi´a tri. cu˙’a luˆ `ong l´o n nhˆa´t bˇa` ng rij 6=0 rij nˆen cuˆo´i c` ung, tiˆe´n tr`ınh tr` u. luˆ `ong s˜e cho luˆ u. sa d¯ˆe´n ta c´o gi´a tri. bˇ`a ng khˆong (do d¯o´ `ong t` s˜e khiˆe´n hai d¯ı˙’nh nhˆan ta.o v`a c´ac cung liˆen thuˆo.c ch´ ung tro˙’. th`anh vˆo du.ng), v`a luˆ `ong trˆen . tˆa´t ca˙’ c´ac cung v´o i rij 6= 0 s˜e thay d¯oˆ˙’i trong pha.m vi [rij , qij ]. Kˆe´t qua˙’ l`a ta c´o mˆo.t luˆ `ong . . ` “lu u thˆong” trong d¯`oˆ thi. v´o i gi´a tri. bˇa ng fts . Mˇa.t kh´ac ta c´o P - i.nh l´ D y 7.3.1 Nˆe´u gi´a tri. cu˙’ a luˆ`ong l´o.n nhˆa´t t` u. sa d¯ˆe´n ta trong d¯`ˆo thi. Ga kh´ac rij 6=0 rij `ong chˆa´p nhˆa.n d¯u.o..c trong G. `on ta.i luˆ th`ı khˆong tˆ u.ng minh. B`ai tˆa.p. Ch´ / 185 http://www.ebook.edu.vn
7.4 Luˆ o.i chi ph´ı nho˙’ nhˆ `ong v´ a´t Trong Phˆ `an 7.2 ch´ ung ta d¯a˜ x´et b`ai to´an t`ım luˆ`ong l´o.n nhˆa´t t` u. s d¯ˆe´n t m`a khˆong d¯`ˆe cˆa.p . . d¯ˆe´n chi ph´ı d¯u o. c gˇa´n trˆen mˆo˜i cung. Phˆ `an n`ay kha˙’o s´at b`ai to´an t`ım luˆ `ong v´o.i gi´a tri. v cho tru.´o.c t`u. s d¯ˆe´n t sao cho chi ph´ı cu˙’a luˆ`ong l`a nho˙’ nhˆa´t. Cu. thˆe˙’ l`a: B`ai to´ an 7.4.1 Cho ma.ng vˆa.n ta˙’ i G := (V, E) v´o.i d¯ı˙’nh v`ao s, d¯ı˙’nh ra t, kha˙’ nˇang thˆong qua cu˙’ a cung (i, j) ∈ E l`a qij . Gia˙’ su˙’. cij l`a chi ph´ı vˆa.n chuyˆe˙’n mˆo.t d¯o.n vi. h`ang trˆen cung (i, j) ∈ E. T`ım luˆ `ong F := (fij ) c´o gi´a tri. v trˆen G v´o.i chi ph´ı nho˙’ nhˆa´t; t´ u.c l`a gia˙’ i b`ai to´an X fij cij → min (vi ,vj )∈E o.i d¯iˆ v´ `eu kiˆe.n ( P (vi ,vj )∈E fij = v, 0≤ fij ≤ qij . Hiˆe˙’n nhiˆen, b`ai to´an khˆong c´o l`o.i gia˙’i nˆe´u v l´o.n ho.n gi´a tri. l´o.n nhˆa´t cu˙’a luˆ `ong t`u. s . d¯ˆe´n t. Tuy nhiˆen, nˆe´u v nho˙’ ho n hoˇa.c bˇ`a ng gi´a tri. n`ay th`ı s˜e c´o mˆo.t sˆo´ luˆ `ong c´o gi´a tri. v . . v`a b`ai to´an c´o l`o i gia˙’i. Ford v`a Fulkerson [27] d¯a˜ xˆay du. ng mˆo.t thuˆa.t to´an “khˆong c´o th´ u. tu..” d¯ˆe˙’ t`ım luˆ `ong v´o.i chi ph´ı nho˙’ nhˆa´t. C´ac thuˆa.t to´an tr`ınh b`ay du.´o.i d¯aˆy du..a theo nh˜ u.ng kˆe´t qua˙’ cu˙’a Klein [38], Busacker v`a Gowen [10]. C´ac thuˆa.t to´an n`ay d¯o n gia˙’n ho n phu o.ng . . . ph´ap cu˙’a Ford-Fulkerson v`a su˙’. du.ng nh˜ u.ng k˜y thuˆa.t d¯˜a gi´o.i thiˆe.u trˆen. 7.4.1 Thuˆ a.t to´ an Klein, Busacker, Gowen Thuˆa.t to´an n`ay du..a v`ao viˆe.c x´ac d¯.inh ma.ch c´o d¯oˆ. d`ai ˆam. Ch´ ung ta h˜ay gia˙’ thiˆe´t rˇ`a ng tˆ `on ` ´ . . . . . ` ˙ ’ ta.i luˆong chˆa p nhˆa.n d¯u o. c F v´o i gi´a tri. v v`a F d¯a˜ d¯u o. c x´ac d¯i.nh. Luˆong n`ay c´o thˆe nhˆa.n d¯u.o..c bˇ`a ng c´ach ´ap du.ng thuˆa.t to´an t`ım luˆ`ong l´o.n nhˆa´t v`a ch´ `ong cho d¯ˆe´n khi ung ta tˇang luˆ . . nhˆa.n d¯u o. c luˆ `ong c´o gi´a tri. v. V´o.i luˆ `ong chˆa´p nhˆa.n n`ay, ta d¯.inh ngh˜ıa d¯`ˆo thi. Gµ (F ) := (V µ , E µ ) nhu. d¯˜a gia˙’i th´ıch trong Phˆ`an 7.2 v`a c´o chi ph´ı trˆen c´ac cung nhu. sau: • v´o.i mˆo˜i cung (viµ , vjµ ) ∈ E1µ , d¯aˇ. t cµij := cij . • v´o.i mˆo˜i cung (vjµ , viµ ) ∈ E2µ , d¯aˇ. t cµji := −cij . Thuˆa.t to´an du..a trˆen d¯i.nh l´ y sau: 186 http://www.ebook.edu.vn
- i.nh l´ D `ong gi´a tri. v v´o.i chi ph´ı nho˙’ nhˆa´t nˆe´u v`a chı˙’ nˆe´u khˆong tˆ y 7.4.2 F l`a luˆ `on ta.i ma.ch Φ trong G (F ) sao cho tˆo˙’ng cu˙’ a c´ac chi ph´ı cu˙’ a c´ac cung thuˆo.c Φ ˆam. µ Ch´u.ng minh. D - ˇa.t c[F ] l`a chi ph´ı cu˙’a luˆ `ong F trong d¯`oˆ thi. G v`a c[Φ|Gµ (F )] l`a tˆo˙’ng cu˙’a c´ac chi ph´ı cu˙’a c´ac cung thuˆo.c ma.ch Φ tu.o.ng u ´.ng v´o.i d¯`oˆ thi. Gµ (F ). - iˆ D `eu kiˆe.n cˆ`an. Gia˙’ su˙’. c[Φ|Gµ (F )] < 0 v´o.i ma.ch Φ n`ao d¯o´ trong Gµ (F ). Thˆem mˆo.t d¯o.n vi. v`ao luˆ `ong trˆen mˆo˜i cung thuˆo.c ma.ch Φ s˜e ta.o ra mˆo.t luˆ `ong m´o.i chˆa´p nhˆa.n d¯u.o..c F + 1 ◦ (Φ) c´o gi´a tri. v. Chi ph´ı cu˙’a luˆ `ong F + 1 ◦ (Φ) bˇ`a ng c[F ] + c[Φ|Gµ (F )] < c[F ]-mˆau . thuˆa˜n v´o i gia˙’ thiˆe´t F l`a luˆ . `ong v´o i gi´a tri. v v`a c´o chi ph´ı nho˙’ nhˆa´t. `eu kiˆe.n d¯u˙’. Gia˙’ su˙’. c[Φ|Gµ (F )] ≥ 0 v´o.i mo.i ma.ch Φ trong Gµ (F ) v`a F ∗ (6= F ) l`a - iˆ D `ong gi´a tri. v c´o chi ph´ı nho˙’ nhˆa´t. luˆ `ong m`a gi´a tri. trˆen cung (vi , vj ) bˇa` ng fij∗ − fij . y hiˆe.u F ∗ − F l`a luˆ Ta k´ V`ı F ∗ v`a F c´o thˆe˙’ phˆan t´ıch th`anh tˆo˙’ng cu˙’a c´ac luˆ `ong do.c theo (t`u. s d¯ˆe´n t) c´ac d¯u.`o.ng d¯i trong G, theo c´ach xˆay du..ng cu˙’a d¯`ˆo thi. unitary G trong Phˆ e `an 7.2.3 d¯oˆ´i v´o.i luˆ `ong F ∗ − F, suy ra v´o.i mo.i d¯ı˙’nh vi ∈ V ta c´o d+ − G∗ (vi ) = dG∗ (vi ). `an 7.2.3, dˆ˜e d`ang kiˆe˙’m tra rˇ`a ng Do d¯o´ theo Phˆ F ∗ − F = 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ). Ho.n n˜u.a, luˆ `ong F ∗ = F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φκ ) l`a chˆa´p nhˆa.n d¯u.o..c nˆen tˆo˙’ng F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) + · · · + 1 ◦ (Φl ) chˆa´p nhˆa.n d¯u.o..c v´o.i mo.i 1 ≤ l ≤ κ. Do d¯´o v´o.i luˆ `ong F ta c´o c[F + 1 ◦ (Φ1 )] = c[F ] + c[Φ1 |Gµ (F )] ≥ c[F ]. Mˇa.t kh´ac c[Φl |Gµ (F + 1 ◦ (Φ1 ))] ≥ c[Φl |Gµ (F )] v´o.i mo.i l = 1, 2, . . . , k. `ong F + 1 ◦ (Φ1 ) + 1 ◦ (Φ2 ) l`a Vˆa.y chi ph´ı cu˙’a luˆ 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 http://www.ebook.edu.vn
≥ c[F ]. Tiˆe´p tu.c qu´a tr`ınh trˆen ta d¯u.o..c c[F ∗ ] ≥ c[F ]. D `eu n`ay mˆau thuˆa˜n v´o.i gia˙’ thiˆe´t F ∗ l`a luˆ - iˆ `ong c´o chi ph´ı nho˙’ nhˆa´t. / Do d¯o´ theo D - i.nh l´ y 7.4.2, d¯ˆe˙’ t`ım luˆ`ong chˆa´p nhˆa.n d¯u.o..c c´o gi´a tri. v v´o.i chi ph´ı nho˙’ nhˆa´t ta bˇa´t d¯`aˆu t` u. luˆ `ong chˆa´p nhˆa.n d¯u.o..c c´o gi´a tri. v, thiˆe´t lˆa.p d¯`oˆ thi. Gµ (F ) v`a kiˆe˙’m tra c´o tˆ`on ta.i ma.ch c´o d¯ˆo. d`ai ˆam khˆong. Nˆe´u khˆong c´o th`ı luˆ `ong nhˆa.n d¯u.o..c c´o chi ph´ı nho˙’ nhˆa´t. Ngu.o..c la.i nˆe´u Φ l`a ma.ch c´o d¯oˆ. d`ai ˆam th`ı ta thˆem δ v`ao luˆ `ong trˆen ma.ch n`ay. Khi ` . ˜ ˙ ’ . . d¯o´ luˆong m´o i vˆan c´o gi´a tri. v v`a c´o chi ph´ı giam mˆo.t lu o. ng δ.c(Φ), trong d¯o´ c(Φ) l`a chi ph´ı cu˙’a ma.ch c´o dˆ `o d`ai ˆam Φ. Hiˆe˙’n nhiˆen δ cˆ `an d¯u.o..c cho.n sao cho c´ac kha˙’ nˇang thˆong qua cu˙’a c´ac cung trong Gµ (F ) khˆong bi. vi pha.m; t´ u.c l`a δ = min µ µ qijµ . (vi ,vj ) Theo c´ach cho.n ban d¯`aˆu cu˙’a c´ac kha˙’ nˇang cu˙’a d¯`oˆ thi. Gµ (F ) luˆ `ong m´o.i nhˆa.n d¯u.o..c t` u. luˆ `ong c˜u (bˇa` ng c´ach cˆo.ng δ v`ao luˆ . . `ong trˆen ma.ch d¯oˆ. d`ai ˆam) l`a chˆa´p nhˆa.n d¯u o. c. Qu´a tr`ınh la.i d¯u o. c lˇa.p la.i v´o i luˆong m´o i v`a vˆan vˆan. Chi tiˆe´t cu˙’a thuˆa.t to´an nhu. sau. . . . ` . Thuˆ a.t to´ `ong c´ an t`ım luˆ a´t o chi ph´ı nho˙’ nhˆ 1. Su˙’. du.ng thuˆa.t to´an luˆ `ong l´o.n nhˆa´t, t`ım luˆ `ong chˆa´p nhˆa.n d¯u.o..c F v´o.i gi´a tri. v. - ˇa.t 2. D E1µ := {(viµ , vjµ ) | fij < qij , (vi , vj ) ∈ E}, E2µ := {(vjµ , viµ ) | fij > 0, (vi , vj ) ∈ E}. Xˆay du..ng d¯`oˆ thi. c´o tro.ng sˆo´ Gµ (F ) := (V µ , E µ ), trong d¯o´ V µ := V, E µ := E1µ ∪ E2µ , • V´o.i mˆo˜i cung (viµ , vjµ ) ∈ E1µ , d¯aˇ. t cµij := cij . • V´o.i mˆo˜i cung (vjµ , viµ ) ∈ E2µ , d¯aˇ. t cµji := −cij . 3. Nˆe´u tˆ d¯ˆo. d`ai ˆam Φ trˆen d¯`ˆo thi. Gµ (F ) c´o tro.ng sˆo´ W := (wij ), chuyˆe˙’n `on ta.i ma.ch c´o sang Bu.´o.c 5. Ngu.o..c `ong v´o.i chi ph´ı nho˙’ nhˆa´t; thuˆa.t to´an d` la.i, F l`a luˆ u.ng. u.c sau: 4. T´ınh δ theo cˆong th´ δ := min{qijµ | (viµ , vjµ ) ∈ Φ}. • V´o.i mo.i cung (viµ , vjµ ) ∈ Φ sao cho cµij < 0 thay d¯ˆo˙’i luˆ `ong fji trˆen cung (vj , vi ) ∈ E . bo˙’ i fji − δ. 188 http://www.ebook.edu.vn
• V´o.i mo.i cung (viµ , vjµ ) ∈ Φ sao cho cµij > 0 thay d¯ˆo˙’i luˆ `ong fij trˆen cung (vi , vj ) ∈ E . bo˙’ i fij + δ. 5. V´o.i luˆ `ong m´o.i F, chuyˆe˙’n sang Bu.´o.c 2. 7.5 Cˇ a.p gh´ ep 7.5.1 C´ ac b` ai to´ `e cˇ an vˆ a.p gh´ ep `e cˇa.p gh´ep trong c´ac d¯`oˆ thi. (n´oi chung khˆong pha˙’i d¯`oˆ thi. hai phˆ C´ac b`ai to´an vˆ `an) d¯u.o..c quan tˆam v`ı hai l´ y do. Th´ u. nhˆa´t, c´o thˆe˙’ dˆa˜n d¯ˆe´n c´ac b`ai to´an n`ay t` u. viˆe.c tˆo˙’ng qu´at ho´a b`ai to´an phˆan cˆong, v`a ch´ ung l`a mˆo.t phˆ `an trong nh˜ . u ng b`ai to´an kh´ac cu˙’a d¯`ˆo thi.: c´ac b`ai to´an t`ım h`anh tr`ınh tˆo´i u u (nhu b`ai to´an ngu `o i d¯u a thu. Trung Hoa), x´ac d¯i.nh dˆay chuyˆ . . . . . `en ´ ´ ` . . ngˇan nhˆa t trong d¯ˆo thi. vˆo hu ´o ng, v.v. Mˆo´i quan tˆam th´ u. hai vˆ y thuyˆe´t, do mˆo´i liˆen hˆe. v´o.i l´o.p c´ac b`ai to´an quy `e kh´ıa ca.nh l´ hoa.ch nguyˆen m`a c´o thˆe˙’ gia˙’i bˇ`a ng thuˆa.t to´an v´o.i d¯oˆ. ph´ u.c ta.p d¯a th´ u.c theo m v`a n (sˆo´ c´ac ca.nh v`a c´ac d¯ı˙’nh cu˙’a d¯`oˆ thi.). X´et b`ai to´an sau xˆay du..ng d¯`oˆ thi. con bˆo. phˆa.n Gp cu˙’a d¯`ˆo thi. vˆo hu.´o.ng G trong d¯o´ bˆa.c cu˙’a c´ac d¯ı˙’nh cu˙’a d¯`oˆ thi. Gp thoa˙’ m˜an t´ınh chˆa´t cho tru.´o.c. B` ai to´ an 7.5.1 (B`ai to´an d¯`oˆ thi. bˆo. phˆa.n c´o r`ang buˆo.c vˆ `e d¯ı˙’nh) Gia˙’ su˙’. G = (V, E) l`a d¯`ˆo thi. vˆ . . . . . o hu ´o ng v´o i chi ph´ı cj tu o ng u ´ ng v´o i mˆo˜i ca.nh ej ∈ E. Ngo`ai ra, cho tru.´o.c c´ac sˆo´ . . nguyˆen du.o.ng δi , i = 1, 2, . . . , n. Vˆa´n d¯`ˆe d¯ˇa.t ra l`a t`ım mˆo.t d¯`ˆo thi. bˆo. phˆa.n G∗p cu˙’ a G sao cho bˆa.c cu˙’ a c´ac d¯ı˙’nh vi tu.o.ng u ´.ng d¯`ˆo thi. G∗p bˇ`a ng δi , v`a tˆo˙’ng cu˙’ a c´ac ca.nh trong G∗p l´o.n nhˆa´t (hoˇa.c nho˙’ nhˆa´t). Hiˆe˙’n nhiˆen, v´o.i d¯`oˆ thi. G v`a c´ac sˆo´ δi cho tru.´o.c, c´o thˆe˙’ khˆong tˆ `on ta.i d¯`ˆo thi. bˆo. phˆa.n ˙ ’ ` ˙ ’ ` ` . Gp thoa m˜an c´ac r`ang buˆo.c vˆe d¯ınh. Hai d¯iˆeu kiˆe.n cˆan (nhu ng khˆong d¯u˙’-ta.i sao?) d¯ˆe˙’ tˆ `on . . ta.i d¯`ˆo thi. bˆo. phˆa.n chˆa´p nhˆa.n d¯u o. c l`a δi ≤ dG (vi ), v´o.i mo.i d¯ı˙’nh vi ∈ V v`a n X δi chˇa˜n. i=1 `eu kiˆe.n sau suy tru..c tiˆe´p t` - iˆ D u. t´ınh chˆa´t: tˆo˙’ng c´ac bˆa.c cu˙’a c´ac d¯ı˙’nh bˇ`a ng hai lˆ `an sˆo´ c´ac ca.nh. 189 http://www.ebook.edu.vn
Tˆa.p con M ⊂ E go.i l`a mˆo.t cˇa.p gh´ep nˆe´u hai ca.nh bˆa´t k` `e nhau. y trong M khˆong kˆ . Chi ph´ı cu˙’a cˇa.p gh´ep M d¯.inh ngh˜ıa bo˙’ i X c(M ) = cj . ej ∈M Ta c´o b`ai to´an sau: B`ai to´an 7.5.2 (B`ai to´an d¯oˆ´i s´anh v´o.i chi ph´ı l´o.n nhˆa´t) T`ım cˇa.p gh´ep M ∗ c´o chi ph´ı l´o.n nhˆa´t. B`ai to´an d¯ˆo´i s´anh v´o.i chi ph´ı l´o.n nhˆa´t c´o thˆe˙’ ph´at biˆe˙’u da.ng b`ai to´an quy hoa.ch nguyˆen: m X z= cj xj → max j=1 sao cho ( P m j=1 bij xj ≤ 1, i = 1, 2, . . . , n, xj ∈ {0, 1}, trong d¯o´ bij l`a ma trˆa.n liˆen thuˆo.c cu˙’a G v`a xj = 1 (hoˇa.c 0) phu. thuˆo.c v`ao ej c´o d¯u.o..c gh´ep cˇa.p hay khˆong. Hiˆe˙’n nhiˆen rˇ`a ng, b`ai to´an d¯ˆo´i s´anh v´o.i chi ph´ı l´o.n nhˆa´t d¯oˆ´i v´o.i d¯`oˆ thi. G ˆ n`ao d¯o´ l`a . . . tru `o ng ho. p d¯aˇ. c biˆe.t cu˙’a b`ai to´an c´o r`ang buˆo.c vˆ `e bˆa.c cu˙’a c´ac d¯ı˙’nh. Nˆe´u sˆo´ c´ac d¯ı˙’nh cu˙’a ˆ ˜ . ` G chˇan, ta thˆem c´ac ca.nh v´o i chi ph´ı bˇa ng −∞ v`ao G ˆ d¯ˆe˙’ thu d¯u.o..c mˆo.t d¯`oˆ thi. d¯`ˆay d¯u˙’ G. . Khi d¯´o b`ai to´an d¯u a vˆ `e B`ai to´an 7.5.1 trˆen d¯`oˆ thi. G trong d¯o´ tˆa´t ca˙’ c´ac δi = 1. Nghiˆe.m cu˙’a b`ai to´an ban d¯`aˆu dˆ˜e d`ang suy ra t` u. b`ai to´an sau bˇ`a ng c´ach bo˙’ qua tˆa´t ca˙’ c´ac ca.nh c´o chi ph´ı bˇ`a ng −∞. Nˆe´u sˆo´ c´ac d¯ı˙’nh cu˙’a G ˆ le˙’ th`ı ta thˆem mˆo.t d¯ı˙’nh cˆo lˆa.p v`ao G ˆ tru.´o.c khi xˆay . du. ng d¯`oˆ thi. G v`a ´ap du.ng l´ y luˆa.n trˆen. Tu.o.ng u ´.ng v´o.i b`ai to´an t`ım cˇa.p gh´ep c´o chi ph´ı l´o.n nhˆa´t l`a b`ai to´an phu˙’ c´o chi ph´ı . P nho˙’ nhˆa´t, t´u c l`a: T`ım phu˙’ E ∗ cu˙’a G sao cho tˆo˙’ng chi ph´ı ej ∈E ∗ cj nho˙’ nhˆa´t. B`ai to´an n`ay c´o thˆe˙’ ph´at biˆe˙’u da.ng quy hoa.ch nguyˆen nhu. sau: m X z= cj xj → min j=1 sao cho ( P m j=1 bij xj ≥ 1, i = 1, 2, . . . , n, xj ∈ {0, 1}, trong d¯o´ xj = 1 (hoˇa.c 0) phu. thuˆo.c v`ao ej c´o thuˆo.c phu˙’ E ∗ hay khˆong. 190 http://www.ebook.edu.vn
v3 v5 • ...................................................................................................................................................... ....... ........ ..... .. .............. ... • . .. ...... . ....... ....... . ..... . ..... ... ........ ... .. ...... ....... ........ ... .. .... . . . ... .. ... .... . . . ....... ... .. ........... . .. .... . .... ... ... ....... . .... ... . . . ........... ..... .. . .... ....... ... .. ..... . . .. ... ... ... . . ....... ..... . . ........... ... .. . . ........... .... v1 • . . . ... •. . ........................................................................................................................................................................................................................... .. .. . .. .... ... • v6 ..... .. ..... .. ... ... ... v2 . .... .... ..... ... .... .. . ..... . . .. .... . ..... ... .... .. .... ..... .... ... .. . . ..... ... .. ... . ................................................................................................................................................... • • v4 v7 v3 v5 ...• ..........................................................................................................................................................• .... ... ........ .. .. ... . .... .... ....... .. ... ....... ....... .... ..... .. . ....... ....... .. . ........ ... ..... .... ........ . . ... ....... . ....... ..... ... ....... ....... .... ... . . ......... .... .... ........ ... .. ... . . ... ... ....... . .. .... ....... ..... . ... ....... .. .... ... v1 • • ......... ....... ....... ....... ....... ............................................................................................................................................................. .. ... . ... • v6 ..... .. ..... .. . . .... . . . v2 . . .... ..... . . .. .... ... ..... ... . .. .. . ..... .. . .... .. .. . ..... .. .... ... . . . ..... .. .. .. .. • . .................................................................................................................................................. . • v4 v7 H`ınh 7.4: (a) Cˇa.p gh´ep. (b) Phu˙’. H`ınh 7.4(a) minh ho.a d¯`oˆ thi. v´o.i cˇa.p gh´ep d¯u.o..c v˜e bˇ`a ng d¯oa.n n´et d¯u ´.t v`a H`ınh 7.4(b) minh ho.a phu˙’ d¯u.o..c v˜e bˇa` ng d¯oa.n n´et d¯u ´.t trong c` ung d¯`oˆ thi.. Trong tru.`o.ng ho..p tˆa´t ca˙’ c´ac ca.nh c´o chi ph´ı bˇ`a ng nhau (chˇa˙’ng ha.n 1) th`ı b`ai to´an d¯oˆ´i s´anh v´o.i chi ph´ı l´o.n nhˆa´t v`a b`ai to´an t`ım phu˙’ v´o.i chi ph´ı nho˙’ nhˆa´t d¯u.a vˆ `e b`ai to´an t`ım . cˇa.p gh´ep l´o n nhˆa´t t´ . u c l`a t`ım cˇa.p gh´ep c´o sˆo´ ca.nh nhiˆ`eu nhˆa´t v`a b`ai to´an t`ım phu˙’ nho˙’ nhˆa´t tu.o.ng u ´.ng. Nˆe´u d¯`ˆo thi. G c´o n d¯ı˙’nh, khi d¯o´ sˆo´ phˆ`an tu˙’. cu˙’a cˇa.p gh´ep l´o.n nhˆa´t khˆong vu.o..t qu´a [n/2]. Tuy nhiˆen, sˆo´ n`ay khˆong pha˙’i l´ uc n`ao c˜ ung d¯a.t d¯u.o..c; chˇa˙’ng ha.n, d¯`ˆo thi. “h`ınh sao” trong H`ınh 7.5 c´o cˇa.p gh´ep l´o.n nhˆa´t v´o.i sˆo´ phˆ `an tu˙’. 1. Tru.`o.ng ho..p d¯aˇ. c biˆe.t khi c´ac chi ph´ı cj tu` yy´ nhu.ng d¯`ˆo thi. l`a hai phˆ `an, th`ı b`ai to´an . t`ım cˇa.p gh´ep c´o chi ph´ı nho˙’ nhˆa´t d¯u a vˆ `e b`ai to´an phˆan cˆong cˆong viˆe.c, mˆo.t b`ai to´an quen ˙ ’ thuˆo.c cua Vˆa.n tr` . ´ u ho.c. V´o i cˆa u tr´ uc d¯oˆ thi. d¯ˇa.c biˆe.t n`ay, B`ai to´an 7.5.1 tro˙’. th`anh b`ai to´an ` vˆa.n ta˙’i. Mu.c d¯´ıch ch´ınh cu˙’a phˆ `an n`ay l`a tr`ınh b`ay b`ai to´an vˆ`e cˇa.p gh´ep l´o.n nhˆa´t cu˙’a d¯`oˆ thi. hai phˆ . `an trong mˆo´i liˆen hˆe. v´o i b`ai to´an luˆ . `ong l´o n nhˆa´t. Vˆ `e c´ac thuˆa.t to´an gia˙’i quyˆe´t c´ac . . . ˙ ’ ˙ ’ b`ai to´an cˇa.p gh´ep trong tru `o ng ho. p tˆo ng qu´at c´o thˆe xem t`ai liˆe.u dˆa˜n [14], [30]. 191 http://www.ebook.edu.vn
•............... .. • .... ..... • .... .... ..... ... ..... ..... ..... . . ......... ..... .... ..... ..... ..... ..... ... ..... ..... ... ..... ..... ..... ... .. ...... ..... ... ..... ..... ..... ..... ... ..... ..... . ..... ..... .... . ....... ..... .. ..... ..... .. ..... • • .. . .. .............................................................................................................................................................. ..... .. ..... .... .... ......... . • .. .. ..... .... ..... .... ..... ..... ... ..... ..... ... ..... . ........ . . ..... ..... ... .... . . . ..... .... . ..... ... . . ..... .. .... . . . . ..... . . .... . . . . ..... ..... ... . ... . . . ..... ... . ... . . . ..... ..... .... . . . ..... • . .... . • . .. • .. - `ˆo thi. h`ınh sao. H`ınh 7.5: D 7.5.2 Cˇ a.p gh´ o.n nhˆ ep l´ a´t trong d`o thi. hai phˆ ¯ˆ `an Tru.´o.c hˆe´t ta bˇa´t d¯`ˆau bˇ`a ng mˆo.t v´ı du.. V´ı du. 7.5.3 (Phˆan cˆong cˆong viˆe.c, cˇa.p gh´ep trong d¯`ˆo thi. hai phˆ `an) Mˆo.t nh`a m´ay c´o p m´ay v`a q cˆong viˆe.c cˆ . . `an thu. c hiˆe.n. Gia˙’ su˙’ G = (V, E) l`a d¯`ˆo thi. hai phˆ `an m`a c´ac d¯ı˙’nh l`a V = V1 ∪ V2 , v´o.i V1 = {1, 2, . . . , p} v`a V2 = {1, 2, . . . , q} v`a c´o mˆo.t ca.nh liˆen thuˆo.c (i, j) nˆe´u m´ay i c´o thˆe˙’ thu..c hiˆe.n cˆong viˆe.c j. Vˆa´n d¯`ˆe d¯ˇa.t ra l`a sˇa´p xˆe´p mˆo˜i m´ay v´o.i mˆo.t cˆong viˆe.c m`a n´o c´o thˆe˙’ thu..c hiˆe.n. D- iˆ `eu d¯o´ c´o ngh˜ıa rˇa` ng, t`ım trong G mˆo.t cˇa.p gh´ep c´o sˆo´ phˆ `an tu˙’. bˇa` ng p. B`ai to´an cˇa.p gh´ep c´o thˆe˙’ d¯u.a vˆ `e b`ai to´an ma.ng vˆa.n ta˙’i nhu. sau. Ta thˆem d¯ı˙’nh nguˆ `on v`a d¯ı˙’nh ra nhˆan ta.o s, t sau d¯o´ nˆo´i t` . u s d¯ˆe´n c´ac d¯ı˙’nh thuˆo.c tˆa.p V1 v`a t`. u c´ac d¯ı˙’nh thuˆo.c tˆa.p ˜ . V2 d¯ˆe´n t. G´an mˆoi cung trong d¯`oˆ thi. thu d¯u o. c, k´. y hiˆe.u G , c´o kha˙’ nˇang thˆong qua bˇa` ng 1. M M Ta c´o G l`a mˆo.t ma.ng vˆa.n ta˙’i. y 7.5.4 Gia˙’ su˙’. G l`a d¯`ˆo thi. hai phˆ - i.nh l´ D `an d¯.inh hu.´o.ng v´o.i c´ac tˆa.p d¯ı˙’nh r`o.i nhau V1 v`a V2 m` a trong d¯´o c´ac ca.nh d¯u.o..c d¯.inh hu.´o.ng t` u. c´ac d¯ı˙’nh trong tˆa.p V1 d¯ˆe´n c´ac d¯ı˙’nh trong tˆa.p V2 . 1. Luˆ`ong F trong ma.ng vˆa.n ta˙’ i GM cho ta mˆo.t cˇa.p gh´ep trong G. D - ı˙’nh vi ∈ V1 d¯u.o..c d¯ˆo´i s´anh v´o.i d¯ı˙’nh vj trong V2 nˆe´u v`a chı˙’ nˆe´u luˆ `ong F trˆen cung (vi , vj ) bˇa` ng 1. `ong l´o.n nhˆa´t tu.o.ng u 2. Luˆ ´.ng v´o.i cˇa.p gh´ep l´o.n nhˆa´t. `a ng #V1 tu.o.ng u `ong c´o gi´a tri. bˇ 3. Luˆ ´.ng v´o.i cˇa.p gh´ep ho`an ha˙’ o. Ch´ u.ng minh. Gia˙’ su˙’. fij = 1. C´o d¯u´ng mˆo.t cung d¯ˆe´n d¯ı˙’nh vi l`a (s, vi ). Do d¯o´ fsi = 1. Suy ra `ong d¯ˆe´n d¯ı˙’nh vi bˇ`a ng 1. Do luˆ luˆ `ong ra kho˙’i d¯ı˙’nh vi bˇ`a ng 1 nˆen c´o d¯u ´ng mˆo.t cung c´o da.ng 192 http://www.ebook.edu.vn