Pentru un graf dirijat G , termenii invers [ 1 ] , transpun [ 2 ] , sau invers [ 3 ] sunt folosiți pentru a se referi la un alt graf direcționat cu același set de vârfuri și aceleași arce, dar orientarea arcelor acestuia. graficul este opus orientării arcelor graficului G . Adică, dacă graficul G conține un arc (u,v) , atunci graficul invers/transpus/opus al graficului G conține un arc (v,u) și invers.
Numele invers apare deoarece inversarea săgeților arcului corespunde inversării unei inferențe logice în logică. Termenul transpus provine din algebră deoarece matricea de adiacență a unui graf direcționat transpus este matricea de transpunere a matricei de adiacență a grafului original.
Nu există o opinie stabilită care dintre termeni este de preferat.
Un grafic invers poate fi notat cu G' , G T , G R sau în alt mod, în funcție de terminologia adoptată în articol sau carte.
Deși din punct de vedere matematic diferența dintre un graf și graficul său transpus este mică, în informatică diferența poate fi foarte mare, în funcție de modul în care este reprezentat graficul. De exemplu, pentru un grafic web, este ușor să determinați conexiunile de ieșire ale vârfurilor, dar dificil de determinat conexiunile de intrare, în timp ce pentru un grafic invers, este adevărat opusul. Prin urmare, pentru algoritmii pe grafice, uneori ar fi util să construiți un grafic invers pentru a aduce graficul într-o formă care este mai potrivită pentru operațiile aplicate graficului. Un exemplu în acest sens este algoritmul Kosaraju pentru componentele puternic cuplate , care aplică căutarea în adâncime de două ori , o dată pentru un grafic dat și a doua oară pentru inversul său.
Un graf simetric oblic este un graf izomorf cu propriul graf transpus printr-o formă specială de izomorfism care împerechează toate vârfurile.
Relația inversă unei relații binare este o relație care inversează ordinea fiecărei perechi de obiecte înrudite. Dacă relația este interpretată ca un grafic direcționat, atunci relația inversă este același obiect ca și graficul transpus. În special, ordinul dual al unui ordin parțial poate fi interpretat ca o transpunere a unui graf aciclic direcționat închis tranzitiv .