Jungumas

Jungumas

Jungusis grafas – tai grafas, kuriame bet kuri viršûniø pora sujungta grandine. Pavyzdžiui, (žr. 1 pav.) K₅ ir C₅ yra jungieji grafai, taèiau intuityviai jauèiame, kad K₅ yra labiau jungus nei C₅.

1 pav. Jungumas

Grafo jungumo klausimas yra aktualus praktikoje. Tarkime, reikia suprojektuoti kompiuteriø tinkl¹. Tinkl¹ sudaro informacijos saugojimo ir apdorojimo centrai, kurie jungiami ryšio kanalais. Informacijos pasikeitimas tarp dviejø centrø vyksta arba tiesiogiai per šiuos centrus jungiantá ryšio kanal¹ (jei toks yra), arba per kitus centrus ir juos jungianèius ryšio kanalus. Aišku, kad tinklo grafas, kurio viršûnës vaizduoja centrus, o dvi viršûnës jungiamos briauna, jei tarp viršûnëms atitinkanèiø centrø yra ryšio kanalas, turi bûti jungusis. Labai svarbus tinklo parametras yra jo patikimumas: tinklas turi funkcionuoti net ir tuo atveju, jei sugenda keli centrai arba ryšio kanalai. Šá parametr¹ kiekybiškai galima ávertinti per žemiau ávestas s¹vokas.

Viršûninio jungumo skaièius. Tai mažiausias skaièius viršûniø, kurias pašalinus, grafas G tampa arba nejungiuoju grafu arba vienos viršûnës grafu. Šis skaièius žymimas .

Briauninis jungumo skaièius. Tai mažiausias skaièius briaunø, kurias pašalinus, grafas G tampa nejungiuoju grafu. Šis skaièius žymimas .

Pavyzdžiui, , .

2 pav. grafui (pašalinus 4-¹j¹ viršûnê, grafas suyra), o (pašalinus briaunas (4, 6), (4, 7), (4, 8) grafas suyra).

2 pav. Grafo jungumo kiekybiniai áverèiai

Grafo G viršûnë v vadinama s¹lyèio tašku, jei G – v turi daugiau jungiøjø komponenèiø nei grafas G.

Grafo G briauna vadinama tiltu, jei, j¹ pašalimus, gautasis grafas turi daugiau jungiøjø komponenèiø nei grafas G.

Pavyzdžiui, 3 pav grafas turi tris s¹lyèio taškus (viršûnës 4, 5, 6) ir vien¹ tilt¹ (briauna (4, 5)).

3 pav. Grafo s¹lyèio taškai ir tiltai

Grážtant prie paragrafo pradžioje pateikto pavyzdžio, nesunku pastebëti, kad grafo viršûninio jungumo ir briauninio jungumo skaièius parodo tinklo atsparum¹ centrø ir ryšio kanalø gedimams, o s¹lyèio taškai bei tiltai parodo labiausiai pažeidžiamas tinklo vietas.

Teorema. Kiekvienam grafui

èia , o – v-osios viršûnës laipsnis.

Teorema. Beveik kiekvienam grafui[6] teisinga lygybë

Grafas vadinamas k-jungiuoju, jei ir briaunomis k-jungiuoju, jei .

Jei , tai grafas vadinamas dviryšiu

2 pav. pavaizduotas grafas yra 1-jungusis ir briaunomis –
3-jungusis. Ai ku, kad šis grafas turi pografius, kurie yra labiau jungieji nei pats grafas. Pavyzdžiui, pografis, kurá indukuoja viršûniø aibë, yra 3-jungusis. Tokiø pografiø apibûdinimui ávedama k-jungiosios komponentës s¹voka.

Grafo k-jungioji komponentë – tai maksimalus k-jungusis pografis. Jis dažnai vadinamas k-komponente.

Pavyzdžiui, 4 pav. grafas G₁ turi dvi 2-jungi¹sias komponentes (pografiai, kuriuos indukuoja viršûniø ir aibës), o grafas G₂ turi dvi 3-komponentes (pografiai, kuriuos indukuoja viršûniø ir aibës). Taèiau reikia pabrëžti, kad abu grafai G₁ ir G₂ yra 1-jungieji. Be to, nesunku pastebëti, kad dvi 2-komponentës turi vien¹ bendr¹ viršûnê (Grafe G₁ – tai 3-ioji viršûnë), o dvi 3-komponentës turi dvi bendras viršûnes (grafe G₂ – tai 4-oji ir 6-oji viršûnës).

Teorema. Dvi skirtingos grafo G k-komponentës turi ne daugiau nei bendrø viršûniø.

Apibrëžimas. Dvi -grandinës vadinamos nesusikertanèiomis (viršûnëmis nesusikertanèiomis), jei jos neturi bendrø viršûniø, išskyrus a ir b.

Teorema (H.Witney, 1932). Grafas yra k-jungusis tada ir tiktai tada, kai bet kuri nesutampanèiø viršûniø pora sujungta ne mažiau kaip k viršûnëmis nesusikertanèiø grandiniø.

Apibrëžimas. Sakoma, kad grafo G viršûniø poaibis S skiria viršûnes a ir b, jei grafe viršûnës a ir b priklauso skirtingoms jungiosioms komponentëms.

4 pav. Grafo k-komponentës

Teorema (K.Mengeras, 1927). Mažiausias skaièius viršûnø, skirianèiø dvi negretimas viršûnes a ir b, yra lygus didžiausiam skaièiui poromis nesusikertanèiø grandiniø, jungianèiø a ir b viršûnes.

Áveskime skirianèiø briaunø s¹vok¹.

Apibrëžimas. Briaunø aibë R skiria grafo G a ir b viršûnes, jei grafe viršûnës a ir b priklauso skirtingoms jungiamosioms komponentëms.

Teorema. Mažiausias skaièius briaunø, skirianèiø grafo G viršûnes a ir b, yra lygus didžiausiam briaunomis nesusikertanèiø grandiniø, jungianèiø a ir b viršûnes, skaièiui.

Dviryšiai grafai

Tiek grafø teorijoje, tiek ir praktikoje svarbi¹ viet¹ užima 2-jungieji grafai, kurie vadinami dviryšiais grafais.

Kaip buvo minëta aukšèiau, grafas yra dviryšis, jei bet kuri¹ nesutampanèiø viršûniø a ir b por¹ jungia bent dvi viršûnëmis nesusikertanèios grandinës.

Galima pateikti ir kit¹ dviryšio grafo apibrëžim¹: grafas vadinamas dviryšiu, jei jis neturi s¹lyèio taškø.

Apibrëžimas. Didžiausias galimas grafo G pografis, neturintis s¹lyèio taškø, vadinamas dvigubo jungumo komponente arba bloku.

Grafo dvigubo jungumo komponenèiø bei s¹lyèio taškø ieškojimo uždavinys turi svarbi¹ reikšmê. Pavyzdžiui, visi komunaliniai ir transporto tinklai negali turëti s¹lyèio taškø, t.y. mažiausiai jie turi bûti dviryšiai.

Dvigubo jungumo komponenèiø išskyrimas grafe padeda sprêsti nepriklausomø ciklø radimo uždaviná bei nustatyti, ar grafas yra plokštusis.

Aptarsime grafo dvigubo jungumo komponenèiø (dviryšiø komponenèiø, blokø) radimo uždaviná.

S¹lyèio taško savybë. Neorientuotojo jungiojo grafo G viršûnë a yra s¹lyèio tašku tada ir tiktai tada, kada egzistuoja tokios kitos dvi grafo viršûnës x ir y, kad bet kuris kelias tarp viršûniø x ir y eina par viršûnê a.

Pavyzdžiui, 5 a) pav. Pavaizduotas grafas G, o 5 b) pav. – to grafo dvigubo jungumo komponentës.

5 pav. Grafo dvigubo jungumo komponentës

Ši s¹lyèio taško savybë ágalina panaudoti paieškos gilyn metod¹, apskaièiuojant grafo G dvigubo jungumo komponentes – blokus.

Panagrinëkime pavyzdá (žr. 6 pav.).

6 pav. Grafo blokinë schema

6 pav. schematiškai vaizduoja jungøjá graf¹, susidedantá iš 9-iø dvigubo jungumo komponenèiø bei turintá 5-is s¹lyèio taškus v₁, v₂, v₃, v₄, ir v₅.

