Grafic transpus

Un grafic și transpunerea acestuia

În analiza matematică și algoritmică a teoriei graficului , graficul transpus al unui digraf G este un alt grafic orientat definit pe același set de noduri în care orientarea tuturor muchiilor este opusă graficului de pornire. Pentru fiecare arc $(u,v)$ ${\ displaystyle (u, v)}$ $(u, v)$ a graficului $G.$ ${\ displaystyle G}$ $G.$ , graficul transpus al $G.$ ${\ displaystyle G}$ $G.$ conține arcul $(v,u)$ ${\ displaystyle (v, u)}$ ${\ displaystyle (v, u)}$ si invers.

Graficul rezultat în urma acestei operații este în general notat cu ${G.}^{'}$ ${\ displaystyle G '}$ ${\ displaystyle G '}$ sau $G^{T}$ ${\ displaystyle G ^ {T}}$ ${\ displaystyle G ^ {T}}$ .

Definiție

Având în vedere un grafic $G=\langle V,E\rangle$ ${\ displaystyle G = \ langle V, E \ rangle}$ ${\ displaystyle G = \ langle V, E \ rangle}$ , unde este $V.$ ${\ displaystyle V}$ $V.$ este ansamblul de noduri și $E\subseteq V^{2}$ ${\ displaystyle E \ subseteq V ^ {2}}$ ${\ displaystyle E \ subseteq V ^ {2}}$ se spune că setul de arce este transpus din $G.$ ${\ displaystyle G}$ $G.$ graficul $G^{T}=\langle V,E'\rangle$ ${\ displaystyle G ^ {T} = \ langle V, E '\ rangle}$ ${\ displaystyle G ^ {T} = \ langle V, E '\ rangle}$ unde este

E'=\{(u,v)|(v,u)\in E\}

{\ displaystyle E '= \ {(u, v) | (v, u) \ în E \}}

{\ displaystyle E '= \ {(u, v) | (v, u) \ în E \}}

. ^[1]

Aplicații

Dacă matematic diferența dintre un grafic și transpunerea acestuia este minimă, poate fi mai importantă din punct de vedere al tehnologiei informației , în funcție de modul în care este reprezentat graficul. De exemplu, pentru un webgraph (adică un grafic care descrie legăturile dintre paginile World Wide Web ) este ușor să determinați legăturile de ieșire dintr-un nod, dar este destul de dificil să le determinați pe cele primite, în timp ce cu un graficul opusul este adevărat.

În consecință, în dezvoltarea algoritmilor pe grafice, poate fi util să se construiască transpunerea unui grafic, făcându-l într-o formă mai potrivită pentru operațiile care ar trebui efectuate pe acesta. Un exemplu este algoritmul Kosaraju pentru componentele puternic conectate , care aplică o căutare aprofundată de două ori, o dată pe datele furnizate și o dată pe cea transpusă. ^[1] Un alt exemplu poate fi algoritmul PageRank , în care pentru fiecare pagină este necesar să știm care sunt nodurile care conțin cel puțin un link către acesta. ^[2]

Notă

^ ^a ^b Alberto Montresor, 9. Grafice ( PDF ), despre algoritmi și structuri de date , disi.unitn.it , Universitatea din Trento. Adus la 22 mai 2016 (Arhivat din original la 22 mai 2016) .
^ Massimo Santini, PageRank - Folosirea hyperlinkurilor pentru extragerea informațiilor din WWW ( PDF ), pe dis.uniroma1.it , Universitatea din Milano - Departamentul de Științe ale Informației, 25 mai 2005. Accesat la 22 mai 2016 (arhivat din adresa URL originală pe 10 iulie 2007) .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe un grafic transpus

Portal IT

Portalul de matematică

[ASD-1] Alberto Montresor, 9. Grafice ( PDF ), despre algoritmi și structuri de date , disi.unitn.it , Universitatea din Trento. Adus la 22 mai 2016 (Arhivat din original la 22 mai 2016) .

[2] Massimo Santini, PageRank - Folosirea hyperlinkurilor pentru extragerea informațiilor din WWW ( PDF ), pe dis.uniroma1.it , Universitatea din Milano - Departamentul de Științe ale Informației, 25 mai 2005. Accesat la 22 mai 2016 (arhivat din adresa URL originală pe 10 iulie 2007) .

[1]

[2]