Transponirani graf

Transponirani graf (tudi konvertirani graf) danega usmerjenega grafa je drugi usmerjeni graf, ki ima ista vozlišča kot dani graf, povezave pa imajo nasprotno smer od danega grafa.

Ime transponirani izhaja iz dejstva, da je matrika sosednosti transponiranega grafa enaka transponirani matriki izhodiščnega grafa.

To pomeni, da takrat, ko graf ${\displaystyle G\,}$ vsebuje povezavo ${\displaystyle (u,v)\,}$ transponirani graf vsebuje povezavo ${\displaystyle (v,u)\,}$ in obratno.

Transponirani graf različni avtorji označujejo na različne načine. Najbolj pogosto je označevanje G', G^T, G^R.