Le graphe transposé

Le graphe transposé.

Le transposé d'un graphe orienté $G$ est le graphe qui a les mêmes sommets et dont chaque arc $(u,v)$ de $G$ est remplacé par l'arc $(v,u)$.

• Écrire une fonction transpose(G) qui renvoie le transposé d'un graphe donné par listes d'adjacence (dictionnaire de listes de successeurs). Quel est son coût ?
• Dans un graphe du web, à quoi sert le transposé ?
• Un moteur de recherche indexe $n=10^6$ pages reliées par $m=10^7$ liens. Comparer la place occupée par une matrice d'adjacence et par des listes d'adjacence.