Suunnatussa graafissa G termejä converse [ 1] , transposo [ 2] tai käänteinen [ 3 ] käytetään viittaamaan toiseen suunnattuun graafiin, jolla on samat kärkijoukot ja samat kaareet, mutta tämän kaarien orientaatio . graafi on vastakkainen graafin G kaarien suuntauksen kanssa . Eli jos graafi G sisältää kaaren (u,v) , niin graafin G käänteis/transponoitu/vastakkainen graafi sisältää kaaren (v,u) ja päinvastoin.
Nimi käänteinen syntyy, koska kaarinuolien kääntäminen vastaa loogisen päättelyn käänteistä logiikassa . Termi transponoitu tulee algebrasta, koska transponoidun suunnatun graafin viereisyysmatriisi on alkuperäisen graafin viereisyysmatriisin transponointimatriisi .
Ei ole olemassa vakiintunutta mielipidettä, kumpi ehdoista on parempi.
Käänteinen graafi voidaan merkitä G' , G T , G R tai muulla tavalla riippuen artikkelissa tai kirjassa käytetystä terminologiasta.
Vaikka matemaattisesti ero graafin ja sen transponoidun graafin välillä on pieni, tietojenkäsittelytieteessä ero voi olla hyvin suuri riippuen graafin esittämistavasta. Esimerkiksi verkkograafissa on helppo määrittää kärkien lähtevät yhteydet, mutta vaikea määrittää saapuvat yhteydet, kun taas käänteisessä graafissa asia on päinvastoin. Sen vuoksi graafisia algoritmeja varten olisi joskus hyödyllistä rakentaa käänteinen graafi, jotta graafi saatetaan muotoon, joka sopii paremmin graafiin sovellettaviin toimintoihin. Esimerkki tästä on Kosaraju-algoritmi vahvasti kytketyille komponenteille , joka hakee syvyyshakua kahdesti , kerran tietylle graafille ja toisen kerran sen käänteiselle.
Vinosymmetrinen graafi on graafi , joka on isomorfinen oman transponoidun graafinsa kanssa erityisellä isomorfismilla, joka yhdistää kaikki kärjet.
Binäärirelaation käänteinen relaatio on relaatio, joka kääntää kunkin toisiinsa liittyvän objektiparin järjestyksen. Jos relaatio tulkitaan suunnatuksi graafiksi, niin käänteinen relaatio on sama kohde kuin transponoitu graafi. Erityisesti osittaisen järjestyksen kaksoisjärjestys voidaan tulkita transitiivisesti suljetun suunnatun asyklisen graafin transponoimiseksi .