Graphe complémentaire

En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple est un graphe simple ayant les mêmes sommets et tel que deux sommets distincts de soient adjacents si et seulement s'ils ne sont pas adjacents dans [1].

Le graphe de Petersen, à gauche et son complémentaire, à droite.

Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé.

PropriétésModifier

Notes et référencesModifier