Tarkime, kad paiešk¹ gilyn pradëjome iš 9-ojo bloko G₉ viršûnës s, ir visas aplankytas viršûnes (briaunas) talpiname á stek¹ STEK. Pradëjê paiešk¹ iš viršûnës s, per viršûnê v₂ galime patekti á blok¹ . Remiantis paieškos gilyn savybe, kad per viršûnê v₂ grášime, kai bus aplankytos visos viršûnës, galime teigti, kad sudaro viršûnës (briaunos), kurios buvo aplankytos tarp áëjimo ir grážimo per viršûnê v₂.

Su kitomis dvigubo jungumo komponentëmis reikalas sudëtingesnis. Iškeliavê iš viršûnës s, galime patekti á jungumo komponentê G₃, o iš G₃ per viršûnê v₃ – patekti á komponentê G₂. Taèiau ir šiuo atveju, kai aplankytos viršûnës (briaunos) saugomos steke STEK, grážtant per viršûnê v₃, visos aplankytos bloko G₂ viršûnës bus steko viršuje (nuo steko viršaus iki viršûnës v₃). Pašalinus iš steko šias viršûnes, steko viršuje liks bloko G₃ viršûnës, kurios buvo aplankytos iki patekome á blok¹ G₂. Kai grášime á viršûnê v₂, steko viršuje bus visos bloko G₃ viršûnës.

Vadinasi, jei mokëtume atpažinti s¹lyèio taškus, tai naudodami paiešk¹ gilyn ir saugodami aplankytas viršûnes (briaunas) steke ta tvarka, kuria jos buvo aplankytos, galime rasti dvigubo jungumo komponentes: viršûnës (briaunos), esanèios steko viršuje grážimo per s¹lyèio tašk¹ metu, sudaro dvigubo jungumo komponentê.

Aptarkime formali¹ s¹lyèio taškø radimo s¹lyg¹.

Tarkime, kad – jungusis neorientuotasis grafas. Tarkime, kad T – já dengiantis medis su šaknimi r, sukonstruotas paieškos gilyn iš viršûnës r metodu.

1 lema. Šaknis r yra s¹lyèio taškas tada ir tiktai tada, kai r turi daugiau nei vien¹ sûnø (žr. 7 pav.).

7 pav. Dengianèio medžio T šaknis r – s¹lyèio taškas

2 lema. Viršûnë yra grafo s¹lyèio taškas tada ir tiktai tada, kai yra nors vienas viršûnës v sûnus r, kuris neturi atvirkštiniø briaunø, jungianèiø já patá arba bet kurá jo palikuoná su viršûnës v protëviu (žr. 8 pav.).

Priminsime, kad grafo G atvirkštinës briaunos yra visos briaunos, nepriklausanèios dengianèiojo medžio T briaunø aibei.

8 pav. Dengianèio medžio T viršûnë v – s¹lyèio taškas

S¹lyèio taškams rasti kiekvienai grafo viršûnei v ávesime du parametrus: ir .

Parametras yra viršûnës v aplankymo eilës numeris, atliekant paiešk¹ gilyn iš viršûnës r.

Parametras [7] – tai mažiausias aplankymo numeris viršûnës x, á kuri¹ galime patekti iš viršûnës v grandine, sudaryta iš nulio arba daugiau dengianèio medžio briaunø ir nedaugiau kaip vienos atvirkštinës briaunos (žr. 9 pav.).

9 a) pav. pavaizduotas grafas G, o 9 b) pav. pavaizduotas t¹ graf¹ dengiantis medis, sukonstruotas paieškos gilyn iš 1-osios viršûnës metodu. Medžio briaunos pavaizduotos ištisine, o atvirkštinës briaunos – punktyrine linija. Romëniškais skaièiais pažymëti viršûniø aplankymo eilës numeriai, o parametro reikšmës apibrëžtos.

9 pav. Parametrø nr[v] ir low[v] reikšmës

Pasinaudodami parametrais ir galima 2 lemos kriterijø perrašyti kaip teorem¹.

Teorema. Viršûnë yra grafo G s¹lyèio taškas tada ir tiktai tada, kai v turi sûnø s, kuriam .

Pavyzdžiui, 9 a) pav. grafui s¹lyèio taškai yra: 1-oji viršûnë (medžio šaknis, turinti du sûnus), 6-oji viršûnë (ji turi sûnø , kuriam ) ir 8-oji viršûnë (ji turi sûnø , kuriam ).

Bendresnis pavyzdys pateiktas 10 paveiksle. Èia 10 a) pav. duotas grafas, o 10 b) – já dengiantis medis, sukonstruotas naudojant paiešk¹ gilyn iš 1-osios viršûnës. Simboliø prie medžio reikšmës tos paèios, kaip ir 9 b) pav. Remiantis aukšèiau pateiktu nagrinëjimu, nesunku apskaièiuoti, kad šio grafo s¹lyèio taškai yra: 1-oji viršûnë (šaknis, turinti du sûnus), 6-oji viršûnë (sûnaus parametras ), 8-oji viršûnë (turi du sûnus ir , kuriø ) ir 11-oji viršûnë (sûnaus ).

Parametr¹ galima apibrëžti rekurentiškai:

low[v] = min (nr[v]; low[s], èia s – viršûnës v sûnus; nr[w], èia (v, w) – atvirkštinë briauna).

10 pav. S¹lyèio taškø apskaièiavimas

Remiantis šiuo apibrëžimu, reikšmë apskaièiuojama taip.

Kai viršûnë v paieškos gilyn metu yra aplankoma pirm¹ kart¹, tai

Kai nagrinëjama atvirkštinë briauna , tai .

Kai grážtame á viršûnê v, pilnai apëjus visas briaunas, incidentiškas sûnui s, tai .

Kai grážtame á viršûnê v, pilnai apëjus visas briaunas, incidentiškas sûnui s, tai reikšmë nusistovi. Jei šiuo metu , tai, pagal teorem¹, v yra s¹lyèio taškas.

Žemiau pateikta dvigubo jungumo komponenèiø ieškojimo procedûra, kurios pagrind¹ sudaro paieškos gilyn algoritmas, išnagrinëtas 2.8.1.2 paragrafe, ir kuris papildytas aukšèiau aptartu s¹lyèio taškø s¹lygos tikrinimu bei blokø formavimu.

const c

type

mas = array [1..c] of integer;

matr = array [1..2, 1..c] of integer;

procedure blok (n, m : integer; L, lst : mas; var st : mas);

var i, k, u : integer;

s, sk, tau : integer;

t, p, pirma : boolean;

fst, prec : mas;

stek : mas;

nr, low : mas;

begin

pirma := false;

v

nr [v] := 1;

low [v] := 1;

sk

tau

for i := 1 to n do begin

fst [i]:= lst [i] + 1;

prec [i] := 0;

st [i] := 0;

end

k := v;

if fst [k] <= lst [k + 1] then

begin

t := false;

p := true;

prec [k] := k;

end

else

t := true;

while not t do

begin

while p do

begin

u := L [fst [k]];

if prec [u] = 0 then

begin

sk := sk +1;

nr [u] := sk;

low [u] := nr [u];

tau := tau + 1;

stek [tau] := k;

tau := tau + 1;

stek [tau] := u;

prec [u] := k;

if fs t [u] <= lst [u + 1] then

k := u

else

p := false;

end

else

begin

if (prec [k] <> u) and (nr [k] > nr[u]) then

begin

tau := tau + 1;

stek [tau] := k;

tau := tau + 1;

stek [tau] := u;

if nr [u] < low [k] then low [k] := nr [u];

end

p := false;

end

end

while not p and not t do

begin

fst [k] := fst [k] + 1;

if fst [k] <= lst [k + 1] then

begin

if k = 1 then

pirma := true;

p := true;

end

else

if prec [k] = k then

t := true

else

begin

s := k;

k := prec [k];

if low [s] < low [k] then low[k]:=low[s];

if ((k <> 1) and (low [s] >= nr [k])) or ((k = 1) and pirma) then

begin

st[k] := 1;

writeln ('s¹l. taškas = ', k : 3);

end

if low [s] >= nr [k] then

begin

writeln ('blokas');

while (stek [tau] <> s) or (stek [tau – 1] <> k) do

begin

write (stek [tau] : 3,' - ',

stek [tau – 1] : 3);

tau := tau – 2;

writeln

end

write (stek [tau] : 3,' – ',

stek [tau – 1] : 3);

tau := tau – 2;

writeln

end

end

end

end

end;

Srautai tinkluose ir giminingi uždaviniai

Pagrindinës s¹vokos

Aptarsime kelis praktiniø uždaviniø pavyzdžius.

