Grafo trasposto

Un grafo ed il suo trasposto

Nell'analisi matematica e algoritmica della teoria dei grafi, il grafo trasposto di un digrafo G è un altro grafo orientato definito sullo stesso insieme di nodi in cui l'orientamento di tutti gli archi è opposto rispetto al grafo di partenza. Per ogni arco $(u,v)$ del grafo $G$, il grafo trasposto di $G$ contiene l'arco $(v,u)$ e viceversa.

Il grafo risultante da tale operazione è generalmente denotato con $G'$ o $G^{T}$.

Definizione

Dato un grafo $G=\langle V,E\rangle$, dove $V$ è l'insieme dei nodi e $E\subseteq V^{2}$ l'insieme degli archi, si dice trasposto di $G$ il grafo $G^{T}=\langle V,E'\rangle$ dove

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

Applicazioni

Se matematicamente la differenza fra un grafo ed il suo trasposto è minima, essa può risultare più importante dal punto di vista dell'informatica, a seconda di come il grafo viene rappresentato. Ad esempio, per un webgraph (ovvero un grafo che descrive i collegamenti fra le pagine del World Wide Web) è semplice determinare i link uscenti da un nodo, ma è piuttosto difficile determinare quelli entranti, mentre con un grafo trasposto è vero l'opposto.

Di conseguenza, nello sviluppo di algoritmi sui grafi, può essere utile costruire il trasposto di un grafo, rendendolo in una forma più adatta alle operazioni che dovrebbero essere effettuate su di esso. Un esempio è l'algoritmo di Kosaraju per le componenti fortemente connesse, che applica una ricerca in profondità due volte, una sul dato fornito ed una su quello trasposto. Altro esempio può essere l'algoritmo di PageRank, in cui per ogni pagina è necessario conoscere quali sono i nodi contenenti almeno un link ad essa.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su grafo trasposto