En théorie des graphes, le graphe transposé , ou graphe inverse Les deux termes sont utilisés, voir pour graphe transposé, et , pour graphe inverse., d'un graphe orienté est obtenu en conservant tous les nœuds de et en inversant tous les arcs de . Autrement dit, avec .
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
Catégorie:Concept en théorie des graphes Transposé Catégorie:Opération sur les graphes