Pretok skozi omrežje

Problem maksimalnega pretoka skozi omrežje.

Imamo funkcijo c, ki priredi povezavam kapacitete.

c: <i,j> |--> cij

Tudi pretok je funkcija povezav.

x: <i,j> |--> xij

• Poiščemo nenasičeno povezavo

Povezava je zasičena, če je povezava v smeri toka in je c_i = x_i ali če je povezava v nasprotni smeri in je c_i = 0. Pot je zasičena, če je ena povezava na poti zasičena.

• Pot zasičimo in začnemo znova

Točka:

- točka

- označena točka

- označena in obiskana točka

Povezava ima obliko (cij, xij) --> npr.: (3,1)

- cij --> Kapaciteta

- xij --> Pretok

- torej ima povezava obliko (kapaciteta, pretok)

Zasičena povezava:

Povezava je zasičena, ko velja:

- Negativna povezava (usmerjena od j proti i)--> pretok = 0

- Pozitivna povezava (usmerjena od i proti j)--> kapaciteta = pretok

Zasičena pot:

Je taka pot na kateri je vsaj ena zasičena povezava

Algoritem

Graf poskušaš čim bolj zasičiti. To delaš na naslednji način:

1. Vsa vozlišča so na začetku neoznačena in neobiskana (beli krogci)

2. Označiš (pobarvaš) začetno vozlišče S

3. Označiš vsa vozlišča do katerih lahko prideš iz S po nenasičenih povezavah. Vozlišče S pa je sedaj

  obiskano (ga prečrtaš) 

4. Nadaljuješ v označenih vozliščih.

  Označiš vozlišča do katerih prideš po nenasičenih povezavah, trenutno vozlišče pa potem prečrtaš     
  (obiskano). 

5. Povezavo med dvema »označenima in obiskanima« točkama označiš z vijugasto črto, to je»kao pot«

6. Če s tem postopkom prideš do končnega vozlišča T, je pot po kateri si prišel do T nenasičena in jo

  zasitiš (povečaš pretok, nadaljuj pri 7.). 
  V nasprotnem primeru si našel maksimalni pretok. Maksimalni pretok izračunaš tako, da sešteješ vse 
  pretoke ki vodijo v končno vozlišče S.

7. Pretok povečaš tako, da pogledaš pretoke na celotni poti, ki si jo naredil od S do T.

  Zapomniš si razliko med kapaciteto in pretokom tistega pretoka, ki mu najmanj manjka do polne 
  kapacitete. Npr.: (10,9) ? razlika je 1.

8. Ponovno si narišeš graf in po celotni prejšnji poti (od S do T) povečaš pretoke pri pozitivnih

  povezavah za pri točki 7. izračunano razliko, pri negativnih povezavah pa to razliko odšteješ.
  Ostali pretoki ostanejo enaki. Nadaljuješ pri toči 1.

Ob koncu algoritma dobimo tudi minimalen prerez grafa. Za tega velja:

1. S,T podmnožica V
2. 1 element S, n element T
3. S unija T = V
4. S presek T = 0

Ta algoritem ima tri funkcije:

• poišče maksimalen pretok
• poišče minimalen prerez
• dokazuje minimalne prereze (al nekej tko)

Primer