Orientovaný graf

Pojmem 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. 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

Kondenzovaný orientovaný graf z uzlů b, c, f vznikl pouze uzel b

Související články

• Neorientovaný graf

Externí odkazy

• Obrázky, zvuky či videa k tématu orientovaný graf na Wikimedia Commons

Autoritní data	NKC: ph139314 BNF: cb119847650 (data) GND: 4156815-1 LCCN: sh85038262 NLI: 987007555293505171 SNK: 190485