5. PRETOKI IN PREREZI

! definicija pretoka

imamo usmerjen graf G = (V,E) in pretočnosti d_e za vsako povezavo e ∈ E.

Iščemo maksimalni pretok:

∀e ∈ E: 0 ≤ x_e ≤ d_e

Imamo dve posebni vozlišči:

• začetno vozlišče s

• končno vozlišče t

predpostavimo, da v s in iz t ne gre nobena povezava, za ostala vozlišča veljajo Kirchhoffovi zakoni

∀w∈V∖{s,t}: ∑_uw∈E x_uw = ∑_wu∈E x_wu

iščemo pretok z maksimalno prostornino:

max ∑_{e∈E,začetek(e)=s} x_e

_p.p. ∀w ∈ V\{s,t}: ∑_uw∈E x_uv = ∑_wu∈E x _wu

∀uv ∈ E: 0 < x_uv < d_uv

To je poseben primer problema razvoza z omejitami:

vzamemo b_v = 0 (v ∈ V), c_e = 0 (e ∈ E) ter dodamo povezavo ts s c_ts = -1, d_ts = ∞

! definicija povečujoča pot

definicija prerez

za problem maksimalnega pretoka na usmerjenem grafu G = (V,E) ter začetnim vozliščem s in končnim vozliščem t je množica C ⊆ V prerez, če velja s ∈ C, t ∉ C

Trditev prostornina pretoka in prereza

izrek (kaj velja za problem maksimalnega pretok in minimalnega prerez)

za problem maksimalnega pretoka in minimalnega prereza velja natanko ena od sledečih možnosti

1. Problem maksimalnega pretoka je neomejen, kapaciteta vsakega prereza je ∞.

2. Obstajata maksimalen pretok x in minimalen prerez C, tako da je prostornina x enaka kapaciteti C.

Kako najdemo povečujočo pot?

Začnemo s C = {s}, nato pa ponavljamo za vsak v ∈ C: ali obstaja w ∉ C, da velja x_vw< d_vw ali x_wv > 0 - če obstaja, dodamo w v C.

• Če v nekem koraku dobimo t ∈ C, smo našli povečujočo pot od s do t, tako da lahko povečamo pretok.

• Če v nekem koraku tak w ne obstaja, povečujoče poti ni - našli smo maksimalni pretok x in minimalni prerez C.