Graphe complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe complet
Image illustrative de l'article Graphe complet
K_5

Notation K_n
Nombre de sommets n
Nombre d'arêtes n(n-1)/2
Distribution des degrés (n-1)-régulier
Diamètre 1
Maille ∞ si n = 1 ou 2
3 si n > 2
Nombre chromatique n
Propriétés Hamiltonien, symétrique, régulier

En théorie des graphes, le graphe complet K_n est l'unique graphe à isomorphisme près possédant n sommets tous reliés deux à deux par une arête.

Dans un graphe G quelconque, on appelle clique un sous-ensemble de sommets induisant un sous-graphe complet de G. Rechercher une clique de taille maximum dans un graphe est un problème classique en théorie des graphes. Il est NP-complet.

Le graphe K_5 est le plus petit graphe non planaire. Il sert dans les caractérisations des graphes planaires de Kazimierz Kuratowski et de Klaus Wagner.

La notion de graphe biparti complet existe également. Mais un graphe biparti complet n'est pas un graphe complet.

Propriétés[modifier | modifier le code]

Le nombre d'arêtes de K_n est :

 \sum_{i=1}^{n} \left(n-i\right) =  \frac{n(n-1)}{2}.

Le premier terme s'obtient en remarquant que la suppression d'un premier sommet de K_n entraîne la suppression de n-1 arêtes, la suppression d'un deuxième sommet, la suppression de n-2 arêtes, et celle d'un i-ème sommet n-i arêtes. Le deuxième terme s'obtient par la même opération en marquant les arêtes au lieu de les supprimer, chaque arête est alors marquée deux fois et l'on fait n-1 marquages par sommet (c'est la formule générale de la demi-somme des degrés).

Le graphe complet K_n est symétrique : il est sommet-transitif, arête-transitif et arc-transitif. Cela signifie que son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets, de ses arêtes et de ses arcs. Ce groupe d'automorphismes est de cardinal n! et est isomorphe au groupe symétrique S_n.

Le polynôme caractéristique du graphe complet K_n est : (x-n+1) (x+1)^{n-1}. Ce polynôme caractéristique n'admet que des racines entières. Le graphe complet est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Galerie[modifier | modifier le code]

Pour chacun des graphes complets de 1 à 12 sommets, est indiqué le nombre de ses arêtes.