Pirmas pavyzdys. Tarkime, kad turime tinkl¹ automobiliniø keliø, kuriais galima nuvykti iš punkto A á punkt¹ B. Keliai gali kirstis tarpiniuose punktuose. Kiekvienai kelio atkarpai yra žinomas maksimalus skaièius automobiliø, kuriuos ši kelio atkarpa gali praleisti per laiko vienet¹ (kelio pralaidumas). Koks didžiausias skaièius automobiliø per laiko vienet¹ gali nuvažiuoti iš punkto A á punkt¹ B? Šis automobiliø skaièius vadinamas nagrinëjamo kelio tinklo automobiliø srauto dydžiu. Paparastai mus domina ne vien tik koks didžiausias automobiliø skaièius gali nuvykti iš A á B, bet ir kiekvieno kelio ruožo srautas, t.y. koks skaièius automobiliø vyksta šiuo kelio ruožu.

Aišku, kad galimas ir kitas klausimas: kiek ir kokiø keliø pralaidumus reikia padidinti, kad maksimalus automobiliø srautas per šá keliø tinkl¹ padidëtø nurodytu dydžiu?

Antras pavyzdys. Tarkime, kad naftos verslovë A naftotiekiø tinklu yra sujungta su perdirbimo ámone B. Taip pat žinome kiekvieno naftotiekio tarpo maksimalø pralaidum¹ – debit¹ (naftos kieká per laiko vienet¹). Koká kieká naftos per laiko vienet¹ galime perpumpuoti šiuo tinklu?

Treèias pavyzdys. Turime informacijos perdavimo tinkl¹. Žinomas kiekvienos ryšio linijos pralaidumas. Koká didžiausi¹ informacijos kieká šiuo tinklu galima perduoti iš punkto A á punkt¹ B?

Šie ir daugelis kitø praktiniø uždaviniø nagrinëjami srautø tinkluose teorijos metodais. Šiame paragrafe sprêsime pagrindiná šios teorijos uždaviná – maksimalaus srauto radimo uždaviná.

Apibrëžimas. Tinklas, tai pora , kur pirmasis poros elementas yra bet koks orientuotasis grafas, kuriame išskirtos dvi viršûnës s ir t, iš kuriø pirmoji viršûnë s, neturinti áeinanèiø lankø, vadinama šaltiniu, o antroji – t, neturinti išeinanèiø lankø, vadinama nuotakiu. Antrasis poros elementas C yra funkcija , kuri kiekvienam lankui priskiria neneigiam¹ realøjá skaièiø , kuris vadinamas lanko pralaidumu.

Apibrëžimas. Tarkime, kad duota funkcija . Tada funkcijos f divergencija viršûnëje v vadinamas dydis , apibrëžiamas formule:

(1)

Jei interpretuosime kaip sraut¹ iš viršûnës u á viršûnê v, tai skaièius parodo “srauto kieká”, kuris išeina iš viršûnës v. Šis skaièius gali bûti teigiamas (jei iš viršûnës v daugiau išeina negu áeina, t.y. viršûnë v yra papildomas šaltinis), neigiamas (jei á viršûnê v daugiau áeina negu išeina, t.y. srautas kaupiasi viršûnëje v) ir lygus nuliui.

Apibrëžimas. Funkcija vadinama srautu tinkle S, jeigu:

kiekvienam grafo G lankui galioja nelygybë

(2)

kiekvienos viršûnës v, išskyrus s ir t, divergencija lygi nuliui, t.y.

(3)

Skaièius vadinamas srauto dydžiu.

Pagal šá apibrëžim¹ nagrinëjame sraut¹, kuris nesikaupia ir neatsiranda nei vienoje tarpinëje grafo G viršûnëje (išskyrus viršûnes s ir t).

Toliau sprêsime maksimalaus srauto radimo uždaviná: rasime toki¹ funkcij¹ , kuri tenkintø (2) ir (3) apribojimus ir kuriai skaièius bûtø didžiausias. Aišku, kad funkcijos f reikšmës kiekvienam lankui apibrëš maksimalø sraut¹ per šá lank¹.

Maksimalaus srauto apskaièiavimo uždavinys yra tiesinio programavimo uždavinys, todël jam gali bûti taikomi tiesinio programavimo uždaviniø sprendimo metodai. Taèiau, ávertinant uždavinio specifik¹, yra sukurti žymiai efektyvesni šio uždavinio sprendimi metodai, kuriuos toliau ir nagrinësime.

Pjûvio apibrëžimas. Tinklo S pjûviu , kurá apibrëžia grafo G viršûniø tikrinis poaibis A, t.y. ir ir , vadiname grafo G tokiø lankø aibê, kad , o .

Kitaip tariant,

Aišku, kad bet kokiam tinklo S srautui f pjûvio srautas yra lygus pjûvá sudaranèiø lankø sumai, t.y.

Lema. Jei , o , tai bet kokiam srautui f iš s á t galioja lygybë

(4)

Árodymas. (4) lygybës teisingumas išplaukia iš (1) ir (3) formuliø.

Susumuokime (3) lygtis visoms grafo viršûnëms . Ši¹ sum¹ sudarys nariai , turintys pliuso arba minuso ženkl¹.

Jei abi viršûnës u ir v priklauso aibei A, tai turës pliuso ženkl¹ lygtyje ir minuso ženkl¹ lygtyje , ir šio dëmens neturës nei viena lygtis , kai ir . Vadinasi, sumuodami šiuos dëmenis, gausime 0.

Jei , o , tai kiekvienas narys sumoje pasikartos vienintelá kart¹ su ženklu plius lygtyje , ir visumoje gausime . Analogiški dëmenys , kai , o , duos (4) formulës nará . Kita vertus, nagrinëjama suma lygi , nes visiems .

Išvada. .

Imdami iš (4) formulës gausime:

Gauta tapatybë árodo intuityviai aiškø fakt¹: nuotakio srautas yra lygus šaltinio srautui.

Árodyta lema sako tai, kad tinklo srautas gali bûti matuojamas bet kuriame pjûvyje, kuris atskiria s ir t viršûnes.

Pavyzdys. 1 pav. pavaizduotas tinklas. Skaièiai prie lankø apibrëžia sraut¹ f. Lankø pralaidum¹ žymi skliausteliuose parašyti skaièiai. Panagrinëkime pjûvius, kuriuos nusako viršûniø ir poaibiai.

1 pav. Srautas tinkle: 1-osios lemos ir didinanèiosios grandinës iliustracija. Punktyru išskirta didinanèioji grandinë.

Aibës A viršûniø divergencija yra:

Šias lygtis sudëjê, gausime:

Sutraukê panašius narius, gausime:

Ástatê srauto reikšmes, gausime:

Pjûviui, kurá nusako poaibis , analogiškai gausime:

Ástatê srauto reikšmes, gausime:

Nesunku pastebëti, kad šie pavyzdžiai iliustruoja lemos árodym¹ bei lemos išvados teisingum¹.

Apibrëžimas. Pjûvio, kurá nusako viršûniø poaibis A, t.y. pjûvio pralaidumas yra skaièius, apibrëžiamas formule

Kitaip tariant, pjûvio pralaidumas yra lygus pjûvá sudaranèiø lankø pralaidumø sumai.

Apibrëžimas. Minimaliu pjûviu vadinsime pjûvá , kurio pralaidumas yra mažiausias tarp visø galimø pjûviø, atskirianèiø s ir t viršûnes.

Vienas iš pagrindiniø srautø tinkluose rezultatø yra nusakomas Fordo ir Falkersono teorema.

Teorema (Fordas (Ford L.R.) ir Falkersonas (Fulkerson D.R.) 1962). Bet kokio srauto iš viršûnës s á viršûnê t dydis neviršija minimalaus pjûvio, skirianèio šias viršûnes, pralaidumo; be to egzistuoja toks srautas, kurio dydis yra lygus tokio minimalaus pjûvio pralaidumui.

Árodymas. Tarkime, kad – minimalus pjûvis. Remiantis lema, bet kokiam srautui f gausime:

Árodymas, kad maksimalaus srauto dydis yra lygus minimalaus pjûvio pralaidumui, yra sudëtingesnis faktas. Šis árodymas išplauks iš maksimalaus srauto konstravimo algoritmo, kuris nagrinëjamas kitame paragrafe.

Maksimalaus srauto konstravimo algoritmas

Visi žinomi maksimalaus srauto konstravimo algoritmai pagrásti nuosekliu srauto didinimo metodu, o visø srauto didinimo metodø pagrind¹ sudaro didinanèiøjø grandiniø teorija.

Apibrëžimas. Tinklo S lankas e iš viršûnës u á viršûnê v vadinamas leistinuoju lanku srauto f atžvilgiu, jeigu

