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 transponowanego jest transponowaną macierzą sąsiedztwa grafu wyjściowego
Ścisła definicja
[edytuj | edytuj kod]Niech będzie grafem skierowanym. Graf gdzie nazywamy grafem transponowanym grafu
Bibliografia
[edytuj | edytuj kod]- Rafał Pytko: Silnie spójne składowe. www.algorytm.org, 26 września 2009. [dostęp 2011-04-11].