Fordův–Fulkersonův značkovací algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Fordův-Fulkersonův značkovací algoritmus je obecný postup značkování nenasycené cesty v grafu při výpočtu maximálního toku.

Maximální tok v grafu při užití Fordovy-Fulkersonovy metody[editovat | editovat zdroj]

Nechť Xk je současný maximální tok grafem. Nechť xk je nalezený přírůstek maximálního toku v grafu.

Pak nový maximální tok lze vyjádřit jako Xk+1 = Xk + xk.

Oprava současných toků[editovat | editovat zdroj]

Opravíme toky v grafu na hranách na cestě označené Fordovou-Fulkersonovou metodou.

Nechť xij je současný tok hranou hij.

  • pro nenasycené hrany orientované ve směru toku se nový tok rovná xk+1ij = xkij + xk
  • pro hrany, kde existuje tok orientovaný proti směru současného " - xij " se nový tok rovná xk+1ij = - xkij + xk
  • pro ostatní se tok nemění xk+1 = xk

Fordův-Fulkersonův značkovací algoritmus[editovat | editovat zdroj]

  1. Označme vstupní uzel sítě značkou " +0 "
  2. Hledáme cestu z vstupního uzlu do výstupního uzlu sítě. Každý vedlejší uzel j, do něhož existuje nenasycená cesta z uzlu i ve směru toku označíme značkou " + i ", každý vedlejší uzel, který obsahuje tok proti směru proudu " - xij" označíme značkou " -i ". Určíme hodnotu přírůstku toku xk jako xk = min (kij - xij), kde kij je kapacita hrany hij.
  3. Pokud nejsme schopni nalézt touto metodou cestu ze vstupu do výstupu, výpočet končí. Současný nalezený maximální tok je konečným maximálním tokem na síti.

Literatura[editovat | editovat zdroj]

Fiala Petr - Řízení projektů, 2. vydání, Praha, 2008, ISBN 978-80-245-1413-0