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