Tok v síti

Šipky znázorňují představu toku v jednoduchém grafu. První číslo u každé hrany představuje aktuální velikost toku, druhé pak kapacitu hrany.

Toky v sítích jsou v rámci teorie grafů předmětem studia teorie sítí.

Motivace

Problémy řešené v rámci zkoumání toků v sítích jsou motivovány praktickými úlohami o propustnosti - typickým příkladem je propustnost železniční, silniční nebo vodovodní sítě. Tomu odpovídá i používaná terminologie.

Síť obsahuje hrany - úseky potrubí, úseky silnice mezi dvěma křižovatkami, které mají danou svou maximální propustnost - kapacitu.

Síť obsahuje vrcholy - místa, kde se setkává více úseků potrubí, případně silniční křižovatky nebo železniční uzly. Z pohledu řešení jednotlivých úloh obvykle pracujeme v uzavřeném konečném systému toků, kde tedy existují zdroje - vrcholy, kde tok vzniká a tzv. stoky - vrcholy, kde tok zaniká. Ostatní vrcholy, označované jako vnitřní, jsou místa, kudy tok probíhá a kde musí přitékat přesně tolik, kolik odtéká.

Definice

Síť definujeme jako ohodnocený orientovaný graf G = ( V ( G ) , E ( G ) ) {\displaystyle G=(V(G),E(G))\,\!} s hodnotící funkcí c : E ( G ) → R 0 + {\displaystyle c\colon E(G)\to R_{0}^{+}} , která udává tzv. kapacitu každé hrany.
Na tomto grafu je množina vrcholů rozdělena na tři disjunktní množiny: zdroje, stoky a vnitřní vrcholy V ( G ) = V + ( G ) ∪ V − ( G ) ∪ V 0 ( G ) {\displaystyle V(G)=V^{+}(G)\cup V^{-}(G)\cup V^{0}(G)\,\!} .

Na každé hraně grafu můžeme pak definovat tzv. tok, kladnou veličinu určenou funkcí t : E ( G ) → R 0 + {\displaystyle t\colon E(G)\to R_{0}^{+}} . Aby mohla být výše uvedená funkce nazvána tokem, musí splňovat následující podmínky:

  • tok je omezený kapacitou hrany: ∀ e ∈ E ( G ) : t ( e ) ≤ c ( e ) {\displaystyle \forall e\in E(G):t(e)\leq c(e)}
  • ve vnitřních vrcholech se musí vstupní a výstupní tok (nebo také přítok a odtok) rovnat: ∀ v ∈ V 0 ( G ) : ∑ e ∈→ v t ( e ) = ∑ e ∈ v → t ( e ) {\displaystyle \forall v\in V^{0}(G):\sum _{e\in \to v}t(e)=\sum _{e\in v\to }t(e)}
  • ve zdrojích nesmí být přítok větší než odtok: ∀ v ∈ V + ( G ) : ∑ e ∈→ v t ( e ) ≤ ∑ e ∈ v → t ( e ) {\displaystyle \forall v\in V^{+}(G):\sum _{e\in \to v}t(e)\leq \sum _{e\in v\to }t(e)}
  • ve stocích nesmí být odtok větší než přítok: ∀ v ∈ V − ( G ) : ∑ e ∈ v → t ( e ) ≤ ∑ e ∈→ v t ( e ) {\displaystyle \forall v\in V^{-}(G):\sum _{e\in v\to }t(e)\leq \sum _{e\in \to v}t(e)}

Úlohy a jejich řešení

Základní úlohou je najít maximální tok v grafu. Maximalitou se v tomto kontextu myslí „co nejvíc využít propustnosti“, tj. navrhnout funkci toku t {\displaystyle t\,\!} tak, aby odtok ze zdrojů ∑ v ∈ V + ( G ) ( ∑ e ∈ v → t ( e ) − ∑ e ∈→ v t ( e ) ) {\displaystyle \sum _{v\in V^{+}(G)}(\sum _{e\in v\to }t(e)-\sum _{e\in \to v}t(e))} byl maximální možný.

Tato úloha může být různým způsobem modifikována - mohu mít například navíc určenou i vrcholovou kapacitu c 2 : V ( G ) → R 0 + {\displaystyle c_{2}\colon V(G)\to R_{0}^{+}} , kterou nesmí překročit odtok ani přítok na jednotlivých vrcholech, tj. ∀ v ∈ V ( G ) : ∑ e ∈→ v t ( e ) ≤ c 2 ( v ) {\displaystyle \forall v\in V(G):\sum _{e\in \to v}t(e)\leq c_{2}(v)\,\!} a obdobně i pro odtok.

Zajímavá a jednoduchá myšlenka převádí úlohu s mnoha zdroji a mnoha stoky na úlohu s jedním zdrojem a jedním stokem:

Zaveďme si do grafu dva nové vrcholy z a s, které označíme za virtuální zdroj a virtuální stok. Vrchol z spojme hranou se všemi zdroji původního grafu a těmto hranám přiřadím nekonečnou kapacitu, všechny stoky původního grafu spojme s vrcholem s a i těm přiřaďme nekonečnou kapacitu. Nakonec ještě všechny původní zdroje a stoky označím za vnitřní vrcholy nově vzniklého grafu, takže tento nový graf bude mít V + = { z } {\displaystyle V^{+}=\{z\}\,\!} a V − = { s } {\displaystyle V^{-}=\{s\}\,\!} . Dá se poměrně snadno nahlédnout, že maximální tok v tomto grafu zúžený na hrany původního grafu je maximálním tokem v původním grafu.

Fordova-Fulkersonova věta uvádí do vztahu maximální tok a minimální řez oddělující zdroj od stoku. Vychází z ní i myšlenka základního způsobu hledání maximálního toku, Fordova-Fulkersonova algoritmu. Jeho lepší variantou je Edmondsův-Karpův algoritmus, dalšími možnými přístupy k řešení jsou Dinicův algoritmus a Goldbergův algoritmus. Pro sítě odpovídající rovinným grafům je možné použít také Algoritmus nejhořejší cesty.

Aplikace

Toky v sítích mají široké spektrum aplikací. Nejčastěji se používají pro modelování skutečných sítí (vodovodních, dopravních, elektrických, počítačových a jiných) a zkoumání jejich vlastností (zejména maximální kapacity jejich segmentů).

Související články

Externí odkazy

  • Logo Wikimedia Commons Obrázky, zvuky či videa k tématu Tok v síti na Wikimedia Commons
  • Toky v sítích - úvod do toků v sítích, animace Ford-Fulkersonova algoritmu
  • Jakub Černý: Základní grafové algoritmy (texty v pdf)
  • Tomáš Valla, Jiří Matoušek: Kombinatorika a grafy I. (2. kapitola)