Graphe transposé
En théorie des graphes, le graphe transposé , ou graphe inverse[1], d'un graphe orienté est obtenu en conservant tous les nœuds de et en inversant tous les arcs de . Autrement dit, avec .
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 est le graphe .
- 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
- 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
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.