b"\n_START_ARTICLE_\nGrafo trasposto\n_START_PARAGRAPH_\nNell'analisi matematica e algoritmica della teoria dei grafi, il grafo trasposto di un digrafo G \xc3\xa8 un altro grafo orientato definito sullo stesso insieme di nodi in cui l'orientamento di tutti gli archi \xc3\xa8 opposto rispetto al grafo di partenza. Per ogni arco  del grafo , il grafo trasposto di  contiene l'arco  e viceversa._NEWLINE_Il grafo risultante da tale operazione \xc3\xa8 generalmente denotato con  o .\n_START_SECTION_\nApplicazioni\n_START_PARAGRAPH_\nSe matematicamente la differenza fra un grafo ed il suo trasposto \xc3\xa8 minima, essa pu\xc3\xb2 risultare pi\xc3\xb9 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) \xc3\xa8 semplice determinare i link uscenti da un nodo, ma \xc3\xa8 piuttosto difficile determinare quelli entranti, mentre con un grafo trasposto \xc3\xa8 vero l'opposto._NEWLINE_Di conseguenza, nello sviluppo di algoritmi sui grafi, pu\xc3\xb2 essere utile costruire il trasposto di un grafo, rendendolo in una forma pi\xc3\xb9 adatta alle operazioni che dovrebbero essere effettuate su di esso. Un esempio \xc3\xa8 l'algoritmo di Kosaraju per le componenti fortemente connesse, che applica una ricerca in profondit\xc3\xa0 due volte, una sul dato fornito ed una su quello trasposto. Altro esempio pu\xc3\xb2 essere l'algoritmo di PageRank, in cui per ogni pagina \xc3\xa8 necessario conoscere quali sono i nodi contenenti almeno un link ad essa."