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\iff (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 G^T jsou transponované SSK grafu G

Externí odkazy

• Šablona:Commonscat