Aller au contenu

Graphe complet

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

Graphe complet
Image illustrative de l’article Graphe complet
K5

Notation Kn
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, 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

[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 Kn.

Certaines sources affirment que la lettre K de cette notation représente le mot allemand komplett[2], mais le nom allemand d'un graphe complet, vollständiger Graph, 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

[modifier | modifier le code]

La graphe Kn est régulier de degré n−1 et a n(n−1)2 arêtes[4].

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

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

Conjectures

[modifier | modifier le code]

Nombre de croisements

[modifier | modifier le code]

On note cr(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 Kn, que Richard K. Guy a publiée en 1960[5]. On sait qu'il existe toujours un tracé avec

cr(Kn)≤14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋

croisements (suite A000241 de l'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[6].

Saaty a en outre vérifié que cette formule donne le nombre optimal de croisements pour n ≤ 10 et Pan et Richter ont montré qu'elle était également optimale pour n = 11, 12[7].

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, Graph Theory [détail de l’édition], chap. 1.1 (« The Basics: Graphs »), p. 3
  2. ↑ (en) David Gries et Fred B. Schneider, A logical approach to discrete math, Springer-Verlag, coll. « Texts and monographs in computer science », (ISBN 978-0-387-94115-8 et 978-3-540-94115-6, lire en ligne Accès libre), p. 436
  3. ↑ (en) Thomas L Pirnot, Mathematics all around, Addison Wesley, (ISBN 9780201308150, lire en ligne Accès libre), p. 154
  4. ↑ Weisstein.
  5. ↑ R. K. Guy, « A combinatorial problem », Nabla (Bulletin of the Malayan Mathematical Society), vol. 7,‎ , p. 68–72
  6. ↑ T.L. Saaty, « The minimum number of intersections in complete graphs », Proceedings of the National Academy of Sciences of the United States of America, vol. 52,‎ , p. 688–690 (PMID 16591215, PMCID 300329, DOI 10.1073/pnas.52.3.688, Bibcode 1964PNAS...52..688S)
  7. ↑ Shengjun Pan et R. Bruce Richter, « The crossing number of K11 is 100 », Journal of Graph Theory, vol. 56, no 2,‎ , p. 128–134 (DOI 10.1002/jgt.20249, MR 2350621).

Sur les autres projets Wikimedia :

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]