Pretoki in prerezi

  • Primer. Letalo iz San Francisca v New York je polno. Imamo pa proste sedeže na drugih letih:

    • San Francisco - Denver: 5 mest
    • San Francisco - Houston: 6 mest
    • Denver - Atlanta: 2 mesti
    • Denver - Chicago: 5 mest
    • Houston - Atlanta: 5 mest
    • Atlanta - New York: 7 mest
    • Chicago - New York: 4 mesta

    Koliko dodatnih potnikov lahko prepeljejo?

Problem maksimalnega pretoka

  • Imamo usmerjen graf in pretočnosti za vsako povezavo .

  • Iščemo maksimalni pretok:

  • Imamo dve posebni vozlišči:

    • začetno vozlišče (angl. source)
    • končno vozlišče (angl. terminal)

  • Predpostavimo, da v in iz ne gre nobena povezava.

  • Za ostala vozlišča veljajo Kirchhoffovi zakoni:

Prostornina pretoka

  • Seštejmo Kirchhoffove zakone po vseh :

    č

  • Prostornina pretoka je enaka

    č

Linearni program

Iščemo pretok z maksimalno prostornino:

č

Problem razvoza z omejitvami

To je poseben primer problema razvoza z omejitvami: vzamemo (), () ter dodamo povezavo s , .

Simpleksna metoda na omrežjih za PRO

Ta problem lahko rešimo s simpleksno metodo na omrežjih za problem razvoza z omejitvami.

Simpleksna metoda na omrežjih za PRO (2)

Simpleksna metoda na omrežjih za PRO (3)

Simpleksna metoda na omrežjih za PRO (4)
  • V praksi uporabljamo Ford-Fulkersonov algoritem.

Povečujoče poti

  • Naj bo dopustna rešitev za problem maksimalnega pretoka na usmerjenem grafu s pretočnostmi () ter začetnim vozliščem in končnim vozliščem .

  • Rečemo, da je () povečujoča pot, če je , ter, za ,

    • in (prema povezava), ali
    • in (obratna povezava).

Ideja algoritma

  • Vzamemo povečujočo pot z množico povezav .

  • Pretok na tej poti povečamo za

    (tj., povečamo na premih in zmanjšamo na obratnih povezavah).

Primer

Primer (2)

Povečamo pretok na izbrani poti za 1:

Primer (3)

  • Najbolj nas omejuje obratna povezava - spet povečamo pretok za :

  • Takih poti ni več - imamo optimalno rešitev.

Prerezi

  • Definicija. Za problem maksimalnega pretoka na usmerjenem grafu ter začetnim vozliščem in končnim vozliščem je množica prerez, če velja , .

  • Za vsaki vozlišči , tako da velja , naj velja .

  • Potem lahko Kirchhoffove zakone pišemo kot

  • Seštejmo za vsak :

  • Členi , kjer , se pojavijo na obeh straneh in se jih lahko znebimo:

Kapaciteta prereza

  • Ker ni končno vozlišče nobene povezave, velja

  • Prostornina pretoka torej zadošča enakosti

  • Definirajmo še kapaciteto prereza kot

Prostornina pretoka in kapaciteta prereza

  • Trditev. Naj bosta in pretok s prostornino in prerez s kapaciteto za problem maksimalnega pretoka. Potem velja .

  • Dokaz.

  • Opomba. Primerjaj s šibkim izrekom o dualnosti!

  • Posledica. Če velja , je maksimalen pretok, pa minimalen prerez.

  • Govorimo torej o problemu maksimalnega pretoka in minimalnega prereza (angl. maximal flow/minimal cut).

Maksimalni pretoki in minimalni prerezi

  • Izrek. 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 in minimalen prerez , tako da je prostornina enaka kapaciteti .

  • Opomba. Primerjaj s krepkim izrekom o dualnosti!

Dokaz

  • Problem maksimalnega pretoka na usmerjenem grafu s pretočnostmi () ter začetnim vozliščem in končnim vozliščem je dopusten linearni program, saj je ničelni pretok dopustna rešitev.
  • Če je neomejen, po zgornji trditvi ne obstaja prerez s končno kapaciteto (sicer bi imeli zgornjo mejo za prostornino).
  • V nasprotnem primeru naj bo optimalna drevesna rešitev pridruženega problema razvoza z omejitvami za drevo .
  • Naj bodo razvozne cene. Ker velja , povezava ni nasičena. Ker velja , sledi .

Dokaz (2)

  • Potem je

    prerez, saj velja in . Določimo prostornino pretoka .

    • Če , , potem , torej in (nasičena povezava).
    • Če , , potem , torej in (prazna povezava).

  • Tako velja

  • Sledi, da je maksimalni pretok in minimalni prerez.

Iskanje povečujočih poti

  • Spomnimo se: povečujoča pot sestoji iz premih povezav, ki niso nasičene, in obratnih povezav, ki niso prazne.

  • Kako najdemo povečujočo pot?

    • Začnemo s , nato pa ponavljamo za vsak : ali obstaja , da velja ali - če obstaja, dodamo v .
    • Če v nekem koraku dobimo , smo našli povečujočo pot od do , tako da lahko povečamo pretok.
    • Če v nekem koraku tak ne obstaja, povečujoče poti ni - našli smo maksimalni pretok in minimalni prerez .

Pridruženi graf

Običajno problem pretoka rešujemo na pridruženem grafu:

→

Primer

Primer (2)

Primer (3)

Primer (4)
  • Prostornina pretoka:
  • Kapaciteta prereza:

Optimalna rešitev

Končnost algoritma

Opomba. Ali se Ford-Fulkersonov algoritem vedno ustavi?

  • NE.
  • Obstajajo primeri, kjer lahko (če "nerodno" izbiramo povečujoče poti) v neskončno ponavljamo postopek (če so nekatere pretočnosti iracionalne), pri čemer prostornina pretoka konvergira proti številu, ki je manjše od prostornine maksimalnega pretoka.
  • Da zagotovimo, da se algoritem ustavi, v vsakem koraku izberemo najkrajšo povečujočo pot (Edmonds-Karpov algoritem).

Disjunktne poti

Opomba. Disjunktne povečujoče poti (po povezavah) lahko obravnavamo hkrati, npr.