Graf transponowany


Graf transponowany w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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 G T {\displaystyle G^{T}} transponowanego jest transponowaną macierzą sąsiedztwa grafu wyjściowego G . {\displaystyle G.}

Ścisła definicja | edytuj kod

Niech G = ( V , E ) {\displaystyle G=(V,E)} będzie grafem skierowanym. Graf G T = ( V , E T ) , {\displaystyle G^{T}=(V,E^{T}),} gdzie ( x , y ) E T ( y , x ) E {\displaystyle (x,y)\in E^{T}\Leftrightarrow (y,x)\in E} nazywamy grafem transponowanym grafu G . {\displaystyle G.}

Bibliografia | edytuj kod

Na podstawie artykułu: "Graf transponowany" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy