Isang halimbawa ng paghahanap ng pinakamataas na daloy gamit ang paraan ng Ford-Fulkerson. Algorithm para sa paghahanap ng maximum na daloy

Sum of flows through arcs incident v, ay katumbas ng kabuuan ng mga daloy sa pamamagitan ng insidente ng arko w; ang kabuuan na ito ay tinatawag na flux value. Pangunahing magiging interesado tayo sa mga daloy na may pinakamalaking posibleng halaga - ang tinatawag na pinakamataas na daloy. Sa pangkalahatan, ang isang network ay maaaring magkaroon ng maraming magkakaibang mga maximum na daloy, ngunit ang kanilang mga halaga ay dapat na pareho. (4)

Ang pag-aaral ng pinakamataas na daloy sa pamamagitan ng isang network N = (V,D,a) ay malapit na nauugnay sa konsepto ng isang hiwa, i.e. tulad ng isang set A ng mga arko ng isang digraph D na may ari-arian na anumang simpleng chain ng v V dumadaan sa arko na kabilang sa A. Ang kapasidad ng isang hiwa ay ang kabuuan ng mga kapasidad ng mga arko na kabilang dito. Ang mga pagbawas na may pinakamaliit na posibleng throughput ay tinatawag na minimal cut.

Ang magnitude ng anumang daloy ay hindi lalampas sa throughput capacity ng anumang seksyon, at, dahil dito, ang magnitude ng anumang pinakamataas na daloy hindi lalampas sa kapasidad ng anumang minimum na hiwa. Gayunpaman, hindi agad malinaw na ang huling dalawang numero ay palaging pantay; Ang resultang ito ay nakuha ng mga Amerikanong mathematician na sina Ford at Fulkerson noong 1955 at tinawag na maximum flow at minimum cut theorem.

Theorem (tungkol sa maximum flow at minimum cut). Sa anumang network, ang laki ng anumang maximum na daloy ay katumbas ng kapasidad ng anumang minimum na hiwa.

Ang maximum flow at minimum cut theorem ay nagbibigay-daan sa iyo upang suriin kung ang isang naibigay na daloy ay maximum o hindi, ngunit para lamang sa medyo simpleng mga network. Siyempre, sa pagsasanay kailangan nating harapin ang malaki at kumplikadong mga network, at sa pangkalahatan ay mahirap hanapin ang maximum na daloy sa pamamagitan ng simpleng pagpili. Ilarawan natin ang isang algorithm para sa paghahanap ng maximum na daloy sa anumang network na may integer throughput.

Hakbang 1. Una, pumili tayo ng isang daloy na may hindi zero na halaga (kung may ganoong daloy). Halimbawa, kung ang N ay ang network na ipinapakita sa Fig. 29.3, pagkatapos ay ang daloy na ipinapakita sa Fig. 29.4. Kapansin-pansin na mas malaki ang halaga ng paunang daloy na aming pinili, mas madali ang mga susunod na hakbang.

Hakbang 2. Batay sa N, bumuo kami ng bagong network na N’ sa pamamagitan ng pagbabago ng direksyon ng daloy sa kabaligtaran. Mas tiyak, anumang arko a kung saan ang (a) = 0 ay nananatili sa N' kasama ang orihinal na kapasidad nito, at anumang arko a kung saan , ay pinapalitan ng isang arko a na may kapasidad at isang kabaligtaran na arko na may kapasidad (a). Ang Network N' sa aming halimbawa ay ipinapakita sa Fig. 29.5. Vertex v ay hindi na pinagmumulan, kundi isang lababo.

Hakbang 3. Kung sa network N’ makakahanap tayo ng non-zero flow mula sa v c, pagkatapos ay maaari itong idagdag sa orihinal na daloy at makakuha ng bagong daloy ng mas malaking halaga sa N. Ngayon ay maaari mong ulitin ang hakbang 2, gamit ang bagong thread na N' sa halip na N' kapag gumagawa ng network. Sa pamamagitan ng pag-uulit ng pamamaraang ito, sa kalaunan ay makakarating tayo sa isang network na N' na naglalaman ng walang mga di-zero na daloy; kung gayon ang katumbas na daloy ay ang pinakamataas na daloy. Halimbawa, sa Fig. 29.5 mayroong isang di-zero na daloy kung saan ang mga daloy sa pamamagitan ng mga arko ( v,u), (u,z), (z,x), (x,y) At ( y,) ay katumbas ng isa, at ang mga flux sa mga natitirang arko ay katumbas ng zero. Ang pagdaragdag ng daloy na ito sa daloy sa Fig. 29.4, nakuha namin ang daloy na ipinapakita sa Fig. 29.6; inuulit ang hakbang 2, madaling ipakita na ito ang pinakamataas na daloy.