a)    ir

arba

b)   ir .

Jei galioja s¹lyga a), tai toká lank¹ vadinsime suderintuoju (soglasovannaja duga). Jei galioja s¹lyga b), tai toká lank¹ vadinsime nesuderintuoju (nesoglasovannaja duga).

Apibrëžimas. Ilgio l didinanèioji grandinë iš viršûnës s á viršûnê t srauto f atžvilgiu yra seka, sudaryta iš besikeièianèia tvarka surašytø (poromis skirtingø) viršûniø ir lankø:

(5)

Èia , ir kiekvienam lankas srauto f atžvilgiu yra leistinasis lankas iš viršûnës á viršûnê .

Pavyzdžiui, 1 pav. pavaizduoto tinklo ir srauto per já atžvilgiu, grandinë:

(6)

yra didinanèioji grandinë, kurios ilgis yra 6.

Žinodami (5) pavidalo didinanèi¹j¹ grandinê, sraut¹ f galime padidinti dydžiu

èia

Tam tikslui (pavyzdžiui, žiûrint á 1 pav.) reikia didinanèiosios grandinës kiekvieno suderintojo lanko sraut¹ padidinti dydžiu d, o kiekvieno nesuderintojo lanko sraut¹ sumažinti tuo paèiu dydžiu d, t.y.

Aišku, kad taip apskaièiuota funkcija yra srautas, nes , ; ir , .

Iš tikro, jei nepriklauso didinanèiajai grandinei, tai .

Tarkime, kad priklauso didinanèiajai grandinei. Tada (žr. 2 pav.):

jei ir yra suderintieji lankai, tai srautas, átekantis á viršûnê ir ištekantis iš jos padidëja tuo paèiu dydžiu d ; tuo bûdu (žr. 2 a) pav.),

jei ir yra nesuderintieji lankai, tai srautas, átekantis ir ištekantis iš viršûnës sumažëja tuo paèiu dydžiu d ; vadinasi (žr. 2 b) pav.),

jei yra suderintasis lankas, o – nesuderintasis lankas, tai srautas áeinanèiu á viršûnê lanku padidëja dydžiu d, o áeinanèiu lanku sumažëja tuo paèiu dydžiu; vadinasi (žr. 2 c) pav.),

jei yra nesuderintasis lankas, o – suderintasis lankas, tai išeinanèiu iš viršûnës lanku srautas sumažëja dydžiu d, o išeinanèiu iš viršûnës lanku padidëja tuo paèiu dydžiu; tuo bûdu (žr. 2 d) pav.).

2 pav. Didinanèiosios grandinës lankø, incidentiškø viršûnei v_i, srauto perskaièiavimas

Srauto dydis padidëja dëmeniu d

Pavyzdys. Panagrinëkime tinkl¹ su srautu f, kuris pavaizduotas 1 pav. (6) seka yra šio tinklo ir srauto per já atžvilgiu didinanèioji grandinë. Šiai grandinei

Vadinasi, 2. 17.1 pav. pavaizduoto tinklo sraut¹ galima padidinti dydžiu 1, t.y. nuo 10 iki 11. 3.17.3 pav. pavaizduotas tas pats 1 pav. tinklas ir perskaièiuotas srautas.

3 pav. Tinklo, pavaizduoto 1 pav., srautas po modifikacijos

Árodysime teorem¹, kuri pagrindžia maksimalaus srauto apskaièiavimo, naudojant didinaèiasias grandines, metod¹.

Teorema. Žemiau pateiktos trys s¹lygos yra ekvivalenèios:

srautas iš s á t maksimalus,

neegzistuoja didinanèios grandinës srauto f atžvilgiu,

egzistuoja pjûvis, kurá nusako toks viršûniø poaibis , skiriantis viršûnes s ir t (, ), kad .

Árodymas Þ 2). Jei srautas maksimalus, tai aišku, kad neegzistuoja didinanèiosios grandinës šio srauto atžvilgiu, nes, priešingu atveju, esant didinanèiai grandinei, sraut¹ bûtø galima padidinti.

Þ 3). Tarkime, kad srautui f neegzistuoja didinanèiosios grandinës. Apibrëžkime viršûniø aibê , kuri¹ sudaro viršûnës tokios grandinës

kad , , ir – leistinasis lankas iš viršûnës á viršûnê , . Aišku, kad , o , nes šiuo atveju egzistuotø didinanèioji grandinë srauto f atžvilgiu. Panagrinëkime pjûvá . Iš aibës A ir suderintojo lanko apibrëžimo išplaukia, kad kiekvienam pjûvio lankui turi galioti lygybë . Vadinasi, .

Analogiškai, remiantis aibës A ir nesuderintojo lanko apibrëžimu, gausime, kad . Remiantis aukšèiau árodyta lema, gausime

Þ 1) išplaukia iš to fakto, kad srauto dydis nevišija .

Pavyzdys. Nesunku patikrinti, kad srautas 3 pav. yra maksimalus. “Prisotintas” pjûvis , atsirandantis teoremos árodyme, yra .

Remiantis pateiktais teoriniais samprotavimais, galima sudaryti paprast¹ maksimalaus srauto apskaièiavimo algoritm¹: pradëdami nuo bet kokio, pavyzdžiui, nulinio srauto (, ), ieškosime didinanèiosios grandinës ir, jei tokia grandinë egzistuoja, sraut¹ didinsime; priešingu atveju srautas f yra maksimalus.

Taèiau èia iškyla klausimas, ar algoritmo žingsniø skaièius yra baigtinis. Fordas ir Falkersonas[8] davë neigiam¹ atsakym¹. 1962 m. jie pateikë pavyzdá tokio tinklo, kuriame galima taip parinkinëti didinanèiasias grandines, kad procesas niekada nepasibaigtø. Be to, srauto dydis vis¹ laik¹ bus ketvirtadaliu mažesnis už maksimalaus srauto dydá.

Taèiau 1972 m. Edmondsas (Edmonds J.) ir Karpas (Karp R.M.)[9] árodë, kad, jei kiekviename žingsnyje sraut¹ didinsime trumpiausios didinanèiosios grandinës atžvilgiu, tai maksimalus srautas bus sukonstruotas, panaudojant ne daugiau kaip grandiniø (èia , ). Rasti trumpiausi¹ didinanèi¹j¹ grandinê patogu, naudojant paiešk¹ platyn (žr. 2.9 paragraf¹). Ávertinant tai, kad trumpiausios grandinës konstravimo algoritmo sudëtingumas yra , galime ávertinti viso maksimalaus srauto apskaièiavimo algoritmo sudëtingum¹, – .

Èia nenagrinësime šio algoritmo detaliø, kadangi toliau panagrinësime efektyvesná 1970 m. Dinico (Dinic E.A.)[10] pasiûlyt¹ maksimalaus srauto apskaièiavimo algoritm¹, kurio sudëtingumas yra .

Dinico metodas susideda iš faziø. Jo efektyvumas pagrástas tuo, kad, nepriklausomai nuo tinklo lankø pralaidumo, faziø skaièius niekada neviršija , èia n – tinklo viršûniø skaièius [Lip88].

Panagrinëkime k-osios fazës veiksmus. Tarkime, kad fazës pradžioje turime tinkl¹ G ir jame apibrëžt¹ sraut¹ f. Toká tinkl¹ žymësime simboliu G_f.

Remdamiesi tinklu G_f, sudarome pagalbiná tinkl¹, kuris neturi kontûrø (ciklø) ir kurio struktûra vaizduoja visas trumpiausias didinanèiasias tinklo G_f grandines. Pažymëkime šá tinkl¹ simboliu S_f. Tinklas S_f konstruojamas paieškos platyn grafe G_f metodu, ir á tinkl¹ S_f átraukiami tinklo G_f srauto f atžvilgiu leistinieji lankai. Tuo bûdu á tinkl¹ S_f áeina šaltinis s, nuotakis t ir grafo G_f leistinieji lankai , èia viršûnë u nutolusi nuo šaltinio s atstumu d, o viršûnë v – atstumu d+1, , o l yra tinklo S_f ilgis, t.y. atstumas nuo s iki t grafe G_f. Šio lanko pralaidum¹ žymësime ir apibrëšime formule

Sudarius pagalbiná tinkl¹ S_f, toliau jame apskaièiuojamas pseudomaksimalus srautas.

