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

  • 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 antisymétrique (en).

ApplicationsModifier

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 aussiModifier

Notes et référencesModifier

  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.