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és
- 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
- (en) Eric W. Weisstein, « Graph Complement », sur MathWorld
Portail de l'informatique théorique 
Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.