Mga Ginamit na Aklat:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Asanov M.O., Baransky V.A., Rasin V.V. Discrete mathematics: mga matroid graph, algorithm

(3) Basaker R., Saati T. May hangganang mga graph at network.

(4) Wilson R. Panimula sa Teoryang Graph

Hayaang magbigay ng nakadirekta na graph G= , kung saan ang direksyon ng bawat arko vÎV nangangahulugang direksyon ng daloy (halimbawa, ang daloy ng mga sasakyan), throughput ang bawat arko ay pantay d(v). Sa maraming mga taluktok E dalawang vertex ang naka-highlight t At s. Vertex t ang pinagmulan ng daloy, s- alisan ng tubig. Ito ay kinakailangan upang matukoy ang maximum na daloy na maaaring maipasa mula sa vertex t V s .

Ipahiwatig natin sa pamamagitan ng x(v) ang dami ng daloy na gumagalaw sa isang arko v. Obvious naman yun

0 £ x(v) £ d(v) , vÎV . (6. 1)

Sa bawat rurok iÎE\(t,s) ang dami ng papasok na daloy ay katumbas ng dami ng papalabas na daloy, i.e. ang pagkakapantay-pantay ay totoo

(x(v)|i О V + (i))= (x(v)| iО V - (i))

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

Para sa tuktok t

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

para sa vertex s

(x(v)| iО V + (i)) -(x(v)¦ i О V - (i))= Q.(6.4)

Magnitude Q ay ang magnitude ng daloy na umaalis sa vertex t at pumasok sa tuktok s.

Kailangang matukoy

Q ® max(6.5)

sa ilalim ng mga paghihigpit (6.1-6.4).

Dami Q, x(v), vÎV, kasiya-siyang mga paghihigpit (6.1-6.4) tatawag tayo ng daloy sa network, at kung ma-maximize nila ang halaga Q, pagkatapos ay ang maximum na daloy. Ito ay madaling makita na ang mga halaga Q=0, x(v)=0, vÎV, ay isang daloy sa network.

Ang Problema (6.1-6.5) ay isang linear programming problem at maaaring lutasin gamit ang simplex method algorithm.

Hatiin natin ang hanay ng mga vertices E sa dalawang magkahiwalay na bahagi E1 at E2 sa paraang tÎE1, sÎE2. Sa pamamagitan ng hiwa V(E1,E2), naghihiwalay t At s tatawagin natin ang set V(E1,E2)ÌV na para sa bawat arko v О V(E1,E2) o h1(v)ОE1 At h2(v)ОE2, o h1(v)ОE2 At h2(v)ОE1.

Hatiin natin ang set V(E1,E2) sa dalawang bahagi V(E1,E2+),V(E1,E2,-) sa sumusunod na paraan:

V(E1,E2+)=(vÎV(E1,E2)| h1(v)ÎE1 At h2(v)ОE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1 At h1(v)ОE2)

Tatawagin natin ang throughput capacity ng cut

Q(E1,E2) = (x(v)| vÎV(E1,E2+))-(x(v)| vÎV(E1,E2,-))

Ang sumusunod ay totoo

Teorama 1. (Tungkol sa maximum flow at minimum cut).

Sa anumang network, ang maximum na daloy mula sa pinagmulan ay t sa stock s katumbas ng pinakamababang throughput Q(E1,E2) sa lahat ng mga hiwa V(E1,E2), na naghihiwalay sa mga vertex t At s.

Tandaan na sa pinakamataas na daloy

x(v)=d(v) , vÎV(E1,E2+),

x(v)=0 , vÎV(E1,E2,-).

Hayaan Q, x(v), vÎV, - ilang daloy ng network, pagkakasunud-sunod

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

