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

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 $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

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

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.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.