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[1].

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és[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a et b (en) Eric W. Weisstein, « Graph Complement », MathWorld