Transponirani graf

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

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 vsebuje povezavo transponirani graf vsebuje povezavo in obratno.

Transponirani graf različni avtorji označujejo na različne načine. Najbolj pogosto je označevanje G', GT, GR.