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

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:

 

Kondenzace

editovat

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

Externí odkazy

editovat