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 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- Le complémentaire du complémentaire est le graphe original.
- La somme d'un graphe et de son complémentaire est le graphe complet[1].
- Une clique dans un graphe est un ensemble indépendant dans son graphe complémentaire.
- Les graphes auto-complémentaires sont les graphes qui sont isomorphes à leur complémentaire.
- Les cographes sont définis notamment par une opération de complémentation.
Notes et références
modifier- (en) Eric W. Weisstein, « Graph Complement », sur MathWorld
