Graphe complet

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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
modifier

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.

[modifier] Propriétés

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$ .