Mạng vận tải và các thuật toán đồ thị

http://www.ebook.edu.vn

Chu

.o

.ng 7

Ma

.ng vˆa

.n ta

˙’i

7.1 Mo

.

˙’ d¯ˆa

`u

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ˆo

`ng d¯u

.o.

.c truyˆe

`n t`u

.mˆo

.td¯ı

˙’nh nguˆo

`nscu

˙’a d¯ˆo

`thi

.d¯ˆe

´n mˆo

.td¯ı

˙’nh d¯´ıch t. Trong

khung ca

˙’nh d¯´o, mˆo

˜i cung (vi, vj) cu

˙’a d¯ˆo

`thi

.Gd¯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ˆo

`ng 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ˆe

`u ´u

.ng du

.ng trong thu

.

.c tˆe

´, chˇa

˙’ng ha

.n, x´ac d¯i

.nh 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ˆe

˜n 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ˆo

`ng 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ˆo

`ng 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ˆo

`ng l´o

.n nhˆa

´tt`u

.sd¯ˆe

´ntd¯u

.a ra lˆa

`n d¯ˆa

`u 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˜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ˆo

`ng l´o

.n nhˆa

´t:

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ˆo

`ng trˆen cung (vi, vj) m`a c`on “kha

˙’ nˇang” rij cho cˆa

.n du

.´o

.i cu

˙’a luˆo

`ng trˆen cung

n`ay. Trong tru

.`o

.ng ho.

.p nhu

.vˆa

.y, khˆong pha

˙’i 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ˆo

`ng c˜ung thoa

˙’ m˜an c`ung l´uc hai r`ang buˆo

.c n`ay. Tuy nhiˆen-n´oi chung-nhiˆe

`u

luˆo

`ng thoa

˙’ d¯iˆe

`u kiˆe

.n n`ay, v`a nˆe

´u 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ˆo

`ng do

.c theo c´ac cung, th`ı b`ai to´an tro

.

˙’ th`anh t`ım luˆo

`ng chˆa

´p nhˆa

.n d¯u

.o.

.c

v´o

.i chi ph´ı nho

˙’ nhˆa

´tt`u

.sd¯ˆe

´nt.

2. X´et tru

.`o

.ng ho.

.p d¯`oi ho

˙’iluˆo

`ng 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ˆa

`n lˇa

.p c´ac b`ai to´an luˆo

`ng l´o

.n nhˆa

´t t`u

.sd¯ˆe

´ntnhu

.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˜ung cˆa

`n

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ˆo

`ng l´o

.n nhˆa

´t gi˜u

.a hai

d¯ı

˙’nh sv`a t.

3. Nˆe

´u thay cho mˆo

.t d¯ı

˙’nh nguˆo

`n v`a mˆo

.t d¯ı

˙’nh d¯´ıch, ta kha

˙’o s´at mˆo

.t sˆo

´nguˆo

`n 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ˆo

`n-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ˆo

`ng t`u

.c´ac nguˆo

`n d¯ˆe

´n c´ac d¯´ıch l`a b`ai to´an luˆo

`ng 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ˆo

`ng

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ˆo

`ng d¯ˆe

´n bˇa

`ng sˆo

´lu

.o.

.ng

luˆo

`ng ra. Nˆe

´u ta bo

˙’ gia

˙’ thiˆe

´t n`ay v`a x´et tru

.`o

.ng ho.

.p luˆo

`ng ra kho

˙’i mˆo

.t cung bˇa

`ng

luˆo

`ng 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ˆo

`ng l´o

.n nhˆa

´t (t`u

.

sd¯ˆe

´nt) 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ˆo

`ng 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ˆo

`ng v`ao s

v`a luˆo

`ng ra kho

˙’itc´o thˆe

˙’ thay d¯ˆo

˙’i ho`an to`an d¯ˆo

.c lˆa

.p.

C´ac b`ai to´an vˆe

`luˆo

`ng d¯u

.o.

.c nghiˆen c´u

.u nhiˆe

`u v`a c´o nh˜u

.ng ´u

.ng du

.ng thu

.

.c tiˆe

˜n. 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ˆo

`ng l´o

.n nhˆa

´t t`u

.sd¯ˆe

´ntv`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ˆo

`ng 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¯ˆe

`u 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¯ˆay. 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

`ng l´o

.n nhˆa

´t

Luˆo

`ng l´o

.n nhˆa

´ttrˆen ma

.ng vˆa

.n ta

˙’iGl`a mˆo

.t luˆo

`ng v´o

.i gi´a tri

.l´o

.n nhˆa

´t. N´oi chung c´o mˆo

.t

v`ai luˆo

`ng v´o

.i c`ung gi´a tri

.l´o

.n nhˆa

´t. Phˆa

`n n`ay tr`ınh b`ay thuˆa

.t to´an t`ım luˆo

`ng 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ˆo

`ng n`ao d¯´o v`a tˇang gi´a tri

.cu

˙’a luˆo

`ng 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ˆo

`ng 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ˆe

˜n so.d¯ˆo

`ma

.ng dˆa

˜n dˆa

`u. Dˆa

`u d¯u

.o.

.c

dˆa

˜n t`u

.t`au sv`a d¯u

.o.

.c bo.m thˆong qua ma

.ng d¯ˆe

´n nh`a m´ay lo

.c dˆa

`ut. C´ac d¯ı

˙’nh b, c, d v`a el`a

c´ac tra

.m bo.m trung gian. C´ac cung biˆe

˙’u thi

.c´ac ˆo

´ng dˆa

˜n dˆa

`u 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ˆe

`u nhˆa

´t lu

.o.

.ng dˆa

`u t`u

.t`au d¯ˆe

´n nh`a m´ay v`a t´ınh gi´a tri

