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.

SymetrizaceEditovat

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:

 

KondenzaceEditovat

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ánkyEditovat

Externí odkazyEditovat