Graphe complémentaire

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 {\displaystyle G} est un graphe simple H {\displaystyle H} ayant les mêmes sommets et tel que deux sommets distincts de H {\displaystyle H} soient adjacents si et seulement s'ils ne sont pas adjacents dans G {\displaystyle 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

  • 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

  1. ↑ a et b (en) Eric W. Weisstein, « Graph Complement », sur MathWorld
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail des mathématiques