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

Đồ 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.
Nội dung trích xuất từ tài liệu:
Đồ thị và các thuật toán – Chương 7: Mạng vận tảiChu.o.ng 7 a.n ta˙’iMa.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.nnhˆ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. Trongkhung 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`asˆ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´oc´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.ahai 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˙’icu˙’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.omˆ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 Fordv`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˙’iquyˆ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ˆ ...