Orientovaný graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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ť . 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:

Orientovaný graf a jeho symetrizace

Kondenzace[editovat | editovat zdroj]

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ů existují spojení jak z do tak i z do .

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[editovat | editovat zdroj]