Graphe complet

Modèle:Infobox Graphe

En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens).

Définitions

Un graphe complet est un graphe dont tous les sommets sont adjacents^[1]. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre $n$ , que l'on note $K_{n}$ .

Certaines sources affirment que la lettre $K$ de cette notation représente le mot allemand Modèle:Langue^[2], mais le nom allemand d'un graphe complet, Modèle:Langue, ne contient pas la lettre $K$ . D'autres affirment que la notation honore les contributions de Kazimierz Kuratowski à la théorie des graphes^[3].

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.

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

Propriétés

Le nombre d'arêtes de $K_{n}$ est :

\sum_{i = 1}^{n} (n - i) = \sum_{i = 1}^{n - 1} i = \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).

On peut également obtenir cette formule en voyant le nombre d’arêtes comme le nombre de couples distincts que l’on peut former avec $n$ nœuds, soit $(\binom{n}{2})$ arêtes, ce qui vaut bien $\frac{n (n - 1)}{2}$ .

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.

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.

Conjectures

Nombre de croisements

Modèle:Article détaillé On note $c r (G)$ le nombre de croisements du graphe $G$ , le nombre minimal de croisements parmi les tracés possibles de $G$ . A. Hill et J. Ernest ont conjecturé une valeur pour le nombre de croisements du graphe complet $K_{n}$ , que Richard K. Guy a publiée en 1960^[4]. On sait qu'il existe toujours un tracé avec

cr (K_{n}) \leq \frac{1}{4} ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ ⌊ \frac{n - 2}{2} ⌋ ⌊ \frac{n - 3}{2} ⌋

croisements (Modèle:OEIS). Il est conjecturé que l'inégalité est en fait une égalité. Une formulation indépendante de la même conjecture a été faite par Thomas L. Saaty en 1964^[5].

Saaty a en outre vérifié que cette formule donne le nombre optimal de croisements pour Modèle:Formule et Pan et Richter ont montré qu'elle était également optimale pour Modèle:Formule^[6].