Graphe transposé

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\}}$.

Un graphe et son transposé.

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

Propriété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étrique.

Applications

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é.

Voir aussi

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

Notes et références

1. Les deux termes sont utilisés, voir Olivier Carton, « Algorithmes sur les graphes » pour graphe transposé, et Jean-Charles Régin et Arnaud Malapert, « Théorie des graphes », pour graphe inverse.

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