Graf transponowany

Graf transponowany – jest to 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 11 kwietnia 2011].