.n`ay. H`ınh 7.1

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

st

bc

de

• •

3

52

2

4

.

..

.

..

.

.......................................................................................................................................................................................................................

.

......................................................................................................................................................................................................................

.......................................................................................................................................................................................................................

.

......................................................................................................................................................................................................................

.

..

.

..

.

..

.

H`ınh 7.1: V´ı du

.vˆe

`ma

.ng vˆa

.n ta

˙’i.

D

-i

.nh ngh˜ıa 7.2.2 Ma

.ng vˆa

.n ta

˙’il`a mˆo

.t d¯o

.n d¯ˆo

`thi

.c´o hu

.´o

.ng, c´o tro

.ng sˆo

´Gsao cho

(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ˆo

`n) cu

˙’a ma

.ng, khˆong c´o cung

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)∈Ed¯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

.Gbˇ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 sv`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

´uGl`a ma

.ng vˆa

.n ta

˙’i ch´ung ta s˜e k´y hiˆe

.u d¯ı

˙’nh v`ao l`a sv`a d¯ı

˙’nh

ra l`a t.

D

-i

.nh ngh˜ıa 7.2.4 Gia

˙’ su

.

˙’ Gl`a ma

.ng vˆa

.n ta

˙’i v´o.i kha

˙’ nˇang cung (vi, vj) l`a qij .Luˆo

`ng (chˆa

´p

nhˆa

.n d¯u

.o.

.c) Ftrong Gg´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 vj6=s, t, ta c´o

X

i

fij =X

i

fji.(7.1)

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

.tfij = 0).

Ta n´oi fij l`a luˆo

`ng trˆen cung (vi, vj).V´o

.i mˆo

˜ij, ta go

.i

X

i

fij

l`a luˆo

`ng d¯ˆe

´n d¯ı

˙’nh vjv`a

X

i

fij

l`a luˆo

`ng ra kho

˙’i d¯ı

˙’nh vj.

D

-iˆe

`u kiˆe

.n (7.1) go

.i l`a ba

˙’o to`an luˆo

`ng. Trong v´ı du

.dˆa

˜n dˆa

`u cu

˙’a H`ınh 7.1, ba

˙’o to`an luˆo

`ng c´o

ngh˜ıa dˆa

`u khˆong d¯u

.o.

.c su

.

˙’ du

.ng v`a c˜ung khˆong d¯u

.o.

.c cˆa

´p thˆem ta

.i c´ac tra

.m bo.mb, 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,

x´ac d¯i

.nh luˆo

`ng trˆen ma

.ng vˆa

.n ta

˙’i cu

˙’a H`ınh 7.1. Chˇa

˙’ng ha

.n, luˆo

`ng d¯ˆe

´n d¯ı

˙’nh dl`a

fsd = 2,

bˇa

`ng luˆo

`ng ra kho

˙’i d¯ı

˙’nh d:

fdc +fde = 1 + 2 = 3.

Luˆo

`ng Fd¯u

.o.

.c v˜e trong H`ınh 7.2, trong d¯´o cung ed¯u

.o.

.c g´an nh˜an x, y nˆe

´u kha

˙’ nˇang cu

˙’ae

l`a xv`a luˆo

`ng trˆen el`a y.

st

bc

de

• •

3,2

5,32,2

2,1

2,2

4,3

4,2

.

..

.

..

.

.......................................................................................................................................................................................................................

.

......................................................................................................................................................................................................................

.......................................................................................................................................................................................................................

.

......................................................................................................................................................................................................................

.

..

.

..

.

..

.

H`ınh 7.2: Luˆo

`ng trˆen ma

.ng vˆa

.n ta

˙’i cu

˙’a H`ınh 7.1.

176

http://www.ebook.edu.vn

Ch´u ´y rˇa

`ng trong v´ı du

.n`ay, luˆo

`ng ra kho

˙’i d¯ı

˙’nh sl`a

fsb +fsd

bˇa

`ng luˆo

`ng 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

.

˙’ Fl`a luˆo

`ng trˆen ma

.ng vˆa

.n ta

˙’iG:= (V, E).Khi d¯´o luˆo

`ng ra kho

˙’i

d¯ı

˙’nh sbˇa

`ng luˆo

`ng d¯ˆe

´n d¯ı

˙’nh t;t´u

.c l`a

X

i

fsi =X

i

fit.

Ch´u

.ng minh. Ta c´o

X

j∈VÃX

i∈V

fij !=X

j∈VÃX

i∈V

fji!

do mˆo

˜i vˆe

´bˇa

`ng Pe∈Efe.V`ı vˆa

.y

0 = Pj∈V(Pi∈Vfij −Pi∈Vfji)

= (Pi∈Vfit −Pi∈Vfti) + (Pi∈Vfis −Pi∈Vfsi) + Pj∈V,j6=s,t (Pi∈Vfij −Pi∈Vfji)

=Pi∈Vfit −Pi∈Vfsi

do fti = 0 = fis v´o.i mo

.ivi∈V, v`a (7.1).

D

-i

.nh ngh˜ıa 7.2.7 Gia

˙’ su

.

˙’ Fl`a luˆo

`ng trˆen ma

.ng vˆa

.n ta

˙’iG. D

-a

.i lu

.o.

.ng

X

i

fsi =X

i

fit

go

.i l`a gi´a tri

.cu

˙’a luˆo

`ng F.

B`ai to´an trˆen ma

.ng vˆa

.n ta

˙’iGc´o thˆe

˙’ ph´at biˆe

˙’u:

B`ai to´an 7.2.8 T`ım mˆo

.t luˆo

`ng 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

ca

˙’ c´ac luˆo

`ng trˆen G, t`ım luˆo

`ng Fc´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

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

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi