Graphe transposé

En théorie des graphes, le graphe transposé $G^{T}$ , ou graphe inverse^[1], d'un graphe orienté $G=(V,A)$ est obtenu en conservant tous les nœuds de $V$ et en inversant tous les arcs de $A$ . Autrement dit, $G^{T}=(V,A^{T})$ avec $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.

Propriétés[modifier | modifier le code]

Le transposé du transposé d'un graphe $G$ est le graphe $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.

Applications[modifier | modifier le code]

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[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

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

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

[1]