Transponovaný graf

V teorii grafů se pojmem transponovaný graf označuje takový orientovaný graf, jehož hrany jsou orientovány opačně než u původního grafu.

Definice

Nechť G = (V, E) je orientovaný graf. Graf G^T = (V, E^T), kde (x, y)\in E^T \Leftrightarrow (y, x)\in E se nazývá transponovaný graf grafu G.

Využití

v algoritmu prohledávání do hloubky při hledání silně souvislých komponent grafu (SSK)

Vlastnosti

SSK grafu GT jsou transponované SSK grafu G

Externí odkazy

Kategorie:Typy grafů