Graf transponowany

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]