Graphe complémentaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le graphe de Petersen, à gauche et son complémentaire, à droite.

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

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