Apibrëžimas. Ilgio l tinklo S_f pseudomaksimalus srautas – tai toks tinklo S_f srautas f ^*, prie kurio tinkle S_f neegzistuoja nei viena l ilgio didinanèioji grandinë; kitaip tariant, bet kokiam tinklo S_f iš viršûnës s á viršûnê t keliui

egzistuoja toks lankas , kad

Po to pseudomaksimalus srautas “perkeliamas” á pagrindiná tinkl¹ G_f : srautas sumuojamas su G_f srautu ; jei ši suma iššaukia lanko “persipildym¹”, t.y. suma viršija , tai šis srauto “perteklius” kompensuojamas sumažinant sraut¹ . Tuo bûdu viršûnës u divergencija padidëja dydžiu , o viršûnës v divergencija tuo paèiu dydžiu sumažëja. Nesunku ásitikinti, kad tokiø visø lankø srautø modifikacija apibrëžia nauj¹ tinklo G_f sraut¹ , kurio dydis . Šiuo veiksmu ir baigiama k-oji fazë.

Maksimalaus srauto konstravimas baigiamas, kai iš tinklo G_f nebegalima sukonstruoti pagalbinio tinklo S_f.

Kaip bus matyti iš toliau pateiktø tinklo S_f bei jo pseudomaksimalaus srauto apskaièiavimo algoritmø, vienos fazës sudëtingumas yra . Kadangi, kaip parodyta literatûroje [Lip88], faziø skaièius neviršija , tai Dinico metodo sudëtingumas yra O(n³).

Pavyzdys. Panagrinëkime tinkl¹, pavaizduot¹ 4 a) paveiksle. Prie lanko parašytas skaièius reiškia lanko maksimalø sraut¹, o skaièius skliausteliuose rodo lanko pralaidum¹.

4 pav. Maksimalaus srauto ieškojimas Dinico metodu

Pradëjê nuo tinklo nulinio srauto , pirmiausia apskaièiuojame pagalbiná be kontûrø tinkl¹ S_f0 (žr. 4 b) pav.). Po to rast¹já pseudomaksimalø sraut¹ perkeliame á tinkl¹ , gaudami sraut¹ , t.y. tinkl¹ G_f1.

Toliau konstruojame pagalbiná tinkl¹ S_f1 (žr. 4 c) pav.), ir rast¹já pseudomaksimalø sraut¹ perkeliame á tinkl¹ G_f1. Gauname sraut¹ (tinkl¹ G_f2).

Paskutinëje fazëje konstruojame pagalbiná tinkl¹ S_f2 (žr. 4 d) pav.). Kai šio tinklo pseudomaksimalø sraut¹ perkeliame á G_f2, gauname sraut¹ f, pavaizduot¹ 4 a) pav., kuris yra maksimalus tinklo G srautas, kadangi (žr. 1 paragrafo Fordo ir Falkersono teorem¹).

4 c) pav. gerai iliustruoja t¹ fakt¹, kad pseudomaksomalus srautas nebûtinai yra maksimalus srautas. Iš tikro, šiame paveikslëlyje pavaizduot¹ pseaudomaksimalø sraut¹ galime padidinti panaudojê ilgio 5 didinanèi¹j¹ grandinê:

Taip pat pažymësime, kad tinklo S_f2 (žr. 4 d) pav.) lankas atsirado iš pagrindinio tinklo G dviejø priešpriešais nukreiptø lankø.

Aptarkime pagalbinio tinklo ir jo pseudomaksimalaus srauto apskaièiavimo algoritmus.

Pagalbinio tinklo S_f apaskaièiavimo algoritmas

Tarkime, kad pradinio tinklo grafas nusakytas gretimumo struktûromis ir , .

– tai aibë viršûniø, á kurias iš viršûnës v išeina lankai.

– tai aibë viršûniø, iš kuriø á viršûnê v áeina lankai.

Lankø pralaidum¹ žymësime masyvu , , o faktin¹já sraut¹ f – masyvu , . Tokia pralaidumo bei srauto vaizdavimo struktûra atminties požiûriu nëra racionali, taèiau prie šios struktûros algoritmas tampa vaizdesnis.

Kintamieji, vaizduojantys pagalbiná tinkl¹ , yra analogiški pradinio tinklo kintamiesiems ir jie žymimi tais paèiais vardais, pridedant prie jø pradinê raidê S. Tuo bûdu, SV žymi tinklo viršûniø aibê; ir , , žymi gretimumo struktûr¹; Sc ir Sf atitinkamai žymi lankø pralaidumus ir sraut¹. Masyvo d elementas , , žymi tinklo viršûnës v nuotolá nuo šaltinio s.

Kaip buvo minëta aukšèiau, tinklas konstruojamas paieškos platyn iš viršûnës s tinkle metodu. Paieškos platyn procese aplankytos viršûnës v talpinamos á eilê. Kiekviena iš eilës paimta viršûnë u nagrinëjama du kartus: pirm¹ kart¹ – ieškomi iš jos išeinantys leistinieji suderintieji lankai ; antr¹ kart¹ – ieškomi leistinieji nesuderintieji lankai .

Jei tinkle vienu metu lankas yra suderintasis ir nesuderintasis leistinasis lankas, t.y. – leistinasis suderintasis lankas, o – leistinasis nesuderintasis lankas, tai á tinkl¹ átraukto lanko pralaidumas yra lygus šiø lankø pralaidumø srauto f atžvilgiu sumai.

procedure psa

begin

for u I V do

begin

d [u] := ¥

SN [u] :=Æ; SPN [u] := Æ

for v I V do Sc [u, v] := 0;

for v I V do Sf [u, v] := 0;

end

Eil Æ; SV := Æ; d [s] := 0;

Eilë s

while Eil ¹ Æ do

begin

u Eilë

SV := SV È

for v I N [u] do

if ( d [u] < d [v] £ d [t] ) and (f [u, v] < c [u, v] ) then

begin

if d [v] = ¥ then Eil v

d [v] := d [u] + 1;

SN [u] := SN [u] È

SPN [v] := SPN [v] È

Sc [u, v] := c [u, v] – f [u, v];

end

for v I PN [u] do

if ( d [u] < d [v] £ d [t] ) and (f [v, u] > 0 ) then

begin

if d [v] = ¥ then Eil v

d [v] := d [u] + 1;

if Sc [u, v] = 0 then

begin

SN [u] := SN [u] È

SPN [v] := SPN [v] È

end

Sc [u, v] := Sc [u, v] + f [v, u];

end

end

end

Tarkime, po procedûros psa ávykdymo . Jei , tai reiškia, kad paieškos platyn metu nuotakio viršûnë t nebuvo pasiekta. Vadinasi, tinkle nuo s iki t nëra didinanèiosios grandinës. Tada, remiantis 2 paragrafo teorema, galime teigti, kad srautas f yra maksimalus.

Jei , tai trumpiausios didinanèiosios grandinës iš s á t ilgis yra l. Be to, visø keliø nuo s iki t ilgiai tinkle yra lygûs l, ir jie žymi l ilgio didinanèiasias grandines tinkle . Reikia pažymëti, kad, pasiekus nuotaká t, tampa lygus , ir viršûnës v, kurioms , procedûroje psa nenagrinëjamos, kadangi nei viena tokia viršûnë negali priklausyti l ilgio keliui, jungianèiam s ir t.

Nesunku ávertinti procedûros psa sudëtingum¹. Kiekviena viršûnë v á eilê talpinama ir šalinama ne daugiau kaip vien¹ kart¹. Kiekvienas viršûnei v incidentiškas lankas analizuojamas vien¹ kart¹, be to, analizës veiksmø skaièius apribotas konstanta. Vadinasi, bendras veiksmø skaièius be inicializacijos yra . Inicializacijos veiksmø skaièius yra . Tuo bûdu, procedûros psa sudëtingumas yra .

Belieka aptarti tinklo pseudomaksimalaus srauto efektyvaus apskaièiavimo algoritm¹. Žemiau pateiktas Malchotros, Kumaro ir Mahešvario (Malhotra V.M., Kumar P.M., Makeshvari S.N. An algorithm for finding maximum flows in networks. Information Processing Lett. 1978, 7, s. 277 – 278) pseudomaksimalaus srauto apskaièiavimo algoritm¹, kurio sudëtingumas yra .

Tinklo S_f pseudomaksimalaus srauto apskaièiavimo procedûra maxpsa

Šio algoritmo aprašymui áveskime tinklo viršûnës potencialo s¹vok¹.

Apibrëžimas. Tinklo viršûnës v potencialas yra maksimalus srauto kiekis, kurá galima praleisti per viršûnê v. Viršûnës v potencialas apibrëžiamas formule

