Irányított G gráf esetén a konverz [ 1] , transzponált [ 2] vagy fordított [ 3 ] kifejezések egy másik irányított gráfra vonatkoznak , amelynek csúcsai és ívei megegyeznek, de ennek íveinek tájolása. gráf ellentétes a G gráf íveinek tájolásával . Vagyis ha a G gráf egy (u,v) ívet tartalmaz , akkor a G gráf inverz/transzponált/ellentétes gráfja tartalmaz egy (v,u) ívet , és fordítva.
Az inverz elnevezés azért keletkezik, mert az ívnyilak megfordítása megfelel a logikai következtetés megfordításának. A transzponált kifejezés az algebrából származik, mivel egy transzponált irányított gráf szomszédsági mátrixa az eredeti gráf szomszédsági mátrixának transzponálási mátrixa.
Nincs kialakult vélemény, hogy melyik kifejezés előnyösebb.
Egy inverz gráf jelölhető G' , G T , G R -ként vagy más módon, a cikkben vagy könyvben alkalmazott terminológiától függően.
Bár matematikailag kicsi a különbség a gráf és a transzponált gráf között, a számítástechnikában a különbség nagyon nagy lehet, attól függően, hogy a gráfot milyen módon ábrázolják. Például egy web gráfnál könnyű meghatározni a csúcsok kimenő kapcsolatait, de nehéz meghatározni a bejövő kapcsolatokat, míg egy fordított gráfnál ennek az ellenkezője igaz. Ezért a gráfokon végzett algoritmusok esetében néha hasznos lenne egy inverz gráfot létrehozni, hogy a gráfot olyan formába hozza, amely alkalmasabb a gráfra alkalmazott műveletekhez. Példa erre a Kosaraju algoritmus erősen csatolt komponensekre , amely kétszer alkalmaz mélységi keresést , egyszer egy adott gráfra, másodszor pedig annak inverzére.
A ferde-szimmetrikus gráf egy olyan gráf , amely izomorf a saját transzponált gráfjával az izomorfizmus speciális formáján keresztül, amely minden csúcsot párosít.
A bináris reláció fordított relációja olyan reláció, amely megfordítja az egyes kapcsolódó objektumpárok sorrendjét. Ha a relációt irányított gráfként értelmezzük, akkor az inverz reláció ugyanaz az objektum, mint a transzponált gráf. Konkrétan egy részleges sorrend kettős sorrendje egy tranzitívan zárt irányított aciklikus gráf transzpozíciójaként értelmezhető.