Graphe transposé — Wikipédia

En théorie des graphes, le graphe transposé ${\displaystyle G^{T}}$, ou graphe inverse^[1], d'un graphe orienté ${\displaystyle G=(V,A)}$ est obtenu en conservant tous les nœuds de ${\displaystyle V}$et en inversant tous les arcs de ${\displaystyle A}$. Autrement dit, ${\displaystyle G^{T}=(V,A^{T})}$ avec ${\displaystyle A^{T}=\{(y,x)\mid (x,y)\in A\}}$.

Cette notion ne doit pas être confondue avec celle de graphe complémentaire ou inversé, pour les graphes non-orientés.

• Le transposé du transposé d'un graphe ${\displaystyle G}$ est le graphe ${\displaystyle G}$ .
• La matrice d'incidence du graphe transposé est la transposée de la matrice d'incidence du graphe original. Un graphe égal à son transposé est dit symétriquegraphe symétrique.

Certains algorithmes utilisent le transposé du graphe d'entrée, par exemple l'algorithme de Kosaraju effectue un parcours en profondeur du graphe et de son transposé.

• Automate transposé, la notion analogue pour les automates finis.
• Relation binaire réciproque

• Portail des mathématiques
• Portail de l'informatique théorique