Đang chuẩn bị liên kết để tải về tài liệu:
Đồ 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. . | Đồ 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.oc 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.oc gˇa´n v´o.i mˆo.t kha˙’ nˇang thˆong qua qij l`a sˆo´ lu.ong 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.oc 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.oc 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.oc 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 . . . ´ .