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 ${\displaystyle G^{T}=(V,E^{T})}$, kde ${\displaystyle (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 G^T jsou transponované SSK grafu G

Externí odkazy

• Obrázky, zvuky či videa k tématu Transponovaný graf na Wikimedia Commons