Graphe complet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
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
Image illustrative de l'article Graphe complet

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

En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents, 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[modifier | modifier le code]

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 .

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[modifier | modifier le code]

Le nombre d'arêtes de est :

.

Le premier terme s'obtient en remarquant que la suppression d'un premier sommet de entraîne la suppression de arêtes, la suppression d'un deuxième sommet, la suppression de arêtes, et celle d'un i-ème sommet 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 marquages par sommet (c'est la formule générale de la demi-somme des degrés).

Le graphe complet 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 .

Le polynôme caractéristique du graphe complet est : . 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 est le plus petit graphe non planaire. Il sert dans les caractérisations des graphes planaires de Kazimierz Kuratowski et de Klaus Wagner.

Galerie[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. (en) Reinhard Diestel (de), Graph Theory [détail des éditions], chap. 1.1 (« Basics:Graphs »), p. 3.

Sur les autres projets Wikimedia :