Graf transponowany

Graf transponowany – graf skierowany z odwróconymi krawędziami.

Powstaje przez zmianę kierunku wszystkich krawędzi. Przykładowo krawędź 1 → 2, w grafie transponowanym zostanie zamieniona na krawędź 2 → 1.

Nazwa wywodzi się stąd, że macierz sąsiedztwa dla grafu $G^{T}$ transponowanego jest transponowaną macierzą sąsiedztwa grafu wyjściowego $G.$

Ścisła definicja

Niech $G=(V,E)$ będzie grafem skierowanym. Graf $G^{T}=(V,E^{T}),$ gdzie $(x,y)\in E^{T}\Leftrightarrow (y,x)\in E$ nazywamy grafem transponowanym grafu $G.$

Bibliografia

• Rafał Pytko: Silnie spójne składowe. www.algorytm.org, 26 września 2009. [dostęp 2011-04-11].