Řez (teorie grafů)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. srpna 2021; kontroly vyžadují 2 úpravy .

Řez grafu v problémech s tokem je dvojice množin vrcholů (S,T) taková, že

$S\pohár T=V$ , kde je množina vrcholů grafu $PROTI$
$S\cap T=\emptyset$
$s \in S, t \v T$ , kde je zdroj, je odtok. $s$ $t$

Velikost řezu je součtem kapacit takových hran , které . $(i, j)$ $i\v S,j\v T$

Další definice řezu (sekce) grafu

Řez grafu je soubor hran, které tvoří bipartitní podgraf, jehož odstraněním se graf rozdělí na dvě nebo více složek, kterými mohou být zejména izolované uzly. Stejně jako přímka procházející všemi okraji řezu grafu.

Charakteristika

Čáry řezu mohou protínat libovolný počet hran a tětiv.
Pro získání hlavního řezu grafu je nutné nakreslit čáru řezu grafu tak, aby protínala pouze jednu větev grafu v libovolném průsečíku tětiv.

Viz také