Graf transponowany

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Graf transponowanygraf 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]