az az irányított gráf, melyet az eredeti irányított gráf összes élének megfordításával kapunk From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén egy G irányított gráf megfordítása (converse)[1] vagy transzponáltja (transpose[2] vagy reverse[3]) alatt olyan irányított gráf értendő, melynek csúcsai G csúcsaival egyeznek meg, éleinek orientációja pedig G éleihez képest fordított. Tehát, ha G tartalmaz egy (u,v) élt, akkor G megfordításában szerepelni fog a (v,u) él és viszont.
A „megfordítás” kifejezés a logikai implikáció nyilainak megfordítására utal. A „transzponált” kifejezés pedig a szomszédsági mátrixra, mivel az irányított gráf transzponáltjának szomszédsági mátrixa éppen az eredeti gráf szomszédsági mátrixának a transzpontáltja.
Nincs általánosan elfogadott terminológia.
A gráf transzponáltjának különböző jelöléseit – G', GT, GR és egyéb jelölések – attól függően szokás használni, hogy az előzőek közül melyik terminológiát használják, illetve szerzőnként is különböző lehet.
Bár matematikailag nincs túl nagy különbség egy gráf és a transzponáltja között, a számítástudományban ez a különbség fontosabb lehet, a gráf reprezentációjától függően. Például a webgráf esetében egy csúcs kimenő éleit könnyű meghatározni, míg a bejövőket nehéz, a gráf megfordításánál nyilván ennek a fordítottja igaz. A gráfalgoritmusokban ezért néha hasznos egy gráf megfordításával számolni az elvégzendő műveletektől függően. Példa erre az erősen összefüggő komponensekre vonatkozó Kosaraju-algoritmus, ami kétszer futtat le mélységi keresést, először a megadott gráfon, másodszor pedig a transzponáltján.
A ferdeszimmetrikus gráfok azok az irányított gráfok, melyek izomorfak saját transzponáltjukkal.
Egy bináris reláció inverze az a reláció, ami a relációban lévő objektumpár sorrendjét megfordítja. Ha a relációt irányított gráfnak tekintjük, ez megegyezik a gráf transzponáltjával. Ezen belül egy részbenrendezés duálisa értelmezhető egy tranzitívan lezárt irányított körmentes gráf transzponáltjaként is.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