Žemiau pateikta maxpsa procedûra pirmiausia apskaièiuoja pagalbinio tinklo visø viršûniø potencialus ir nulinio potencialo viršûnes patalpina á stek¹ STEK. Aišku, kad nulinio potencialo viršûnes drauge su joms incidentiškais lankais galima pašalinti iš tinklo , ir šis pašalinimas neturës átakos jokiam tinklo srautui. Tokiø viršûniø, o tikslaiu joms incidentiškø lankø pašalinimas gali paveikti kitø tinklo viršûniø potencialus, ir jie gali tapti lygûs nuliui. Jei taip atsitinka, tai naujos nulinio potencialo viršûnës šalinamos iš tinklo.

Jei, pasibaigus nulinio potencialo viršûniø šalinimo procesui, tinklas neturi nenulinio potencialo viršûniø, tai tinklo pseudomaksimalus srautas surastas. Priešingu atveju randame mažiausio potencialo viršûnê r ir jos potencial¹ p. Tada iš viršûnës r á viršûnê t ir iš viršûnës s á viršûnê r konstruojame p dydžio sraut¹. Tuo bûdu apskaièiuojamas p dydžio srautas iš šaltinio s á nuotaká t. Šis srautas naudos tik leistinuosius suderintuosius lankus.

Aptarsime, kaip konstruojamas p dydžio srautas iš viršûnës r á viršûnê t. Srauto iš viršûnës s á viršûnê r konstravimas yra analogiškas.

Kaip buvo minëta, p dydžio srautas iš viršûnës r á viršûnê t naudos tik suderintuosius leistinuosius lankus, ir já patogiausia konstruoti naudojant paiešk¹ platyn iš viršûnës r. Ásivaizduokime, kad viršûnëje r patalpintas krovinys , ir mes norime “perkelti” šá kroviná á viršûnê t. Kiekviena paieškos platyn metu aplankyta viršûnë v “perkelia” kroviná á viršûnes u, á kurias eina lankai iš viršûnës v. Be to, á viršûnê u “perkeliamo” krovinio dalis yra lygi lanko pralaidumui, t.y. . Aišku, kad tokie lankai gali bûti šalinami iš tinklo. Lankø šalinimas iššaukia viršûniø potencialø perskaièiavim¹, ir, jei viršûnës v potencialas tampa lygus nuliui, tai viršûnë v talpinama á stek¹ STEK.

Tuo bûdu, krovinys iš viršûnës r, kuri nuo šaltinio s nutolusi atstumu d, pirmiausia bus “perkeltas” á viršûnes, nutolusias nuo šaltinio s atstumu , po to, iš šiø viršûniø, á viršûnes, nutolusias nuo šaltinio s atstumu ir t.t. iki visas krovinys bus “perkeltas” á viršûnê t. Kadangi p yra mažiausias viršûnës potencialas, tai toks krovinio “perkëlimas” visada yra galimas.

Kaip minëjome, srautas iš s á r konstruojamas analogiškai.

p dydžio srauto iš viršûnës s á t konstravimu baigiasi pagrindinio ciklo veiksmai, ir, kaip buvo minëta aukšèiau, pagrindinis ciklas bus kartojamas, kol tinklas turës nenulinio potencialo viršûniø.

procedure maxpsa

begin

STEK Æ

for v I SV do

begin

Pin [v] := 0; Pout [v] := 0;

if v = s then Pin [v] := ¥

else

for uI SPN [v] do

Pin [v] := Pin [v] +Sc [u, v];

if v = t then Pout [v] := ¥

else

for uI SN [v] do

Pout [v] := Pout [v] + Sc [v, u];

P [v] := min (Pin [v], Pout [v]);

if P [v] = 0 then STEK v

end

for v I SV do Q [v] := 0;

XN := SV;

while XN ¹ Æ do

begin

while STEK ¹ Æ do

begin

v STEK; XN := XN

for u I SPN [v] do

begin

Pout [u] := Pout [u] – (Sc [u, v] – Sf [u, v]);

SN [u] := SN [u] ;

SPN [v] := SPN [v] ;

if P [u] ¹ 0 then

begin

P [u] := min (Pin [u], Pout [u]);

if P [u] = 0 then STEK u

end

end

for u I SN [v] do

begin

Pin [u] := Pin [u] – (Sc [v, u] –Sf [v, u]);

SPN [u] := SPN [u] ;

SN [v] := SN [v] ;

if P [u] ¹ 0 then

begin

P [u] := min (Pin [u], Pout [u]);

if P [u] = 0 then STEK u

end

end

end

if XN ¹ Æ then

begin

p ¥

for v I XN do

if P [v] < p then

begin

r :=v;

p := P [r];

end

Eilë Æ Eilë r; Q [r] := p;

repeat

v Eilë

Pin [v] := Pin [v] – Q [v];

Pout [v] := Pout [v] – Q [v];

P [v] := P [v] – Q [v];

if P [v] = 0 then STEK v

if v = t then Q [v] := p

else

begin

u := pirmoji aibës SN [v] viršûnë

while Q [v] > 0 do

begin

if Q [u]  = 0 then Eilë u

delta := min (Q [v], Sc [v, u] – Sf [v, u]);

Sf [v, u] := Sf [v, u] + delta;

Q [v] := Q [v] – delta;

Q [u] := Q [u] + delta;

if Sf [v, u] = Sc [v, u] then

begin

SN [v] := SN [v] ;

SPN [u] := SPN [u] ;

end

if Q [v] > 0 then

u := po viršûnës u einanti kita aibës SN [v] viršûnë

end

end

until v = t;

Eilë Æ Eilë r; Q [r] := p;

repeat

v Eilë

if v ¹ r then

begin

Pin [v] := Pin [v] – Q [v];

Pout [v] := Pout [v] – Q [v];

P [v] := P [v] – Q [v];

if P [v] = 0 then STEK v

end

if v = s then Q [v] := 0

else

begin

u := pirmoji aibës SPN [v] viršûnë

while Q [v] > 0 do

begin

if Q [u] = 0 then Eilë u

delta := min (Q [v], Sc [u, v] – Sf [u, v]);

Sf [u, v] := Sf [u, v] + delta;

Q [v] := Q [v] – delta;

Q [u] := Q [u] + delta;

if Sf [u, v] = Sc [u, v] then

begin

SPN [v] := SPN [v] ;

SN [u] := SN [u] ;

end

if Q [v] > 0 then

u := po viršûnës u einanti kita aibës
SPN [v] viršûnë

end

end

until v = s;

end

end

end

Aptarkime procedûros maxpsa sudëtingum¹. Pradinis viršûniø potencialø apskaièiavimas reikalauja veiksmø, kadangi kiekvienas grafo lankas analizuojamas ne daugiau kaip du kartus: apskaièiuojant Pout [v] ir Pin [v].

Pagrindinio ciklo nulinio potencialo viršûniø šalinimo sudëtingumas taip pat yra , kadangi kiekviena viršûnë á stek¹ STEK talpinama vien¹ kart¹, o šalinant viršûnê iš steko pašalinamos visos jai incidentiškos briaunos, tuo bûdu kiekvienas lankas šalinamas ne daugiau kaip vien¹ kart¹.

Kiekviena pagrindinio ciklo iteracija iššaukia ne mažiau kaip vienos nulinio potencialo viršûnës atsiradim¹ (viršûnës r potencialas visada bus lygus nuliui). Vadinasi, pagrindinio ciklo pasikartojimø skaièius neviršija n.

Pagrindiniame cikle, be minëtø nulinio potencialo viršûniø šalinimo veiksmø, naudojant paiešk¹ platyn konstruojamas p dydžio srautas iš r á t ir iš s á r. Šiø daliø sudëtingumas yra lygus lankø analizavimo skaièiaus eilei.

Lanko analizë gali bûti “naikinamoji”, kai srautas per lank¹ yra lygus to lanko pralaidumui, ir toks lankas šalinamas iš tinklo.

Lanko analizë gali bûti “nenaikinamoji”, kai srauto per lank¹ dydis yra mažesnis už to lanko pralaidum¹. Toks lankas iš tinklo nešalinamas ir gali bûti analizuojamas kartojant pagrindiná cikl¹.

Aišku, kad per visus pagrindinio ciklo pasikartojimus “naikinamuoju” bûdu analizuojame lankø, o kiekviename pagrindiniame cikle “nenaikinamuoju” bûdu analizuojame ne daugiau kaip n lankø (po vien¹ kiekvienai aplankytai viršûnei). Vadinasi, per visus pagrindinio ciklo pasikartojimus “nenaikinamuoju” bûdu bus analizuota ne daugiau kaip n² lankø. Tuo bûdu, bendras pagrindinio ciklo veiksmø skaièius yra , t.y. .

