Gráf transzponáltja
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.
Jelölés[szerkesztés]
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.
Alkalmazások[szerkesztés]
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.
Kapcsolódó fogalmak[szerkesztés]
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.
Fordítás[szerkesztés]
- Ez a szócikk részben vagy egészben a Transpose graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek[szerkesztés]
- ↑ Harary, Frank; Norman, Robert Z. & Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. MIT Press and McGraw-Hill., ex. 22.1–3, p. 530.
- ↑ Essam, John W. & Fisher, Michael E. (1970), "Some basic definitions in graph theory", Reviews of Modern Physics 42 (2): 275, DOI 10.1103/RevModPhys.42.271, entry 2.24
