Orientovaný graf
Author
Albert FloresPojmem orientovaný graf se v teorii grafů označuje takový graf, jehož hrany jsou uspořádané dvojice. Naproti tomu hrany neorientovaného grafu jsou (dvouprvkové) množiny. Hrany orientovaného grafu mají tedy pevně danou orientaci. Tudíž výrazy (x, y) a (y, x) označují různé hrany. Hrana (x, x) se nazývá smyčka.
V informatice se orientované grafy často používají například pro znázornění konečného automatu. Vrcholy odpovídají stavům automatu, hrany pak přechodům mezi nimi.
Symetrizace
Je-li G = (V, E) orientovaný graf, lze sestrojit neorientovaný graf G’ = (V, E’), který je k němu v jistém smyslu ekvivalentní: nechť \{v_1, v_2\} \in\mathit{E'}\Leftrightarrow (v_1, v_2)\in\mathit{E}\lor (v_2, v_1)\in\mathit{E}. Z grafu G tedy jakoby odstraníme informaci o směru hran a G’ se pak nazývá symetrizace grafu G.
Vlevo orientovaný graf, vpravo jeho symetrizace:
Kondenzace
Kondenzace je taková operace, která ze silné komponenty vytvoří jeden uzel (viz obrázky vpravo). Silná komponenta je maximální silně souvislý graf. +more To znamená podgraf, kde pro každou dvojici uzlů x, y existují spojení jak z x do y tak i z y do x.
Orientovaný graf a jeho silná komponenta z uzlů b, c a f +moresvg|náhled|vpravo'>Kondenzovaný orientovaný graf z uzlů b, c, f vznikl pouze uzel b.