Iš viso nagrinëjimo darome išvad¹, kad procedûros maxpsa sudëtingumas yra .

Dabar aprašytas psa ir maxpsa procedûras galima sukomponuoti á vien¹ bendr¹ maksimalaus srauto apskaièiavimo algoritm¹.

Maksimalaus srauto apskaièiavimo algoritmas

Duota: tinklas, nusakytas gretimumo struktûromis ir , ; laukø pralaidumu , ; šaltiniu s ir nuotakiu t.

Rezultatas:  maksimalus srautas , .

begin

for u I V do

for v I V do f [u, v] :=0; .

repeat

psa

if d [t] ¹ ¥ then

begin

maxpsa

for u I SV do

for v I SV do

begin

f [u, v] := f [u, v] + Sf [u, v];

if f [u, v] > c [u, v] then

begin

f [v, u] := f [v, u] – (f [u, v] – c [u, v]);

f [u, v] := c [u, v];

end

end

end

until d [t] = ¥

end

Išvada. Iš procedûrø psa ir maxpsa sudëtingumo analizës bei to, kad faziø skaièius neviršija išplaukia, kad pateikto maksimalaus srauto algoritmo sudëtingumas yra . Tuo paèiu šiø algoritmø analizë parodë, kad bet kokiam tinklui egzistuoja maksimaus srautas. O tai ir yra Fordo ir Falkersono teoremos pilno árodymo trûkstama grandis.

Šá paragraf¹ baigsime akivaizdžia, bet svarbia pateikta maksimalaus srauto radimo algoritmo savybe.

Teorema. Jeigu tinklo visø lankø pralaidumai yra sveikieji skaièiai, tai maksimalus srautas, apskaièiuotas pagal pateikt¹ algoritm¹, yra sveikaskaitinis, t.y. yra sveikasis skaièius kiekvienam tinklo lankui .

Maksimalaus suporavimo uždavinys dvidaliame grafe

Apibrëžimas. Suporavimas neorientuotajame grafe – tai toks grafo G briaunø poaibis , kad bet kokios dvi poaibio M briaunos tarpusavyje nëra gretimos, t.y. bet kokios dvi poaibio M briaunos nëra incidentiškos vienai ir tai paèiai viršûnei.

Jei briauna , tai sakome, kad M suporuoja u ir v viršûnes.

Jei viršûnë v nëra incidentiška nei vienai poaibio M briaunai, tai viršûnë v vadinama laisv¹ja viršûne, priešingu atveju – suporuot¹ja.

Maksimalaus suporavimo neorientuotame grafe uždavinys yra plaèiai paplitês, ir yra žinomi efektyvûs šio uždavinio sprendimo algoritmai. Visi jie pagrásti alternuojanèiø grandiniø teorija (teorija èeredujušèichsia cepei).

Tarkim, M – grafo G suporavimas.

Apibrëžimas. Grafo G grandinë, kuri¹ sudaro biaunos, pakaitomis nepriklausanèios ir priklausanèios poaibiui M, vadinama suporavimo M atžvilgiu alternuojanèia grandine.

Grandinë, kurios ilgis lygus 1, pagal apibrëžim¹ taip pat yra alternuojanti.

Alternuojanèios grandinës briaunos, priklausanèios suporavimui M, vadinamos tamsiomis briaunomis, o nepriklausanèios M – šviesiomis briaunomis.

Pavyzdys. Panagrinëkime 5 pav. pavaizduot¹ graf¹.

5 pav. Suporavimo uždavinys

Aibë yra suporavimas grafe G; grandinë yra suporavimo M atžvilgiu alternuojanti grandinë; , – tamsiosios grandinës P briaunos; , , – šviesiosios grandinës P briaunos; aibës ir – atitinkamai suporuotøjø ir laisvøjø viršûniø aibës.

Aišku, kag jei grafe G suporavimo M atžvilgiu egzistuoja grandinë, jungianti dvi laisv¹sias viršûnes, tai grafe G galima sukonstruoti suporavim¹, turintá didesná briaunø skaièiø nei M. Aišku, kad tokios alternuojanèios grandinës šviesiøjø briaunø skaièius yra vienetu didesnis nei tamsiøjø. Pašalinê iš M visas tamsiasias grandinës briaunas, ir á M ávedê visas šviesiasias tos grandinës briaunas, gausime suporavim¹, kuriame briaunø skaièius bus vienetu didesnis nei M. Dël tos priežasties alternuojanti grandinë, jungianti dvi laisvasias viršûnes, vadinama didinanèiaja grandine.

Teorema (K.Beržas). Neorientuotojo grafo G suporavimas M yra didžiausias tada ir tiktai tada, kai šiame grafe suporavimo M atžvilgiu nëra didinanèiosios grandinës.

Šiai teoremai iliustruoti panagrinëkime aukšèiau 5 pav. pateikt¹ graf¹. Imkime suporavim¹ ir didinanèi¹j¹ grandinê . Dabar galima sudaryti didesná suporavim¹ .

Suporavimas taip pat nëra didžiausias, nes šio suporavimo atžvilgiu egzistuoja grandinë .

Gausime suporavim¹ , kuris yra didžiausias, nes jo atžvilgiu grafe nëra didinanèiosios grandinës.

Tuo bûdu, Beržo teorema nusako toki¹ didžiausio suporavimo radimo strategij¹.

Randame bet koká pradiná suporavim¹ M.

Pavyzdžiui, pradinis suporavimas gali bûti bûti kuri grafo briauna.

Didesnio pradinio suporavimo galima ieškoti, naudojant “godaus” algoritmo strategij¹:

a)    rasti briaun¹, kurios incidentiškø viršûniø laipsniø suma yra mažiausia, ir átraukti ši¹ briaun¹ á suporavim¹;

b)   iš grafo pašalinti á suporavim¹ átraukt¹ briaun¹ drauge su jai gretimomis briaunomis.

Aišku, kad punktai a) ir b) bus kartojami tol, kol grafas G turës bent vien¹ briaun¹.

Nuosekliai konstruoti suporavimø sek¹ , kurioje gaunamas iš radus grafe G suporavimo atžvilgiu didinanèi¹j¹ grandinê. Kadangi , tai sekos ilgis bus nedidesnis nei . Todël norint rasti efektyvø šio uždavinio sprendimo algoritm¹, pagrást¹ išnagrinëta strategija, reikia sukonstruoti efektyvø didinanèiosios grandinës radimo algoritm¹. Nors tokie efektyvûs algoritmai egzistuoja, èia apsiribosime didžiausio suporavimo dvidaliame grafe nagrinëjimu.

Dažniausiai suporavimo uždavinys sprendžiamas dvidaliuose grafuose (žr. 2.2, 2.10 paragrafus). Tai klasikinis kombinatorikos uždavinys, žinomas “uždavinio apie sutuoktiniø poras” vardu.

Primename, kad -grafas yra dvidalis, jei jo viršûniø aibê V galima išskaidyti á du poaibius X ir Y taip, kad visø grafo G briaunø galai priklausytø skirtingiems poaibiams. Todël dvidalis grafas žymimas .

“Uždavinys apie sutuoktiniø poras” turi toki¹ interpretacij¹. Tarkime, X ir Y atitinkamai yra vaikinø ir merginø aibës. Sudarykime dvidalá graf¹ , èia , jei jaunuolis x draugauja su mergaite y. Tada kiekvienas suporavimas M atitinka aibê galimø sutuoktiniø porø, kiekviena iš kuriø sudaryta iš tarpusavyje draugaujanèiø jaunuolio ir merginos; be to, kiekvienas žmogus dalyvauja ne daugiau kaip vienoje poroje.

Pasirodo, kad maksimalaus suporavimo uždaviná dvidaliame grafe galima lengvai suvesti á maksimalaus srauto tinkle ieškojimo uždaviná.

Tarkime, – dvidalis grafas. Sudarykime tinkl¹ , kuris turëtø šaltiná s, nuotaká t ( ir ), viršûniø aibê , lankø aibê

ir kiekvieno lanko pralaidumas .

Pavyzdys. 6 a) pav. pavaizduotas dvidalis grafas H, o 6 b) pav. – jam atitinkantis tinklas .

6 pav. Dvidalis grafas H ir jam atitinkantis tinklas S(H). Suporavimas
M = ir jam atitinkantis srautas f_M.

Teorema. Kiekvienam grafo H k galios suporavimui , (, visiems ) egzistuoja vienintelis tinklo dydžio k sveikaskaitinis srautas apibrëžiamas taip:

visiems ,

visiems likusiems tinklo lankams e;

ir atvirkšèiai, kiekvienam tinklo dydžio k srautui f atitinka vienintelis grafo H suporavimas , apibrëžiamas taip:

6 pav. pavaizduotas suporavimas grafe H ir jam atitinkantis srautas tinkle .

Ši teorema ágalina maksimalaus srauto apskaièiavimo algoritmus, išnagrinëtus 6 paragrafe, panaudoti apskaièiuojant maksimalø suporavim¹ dvidaliame grafe.

Naudodami Dinico metod¹, maksimalø suporavim¹ galima apskaièiuoti atlikus veiksmø. Taèiau, atsižvelgiant á tinklo specifik¹, yra sukurti efektyvesni maksimalaus suporavimo apskaièiavimo algoritmai. Èia panagrinësime Hopkrofto ir Karpo algoritm¹, kurio sudëtingumas yra (žr. Hopcroft J., Karp R.M. An algorithm for maximum Matchings in bipartite graphs. SIAM J. Comput., 1973, 2, s. 225-231).

Šis algoritmas naudoja bendr¹ Dinico metodo schem¹. Vienok, dël tinklo specifikos galima sumažinti tiek faziø skaièiø, tiek ir sukurti efektyvesná pseudomaksimalaus srauto kiekvienoje fazëje apskaièiavimo algoritm¹.

Pirmiausia pašymësime, kad tinklo kiekvienos didinanèiosios grandinës ilgis yra nelyginis skaièius, ir, iš jos atmetus pirm¹j¹ ir paskutini¹j¹ grandis, ši grandinë bus alternuojanti, prasidedanti ir pasibaigianti šviesiaja briauna (leistinaisiais suderintaisiais lankais).

Apibrëžimas. Duotajam suporavimui M ilgio , iš X á Y grandinê :

kurioje visos viršûnës yra skirtingos, x₀ – laisvoji X aibës viršûnë, o y_k+1 – laisvoji Y aibës viršûnë, o kiekviena antroji briauna priklauso M, t.y.

vadinsime alternuojanèia grafo H grandine.

Aišku, kad alternuojanèi¹ grandinê galima nusakyti viršûniø seka. Ši seka vieninteliu bûdu apibrëžia srauto atžvilgiu didinanèi¹j¹ grandinê:

Be to, šios grandinës iššauktas srauto padidëjimas nusako suporavim¹, gaut¹ susumavus aibes A ir P moduliu 2: .

Pavyzdžiui, 7 a) pav. pavaizduotas dvidalis grafas ir suporavimas M; 7 b) pav. pavaizduota didinanèioji alternuojanèioji grandinëP, o 7 c) pav. pavaizduotas suporavimas .

7 pav. Suporavimo M padidinimas, panaudojant alternuojanèi¹ grandinê P

Aišku, kad ir dvidalio grafo H atveju yra teisinga Beržo teorema: grafo H suporavimas M yra didžiausias tada ir tiktai tada, kai šiame grafe suporavimo M atžvilgiu nëra didinanèiosios grandinës.

Aprašysime Hopkrofto ir Karpo algoritm¹. Šio algoritmo schema yra analogiška Dinico algoritmo schemai: kiekvienoje fazëje tinklui apskaièiuosime pagalbiná bekontûriná tinkl¹, jo pseudomaksimalø sraut¹ ir já “perkelsime” á pagrindiná tinkl¹. Kaip buvo minëta aukšèiau, dël tinklo specifikos šie algoritmai yra efektyvesni nei Dinico metode naudojamas analogiškas algoritmas, o faziø skaièius – mažesnis.

Pirmiausia aptarsime pagalbinio bekontûrinio tinklo apskaièiavimo algoritm¹ PGA.

Tarkime, yra dvidalis grafas, o M – suporavimas šiame grafe. Graf¹ H pakeiskime orientuotuoju grafu tokiu bûdu: kiekvienai suporavimo M briaunai suteikime orientacij¹ nuo Y á X, o visoms likusioms briaunoms – orientacij¹ nuo X á Y. Aišku, kad tada kelias nuo laisvosios viršûnës á laisv¹j¹ viršûnê bus srauto M atžvilgiu didinanèioji grandinë.

Procedûra PGA pradžioje konstruoja bekontûrinio tinklo lankus nuo viršûnës s á visas laisv¹sias aibës X viršûnes. Po to iš šiø laisvøjø viršûniø grafe organizuojama paieška platyn. Jei paieškos platyn metu pasiekiame laisv¹j¹ viršûnê , tai á bekontûriná tinkl¹ átraukiame lank¹ . Be to, nuo to momento, kai á tinkl¹ átraukiamas pirmasis toks lankas, daugiau nenagrinëjamos viršûnës, kurios nutolê nuo viršûnës s nemažiau kaip kelio nuo s iki t ilgis.

Panagrinëkime pseudomaksimalø sraut¹ procedûros PGA sukonstruotame pagalbiniame tinkle. Šiame pagalbiniame ilgio tinkle l ilgio (atmetame 1-¹já ir paskutinájá lankus) alternuojanèios didinanèiosios grandinës visø viršûniø potencialai yra lygûs 1. Pagal ši¹ grandinê padidinus sraut¹, visos grandinës viršûnës eliminuojamos iš tolesnio nagrinëjimo. Vadinasi, pagalbinio tinklo pseudomaksimalø sraut¹ apibrëš didžiausia aibë ilgio l poromis nesusikertanèiø alternuojanèiø grandiniø. Tokiø grandiniø ieškojim¹ realizuoja procedûra fazë, kuri naudoja paieškos gilyn iš viršûnës s pagalbiniame tinkle metod¹. Naujos aplankytos viršûnës talpinamos á stek¹ STEK. Kiekvien¹ kart¹, kai pasiekiama viršûnë t, steke esanèios viršûnës apibrëžia alternuojanèi¹ didinanèi¹j¹ grandinê. Tada visos viršûnës, išskyrus viršûnê s, šalinamos iš steko kartu didinant sraut¹ (suporavim¹), kurá nusako masyvas pora. Žemiau pateikti procedûrø PGA, fazë ir pagrindinës programos tekstai.

Hopkrofto ir Karpo didžiausio suporavimo algoritmas

Duota:  Dvidalis grafas , nusakytas gretimumo struktûra , èia – aibë viršûniø, gretimø viršûnei x.

Rasti:  Didžiausi¹ suporavim¹, kurá nusako masyvas pora [1..n], , kurios elementas

procedure PGA

begin

for u I V È do

begin

d [u] = ¥

SN [u] := Æ

end

Eilë Æ; SV := Æ

SV := SV È

d [s] := 0;

for x I X do

if pora [x] = 0  then

begin

Eilë x

SN [s] := SN [s] È

d [x] := 1;

end

while Eilë ¹ Æ do

begin

u Eilë

SV := SV È

if u I Y then

if pora [u] = 0 then

begin

SN [u] := SN [u] È t

if d [t] = ¥ then

begin

SV := SV È

d [t] := d [u] + 1;

end

end

else

begin

x := pora [u];

if d [t] = ¥ then

begin

Eilë x

SN [u] := SN [u] È

d [x] := d [u] + 1;

end

end

else

for y I N [u] do

if d [u] < d [y] then

begin

if d [y] = ¥ then Eilë y

SN [u] := SN [u] È

d [y] := d [u] + 1;

end

end

end

procedure faz

begin

for u I SV do

begin

naujas [u] := true;

p [u] := pradžia [u];

end

STEK Æ; STEK s; naujas [s] := false;

while STEK ¹ Æ do

begin

u := top (STEK);

if p [u] = nil then b := false

else b := not naujas [p [u] .viršûnë

while b do

begin

p [u] := p [u] pëdsakas

if p [u] = nil then b := false

else b := not naujas [p [u] .viršûnë

end

if p [u] ¹ nil then

if p [u] .viršûnë = t then

while top (STEK) ¹ s do

begin

y STEK

x STEK

pora [x] := y; pora [y] := x;

end

else

begin

v := p [u] .viršûnë

STEK v

naujas [v] := false;

end

else

u STEK

end

end

begin

for v I V do pora [v] := 0;

PGA

while t I SV do

begin

fazë

PGA

end

end

Reikia pažymëti, kad didelis Hopkrofto ir Karpo algoritmo efektyvumas gaunamas todël, kad faziø skaièius yra nedidesnis nei [Lip88].