ay isang kadena na nagdudugtong sa mga vertex t At s. Itakda natin ang direksyon ng paggalaw sa chain na ito mula sa itaas t Upang s. Arc v(j) mula sa kadena na ito ay tinatawag na isang tuwid na linya kung ang direksyon nito ay tumutugma sa direksyon ng paggalaw mula sa t Upang s, at ang reverse kung hindi man. Tatawagin nating landas ang kadena na ito pagtaas ng daloy, kung para sa mga tuwid na arko v mga tanikala x(v)< d(v) at para sa kabaligtaran x(v) > 0. Ang isang karagdagang daloy ay maaaring maipasa sa circuit na ito q mula sa t Upang s laki q = min (q1,q2), saan q1=min (d(v) -x(v)), ang minimum ay kinuha sa lahat ng tuwid na arko ng chain, q1=min (x(v)), ang minimum ay kinukuha sa lahat ng reverse arc ng chain.

Teorama 2.

Daloy Q, x(v) , vÎV, ay maximum kung at tanging kung walang paraan upang mapataas ang daloy.

Ang iminungkahing algorithm para sa paglutas ng problema ng maximum na daloy sa isang network ay batay sa paghahanap ng isang paraan upang mapataas ang daloy mula sa t V s, na nakabatay naman sa proseso ng pag-aayos ng mga vertex label. Sabihin na natin

kaitaasan i minarkahan ng marka q(i)>0, at kilala rin ang straight arc arc v(i), kung saan dumating ang daloy na ito, o minarkahan ng , kung ilang karagdagang daloy ng magnitude q(i)>0, at kilala rin ang reverse arc v(i), kung saan pumasok ang daloy na ito;

ang vertex i ay titingnan kung ang lahat ng mga kalapit na vertex nito ay minarkahan.

Kung minarkahan ang vertex s, may nakitang landas na magpapalaki ng daloy ayon sa magnitude q, na dumaraan sa landas na ito. Upang ilarawan ang algorithm kailangan din namin ng isang array SPW, na naglalaman ng mga bilang ng mga minarkahang vertice sa pagkakasunud-sunod kung saan sila minarkahan. C1- numero sa array SPW tiningnan ang tuktok, C2- ang bilang ng huling minarkahang vertex sa array na ito.

Ang manwal na ito ay inilaan para sa mga mag-aaral na kumukuha ng mga kurso sa discrete mathematics at/o graph theory. Sa tulong nito ay makabisado mo ang paksang "Maximum flow at minimum cut sa network." Direkta mula sa manwal na ito, maaari mong kalkulahin ang iyong ID, kahit na wala kang MATLAB sa iyong computer. Kung mayroon kang MATLAB, pumunta sa pahinang ito: doon mayroon kang pagkakataong makialam sa script ng pagkalkula (program). Dito, ang problema ng maximum na daloy sa network ay nalutas sa pamamagitan ng pagbabawas nito sa isang linear programming problem.

Ipakilala natin ang sumusunod na notasyon:

• n=|V| − laki ng graph (bilang ng mga vertex);
• m=|E| − graph cardinality (bilang ng mga gilid);
• A − incidence matrix ng isang network digraph ng laki n× m; bawat elemento nito isang ik=1 kung mula sa i-lumabas ang tuktok k-i arc; isang ik=−1, kung sa i pumapasok ang th vertex k-i arc; At isang ik=0 sa ibang mga kaso; sa bawat haligi ng naturang matrix ay may eksaktong isa, isang minus one, at ang natitira ay mga zero;
• s− numero ng source vertex ng network; mga arko lamang ang dapat lumabas mula sa tuktok na ito, at anumang iba pang tuktok ay dapat maabot mula sa pinagmulan;
• t− numero ng network sink vertex; ang mga arko lamang ang dapat pumasok sa vertex na ito, at ang isang drain ay dapat maabot mula sa anumang iba pang vertex;
• a s − s A ; ito ay dapat maglaman lamang ng ilan, dahil mga arko lamang ang dapat lumabas mula sa pinagmulan;
• a t − t-ika-row ng incidence matrix ng network digraph A ; dapat ay naglalaman lamang ito ng mga minus, dahil ang mga arko lamang ang dapat pumasok sa alisan ng tubig;
• A st− incidence matrix ng network digraph A kasama ang mga itinapon dito s ika at t ika linya;
• e − column vector ng haba m; sa bawat elemento nito e k ang magiging magnitude ng daloy sa k ika-arko;
• c − column vector ng haba m; sa bawat elemento nito c k Itinatakda ng ≥0 ang throughput k ika-arko.

Kung gayon ang pinakamataas na problema sa daloy ng network ay maaaring mabalangkas bilang isang linear na problema sa programming:

Ang kabuuang daloy na umaalis sa pinagmulan (1) ay na-maximize. Bukod dito, sa anumang intermediate vertex ang papasok na daloy ay katumbas ng papalabas na daloy (2), at ang kapasidad ng mga arko ay limitado (3).

Ang dalawahang problema hanggang sa maximum na problema sa daloy ay ang problema sa minimum na hiwa. Upang makabuo ng isang minimal na hiwa, maaari mong gamitin ang duality theorems. Kailangang:

• alisin ang lahat ng walang laman mula sa network digraph ( e k= 0) at puspos ( e k = c k) mga arko;
• hanapin ang mga konektadong bahagi ng natitirang graph;
• kung mayroong dalawang tulad na mga bahagi, kung gayon ang mga itinapon na arko ay nagbibigay ng kaunting hiwa;
• kung higit sa dalawang konektadong bahagi ang lumitaw, kung gayon ang network digraph ay may ilang kaunting mga pagbawas (ang kaukulang problema sa linear programming ay bumababa).

Para sa isang lumalalang problema, ang unang minimal na hiwa na pinakamalapit sa pinagmulan ay itinayo sa pahinang ito.

Para sa tamang operasyon sa pahinang ito dapat na sinusuportahan ng iyong browser ang mga script Java Script. I-on ang mga ito.

Ilagay ang paunang data sa mga lugar ng pag-input sa ibaba. Sa unang lugar, kailangan mo (mas tiyak, maaari mong) ipasok ang mga coordinate ng vertices upang gumuhit ng isang digraph ng network. Ang mga ito ay tinukoy sa anyo ng isang matrix n×2: sa unang hanay − x ika-coordinate, sa pangalawang − y-e. Maaaring tukuyin ang mga numero bilang mga integer, na may decimal point, o sa exponential form. Paghiwalayin ang mga numero na may mga puwang. Kabuuan Tinutukoy ng mga linya sa lugar ng pag-input na ito ang laki ng digraph n− bilang ng mga vertex. Ang mga paunang data na ito (vertex coordinates) ay opsyonal: kung hindi tinukoy ang mga ito, ang network digraph ay iguguhit bilang isang tama n-gon, at ang bilang ng mga vertex ay matutukoy ng pinakamataas na numero ng vertex sa susunod na lugar ng pag-input.

Sa susunod na lugar ng pag-input, ang kaliwang bahagi ay kinakailangan. Tinutukoy nito ang istraktura ng digraph ng network. Ang bawat arko sa isang digraph ay nag-uugnay sa dalawang vertice. Ang mga numero ng mga vertex na ito ay tinukoy sa anyo ng isang matrix m×2 sa kaliwang bahagi ng pangalawang lugar ng pag-input. Sa bawat linya, ang 1st vertex (buntot, pinagmulan) ng arc ay unang tinukoy, at pagkatapos, sa pamamagitan ng isang espasyo, ang 2nd vertex (tip, drain) ng arc ay tinukoy. Dapat ay mayroon ang mga column na ito mga integer mula 1 hanggang n kasama. Paghiwalayin ang mga numero na may mga puwang. Sa kanang bahagi, ang mga kapasidad ng mga arko ay tinukoy - mga positibong tunay na numero. Kung ang column na ito ay hindi tinukoy, ang lahat ng mga kapasidad ay itinuturing na pareho (isa). Tinutukoy ng kabuuang bilang ng mga numero sa bawat isa sa mga column na ito ang cardinality ng digraph m− bilang ng mga arko.

Gawain sa transportasyon
Maaaring lumitaw sa pisika, ekonomiya, atbp.
Sa mga indibidwal na bahagi ng network ng transportasyon
(network ng mga riles, kalsada, atbp.
mga landas; pipeline network, atbp.) superimposed
mga paghihigpit - ang kanilang pinakamataas na pinahihintulutan
load.
Ito ay kinakailangan upang matukoy ang maximum
posibleng bilang ng mga pasahero, kalakal,
produkto, atbp., na maaaring dalhin sa pamamagitan nito
network at kung paano.
Bubuo kami ng discrete graph model
itong problema sa transportasyon at lutasin ito dito
mga modelo.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.