Gráf transzponáltja

Gráf és 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

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', G^T, G^R é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

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

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

• 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

1. Harary, Frank; Norman, Robert Z. & Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley
2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. MIT Press and McGraw-Hill., ex. 22.1–3, p. 530.
3. 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