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 $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\iff (y,x)\in E$ nazywamy grafem transponowanym grafu $G.$

Bibliografia

• Szablon:Cytuj stronę