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. +more 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)) \,\! s hodnotící funkcí 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) \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\colon E(G) \to R_0^+. +more Aby mohla být výše uvedená funkce nazvána tokem, musí splňovat následující podmínky: * tok je omezený kapacitou hrany: \forall e \in E(G): t(e) \le c(e) * ve vnitřních vrcholech se musí vstupní a výstupní tok (nebo také přítok a odtok) rovnat: \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: \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: \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. +more navrhnout funkci toku t \,\. tak, aby odtok ze zdrojů \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\colon V(G) \to R_0^+, kterou nesmí překročit odtok ani přítok na jednotlivých vrcholech, tj. \forall v \in V(G) : \sum_{e \in \to v} t(e) \leq c_2(v) \,\. +more 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. +more 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 \} \,\. a 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. +more 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

Goldbergův algoritmus * Fordův-Fulkersonův algoritmus *Dinicův algoritmus * Minimální řez

Externí odkazy

[url=http://teorie-grafu. elfineer. +morecz/vybrane-problemy/toky-v-sitich. php]Toky v sítích[/url] - úvod do toků v sítích, animace Ford-Fulkersonova algoritmu * Jakub Černý: [url=https://web. archive. org/web/20071018060717/http://kam. mff. cuni. cz/~kuba/ka/]Základní grafové algoritmy[/url] (texty v pdf) * Tomáš Valla, Jiří Matoušek: [url=http://kam. mff. cuni. cz/~valla/kg. html]Kombinatorika a grafy I. [/url] (2. kapitola).

Kategorie:Grafové pojmy