GéométrieObjet mathématique · Glossaire
Graphe complet
Un graphe complet sur n sommets est un graphe simple non orienté dans lequel toute paire de sommets distincts est reliée par exactement une arête. Il est noté Kₙ et possède n(n − 1)/2 arêtes. Le graphe complet K₃ est un triangle, K₄ est le graphe du tétraèdre, etc. Les graphes complets sont des objets de référence en théorie des graphes : Kₙ est le graphe le plus dense possible sur n sommets et sert de cas extrême dans de nombreux résultats combinatoires.
Sommaire
Ce que vous allez apprendre
- Reconnaître un graphe complet en contrôlant l'adjacence de chaque paire de sommets.
- Calculer n(n − 1)/2 arêtes et le degré n − 1 de chaque sommet.
- Construire K_5 et vérifier ses 10 arêtes par deux comptages.
- Distinguer graphe complet, graphe connexe, graphe biparti complet et sous-graphe complet.
- Interpréter correctement les croisements d'un dessin et le seuil non planaire K_5.
En clair
Placez cinq points sur une feuille, puis reliez chaque point aux quatre autres. Dès qu'une paire de points reste sans trait, le dessin n'est pas complet. Dès qu'un second trait relie la même paire, il ne représente plus un graphe simple.
Le graphe obtenu, noté K5, contient toutes les connexions possibles entre ses cinq sommets : dix arêtes au total. La position des points et les croisements du dessin ne changent pas les connexions.
Définition
Un graphe complet est un graphe simple et non orienté dont deux sommets distincts quelconques sont adjacents. « Simple » exclut les boucles et les arêtes multiples ; « non orienté » signifie qu'une arête n'a pas de sens de parcours. Si le nombre de sommets est noté n, le graphe complet correspondant se note Kn.
Chaque sommet de Kn est voisin des n − 1 autres et possède donc le degré n − 1. En comptant ces voisinages pour les n sommets, chaque arête apparaît deux fois, une fois depuis chacune de ses extrémités. Le nombre d'arêtes est ainsi . Aucun graphe simple non orienté à n sommets ne peut en avoir davantage.
Les premiers cas fixent les repères : K1 a un sommet et aucune arête, K2 a une arête, K3 forme un triangle. K4 est le graphe des quatre sommets et des six arêtes du tétraèdre ; le graphe lui-même n'est pas le solide.
De quoi c'est fait
Un graphe complet réunit trois éléments nécessaires. L'ensemble des sommets fournit les objets à relier. Les paires de sommets distincts déterminent toutes les connexions possibles. L'ensemble des arêtes contient exactement une arête pour chacune de ces paires.
Le nombre de sommets fixe donc à la fois le degré de chaque sommet et le nombre total d'arêtes. Réciproquement, une seule paire non reliée suffit à faire perdre la complétude. La position, la couleur ou la taille des sommets ne définissent pas Kn : seule compte l'adjacence. Ces données suffisent à construire le graphe et à calculer ses n(n − 1)/2 arêtes.
Un exemple, pas à pas
Construisons K5. Les données sont cinq sommets, un graphe simple non orienté et l'obligation de relier chaque paire distincte exactement une fois.
1. Depuis le premier sommet, traçons quatre arêtes vers les quatre autres.
2. Depuis le deuxième, l'arête vers le premier existe déjà ; ajoutons seulement les trois arêtes nouvelles. Il en reste ensuite deux depuis le troisième, puis une depuis le quatrième.
3. Le total vaut 4 + 3 + 2 + 1 = 10 arêtes. La figure matérialise ces dix paires sans attribuer de sens aux traits.
4. Contrôlons avec la formule : pour n = 5, n(n − 1)/2 = 5 × 4/2 = 10. Un second contrôle consiste à compter quatre arêtes incidentes à chacun des cinq sommets : les 20 incidences représentent bien 10 arêtes, chacune étant comptée deux fois.
En pratique
Pour vérifier qu'un réseau simple est complet, choisissez chaque sommet et contrôlez qu'il a exactement n − 1 voisins. Si un degré est inférieur, cherchez une paire non reliée ; inspecter toutes les arêtes une à une est alors inutile.
Pour déterminer le maximum d'arêtes possibles sur n sommets, utilisez Kn comme cas extrême. Si les boucles, les arêtes multiples ou les orientations sont autorisées, ce modèle n'est plus adapté et il faut préciser une autre famille de graphes.
Pour modéliser des rencontres où chaque participant affronte exactement une fois tous les autres, associez un sommet à chaque participant et une arête à chaque rencontre. Kn convient ; si seules certaines rencontres sont prévues, un graphe non complet décrit mieux le programme.
À ne pas confondre
Graphe complet et graphe connexe. Un graphe connexe exige seulement un chemin entre chaque paire de sommets ; un graphe complet exige une arête directe. Une chaîne de trois sommets est connexe, mais ses deux extrémités non adjacentes prouvent qu'elle n'est pas complète.
Graphe complet et graphe biparti complet. Dans un graphe biparti complet, toutes les arêtes relient deux groupes distincts et aucune ne joint deux sommets d'un même groupe. Avec deux sommets dans chaque groupe, K2,2 a quatre arêtes, alors que K4 en a six.
Graphe complet et sous-graphe complet. Un graphe peut ne pas être complet tout en contenant quelques sommets tous adjacents deux à deux. Trois sommets formant un triangle dans un réseau plus vaste constituent un sous-graphe complet K3, sans rendre complet le réseau entier.
Limites et pièges
Croisements trompeurs. Des arêtes qui se croisent sur la feuille ne créent pas de sommet si aucun sommet n'est marqué à l'intersection. K4 peut sembler croisé lorsqu'il est dessiné sur un cercle, mais un autre tracé le représente sans croisement.
Seuil de planarité. K5 ne peut pas être dessiné dans le plan sans croisement d'arêtes : c'est le premier graphe complet non planaire. Déplacer les cinq sommets ne résout donc pas le problème ; il faut accepter un croisement ou changer de surface.
Petits ordres. Pour n = 1, la condition portant sur les paires distinctes est satisfaite sans aucune arête, et la formule donne 0. Certains cadres admettent aussi K0, le graphe sans sommet ; il faut alors annoncer cette convention au lieu de la supposer.
Modification du cadre. Une boucle, deux arêtes parallèles ou des arcs orientés sortent de la définition de Kn. Le symptôme est qu'une paire n'est plus représentée par une unique arête non orientée ; il faut nommer le multigraphe ou le graphe orienté réellement étudié.
Pour aller plus loin
graphe biparti — Comparer les arêtes autorisées entre deux groupes avec les connexions toutes paires de Kn.
Sous-graphe — Préciser comment extraire des sommets et des arêtes, puis reconnaître un sous-graphe complet dans un réseau plus vaste.
arbre - graphe - — Opposer la densité maximale de Kn à une structure connexe sans cycle qui ne garde que n − 1 arêtes.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres