border=0


Seksje 3. Netwurk streamt en relatearre taken




Netwurk streamt

Folsleine stream yn it transportnetwurk

De teory fan transportnetwurken ûntstie by it oplossen fan problemen ferbûn mei de organisaasje fan ferfier fan guod. Dochs wie it begryp fan in stream op in ferfiernetwurk, it algoritme foar it finen fan 'e stream fan' e grutste omfang, en it kritearium foar it bestean fan in stream dy't de útfierbôgen fan it netwurk fersadiget, nuttich te wêzen foar in protte oare tapaste en teoretyske fragen fan kombinatoryske aard.

Wy yntrodusearje de basisbegripen fan dizze teory.

In transportnetwurk is in digraaf D = (V, X) mei in protte hoekpunten V = {v 1 , ..., v n }, wêr't de folgjende betingsten binne foldien:

1) d'r is ien en mar ien toppunt v 1 , de boarne neamd, sa dat Г -1 (v 1 ) = Æ (d.w.s. gjin bôge komt yn v 1 ),

2) der is ien en mar ien toppunt v n , in sinke neamd, sa dat Г (v n ) = Æ (d.w.s. gjin bôge komt fan v n ),

3) elke bôge xÎX wurdt assosjeare mei in heule getal c (x) ³ 0, de bôge-trochfier neamd.

In funksje j (x) definieare op 'e set X fan bogen fan it ferfiernetwurk D en it nimmen fan heule getallen hjit in tastiene stream (of gewoan in stream) yn it ferfiernetwurk D as

1) foar elke bôge xÎX, foldocht de kwantiteit j (x), neamd de stream lâns de bôge x, oan 'e tastân 0 £ j (x) £ c (x),

2) foar alle tuskentiidse toppunt v is de som fan de streamingen lâns bôgen dy't yn v binne gelyk oan de som fan de streamingen lâns bôgen dy't ûntsteane út v.

De grutte fan 'e stream j yn it transportnetwurk D is de wearde gelyk oan de som fan' e streammen lâns alle bôgen dy't yn 'e riolearring reitsje, of, itselde, de som fan' e streamingen lâns alle bôgen dy't fan oarsprong binne.

In bôge xÎX hjit verzadigd as de stream dêrop gelyk is oan syn trochfier. Stream j wurdt kompleet neamd as elk paad yn it netwurk fan boarne oant sink teminsten ien verzadigde bôge befettet.

A l g r r en t m

it bouwen fan in folsleine stream yn it netwurk

Gegevens: ferfiernetwurk D definieare troch de matrix fan trochputbogen.

Resultaat: folsleine netwurkstream.

1) Wy oannimme foar elke bôge xÎX j (x) = 0 (wy begjinne fan nulstream).

2) Put D * = D.

3) Wy ferwiderje fan 'e digraaf D * alle bôgen dy't wurde verzadigd tidens stream j yn it transportnetwurk D. De resultearjende digraaf wurdt opnij oantsjutten mei D *.

4) Wy sykje yn D * nei in ienfâldige ketting m fan v 1 oant v n . As d'r gjin sa'n ketting is, dan is j de winske folsleine stream yn it transportnetwurk D. Gean dan oars nei stap 5.

5) Wy ferheegje de flux j (x) foar elke bôge x fan m mei deselde wearde a> 0, sadat teminsten ien bôge fan m is verzadigd, en de streamingen lâns alle oare bôgen fan m net mear as har trochfier binne. Yn dit gefal sil de wearde fan 'e stream j ek tanimme mei a, en de stream j sels yn it transportnetwurk D bliuwt jildich. Gean dêrnei nei stap 3.


border=0


Maksimale stream

In stream j wurdt maksimum neamd as syn wearde in maksimale wearde nimt yn ferliking mei oare tastiene streamingen yn it transportnetwurk D. De maksimale stream is altyd folslein (it petear is, yn 't algemien, net wier).

Foar in gegeven transportnetwurk D en in tastiene stream j yn dit netwurk, yntrodusearje wy de digraaf fan stappen I (D, j) mei deselde hoekpunten as it netwurk D. Oan elke bôge x = (v, w) Î X fan it transportnetwurk D yn 'e digraaf fan stappen I (D, j) dêr korrespondearje twa bôgen: x en x * = (w, v) - in bôge tsjinoer yn rjochting nei de bôge x. Wy tawize oan bôgen x en x * de digraaf fan 'e stappen I (D, j) de lingte l:

0 as j (x) <c (x),

l (x) =

¥ as j (x) = c (x),

0 as j (x)> 0,

l (x *) =

¥ as j (x) = 0.

A l g r r en t m

gebou maksimale stream

Gegevens: ferfiernetwurk D definieare troch de matrix fan trochputbogen.

Resultaat: maksimale netwurkstream.

1) Wy stelle i = 0. Lit j 0 elke tagonklike stream wêze yn it transportnetwurk D (bygelyks folslein as nul).

2) Mei it gebrûk fan it netwurk D en de stream j i, konstruearje wy de digraaf fan 'e stappen I (D, j i ).

3) Wy fine in ienfâldige ketting m i dat it minimale paad is fan v 1 nei v n yn 'e laden digraaf I (D, j i ) (elk hjirboppe beskreaun algoritme kin brûkt wurde). As de lingte fan dizze ketting ¥ is, dan is de stream j i maksimum en it algoritme einiget. Oars ferheegje wy de stream lâns de ketting m i mei de maksimale tastiene wearde a i > 0, wêrby't in i ÎZ (tafoegje dizze foar elke bôge xÎX wêrtroch de ketting m i trochjout nei de al besteande wearde fan 'e stream lâns de bôge x, as de bôge x ynkomt yn m i , en aftrekken as de bôge x * is opnommen yn m i ), sadat de tastân fan 'e tastiene stream wurdt bewarre. As resultaat feroaret de stream yn it transportnetwurk D, d.h. fan 'e stream j gean ik nei de stream j i + 1 , dy't jildich is, en tagelyk nimt de wearde mei in i ta . Tawize i = i + 1 en gean nei stap 2.



Etiketalgoritme foar it finen fan maksimale stream

Betink in oar algoritme foar it konstruearjen fan de maksimale stream yn in transportnetwurk mei help fan toppunktetiketten.

Ford-Fulkerson-taggenalgoritme

de maksimale stream te finen

Gegevens: ferfiernetwurk D definieare troch de matrix fan trochputbogen.

Resultaat: maksimale netwurkstream.

1) Bou in willekeurige stream φ op it transportnetwurk D (set bygelyks φ (u) = 0 foar elke bôge u).

2) Besjoch de paden dy't de ynfier fan it netwurk v 1 ferbine mei de útfier v n . As de stream φ folslein is, gean dan nei stap 4.

3) Asjebleaft beskôgje it paad μ dat de ynfier fan it netwurk v 1 ferbynt mei de útfier v n , alle bogen dy't net satureare binne. Bou in nije stream φ´:

wêr . Werhelje dit proses oant it is ûntfongen.

folsleine stream φ.

4) Telle heule labels oan de hoekpunten fan it netwurk D en tekenje "+" of "-" oan de bôgen neffens de regels:

· Ynfier v 1 label 0 tawize,

· As de toppunt v i wat label hat ûntfongen, en y is de unmarkeare toppunt, dan is de toppunt y Гv i sa dat φ ((v i , y)) <c ((v i , y)) label i tawize, en oan 'e bôge (v i , y) it teken "+"; top y Г -1 v i , sa dat φ ((y, v i ))> 0, tawize it label i, en oan 'e bôge (y, v i ) - "-". Oare untagged hoekpunten en bôgen krije gjin tekens en tekens;

· Werhelje it proses beskreaun yn 'e foarige paragraaf oant it uterlik fan nije markearre hoekpunten en bôgen ophâldt. As, as gefolch fan dit artikel, de toppunt v n gjin labels krije, dan is de stream maksimaal. Gean oars nei stap 5.

5) Beskôgje de sekwinsje fan markearre hoekpunten λ = (v n, v i1 , v i2 , ..., v 1 ), dy't elk in label hat gelyk oan it oantal fan 'e folgjende toppunt, en in sekwinsje μ (net needsaaklik in paad) dy't opienfolgjende hoekpunten ferbine fan λ. Bou in nije stream φ´:

Gean nei stap 4.

In foarbyld . Tink oan it transportnetwurk D en de totale stream φ, wêrfoar = 14:

2 (1, +)

7 (8) 7 (7)

0 (1, +) 5 (3, -) 6 (4, +)

1 4 (5) 3 6 (7) 1 (1)


3 (3) 10 (10) 0 (3) 13 (15)

4 (5, +) Fig. 1

Wiskje 1 label 0 tawize, en dan toppunt 2 label jouwe (1, +), om't φ ((1,2)) <c ((1,2)). Omdat φ ((2,5)) = c ((2,5)), gean dan nei toppunt 3, wêr't wy it label (1, +) tawize, dan nei toppunt 5 - (3, -), nei toppunt 4 - (5, + ), toppunt 6 - label (4, +). Tink oan de sekwinsje fan hoekpunten λ = (6,4,5,2,1), en konstruearje in nije stream wêrfan de wearde 15 is.

2 (1, +)

7 (8) 7 (7)

0 5 6

1 5 (5) 3 5 (7) 1 (1)


3 (3) 10 (10) 1 (3) 14 (15)

4 Fig. 2

It is maklik om te sjen dat dizze stream net kin wurde ferbettere.





; Datum tafoege: 2018-01-08 ; ; views: 332 ; Brûkt publisearre materiaal ynbreuk op auteursrjocht? | | Beskerming fan persoanlike gegevens | ORDERJOB


Hawwe jo net fûn wat jo sochten? Brûk de sykopdracht:

Bêste spreuken: By it trochjaan fan it laboratoarium makket de studint út as hy alles wit; de learaar makket him leau. (9117) - | 7229 - of lês alles ...

2019 @ edudocs.fun

Side generaasje yn: 0.006 sek.