Graphe complet - Définition et Explications
Un graphe complet est un graphe dont les sommets sont tous reliés deux à deux par une arête. Dans un graphe G, on nomme clique un sous-graphe complet de G, c'est-à-dire une partie de l'ensemble des sommets de G telle que le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) induit (L'induit est un organe généralement électromagnétique utilisé en électrotechnique chargé de...) par G sur cette partie soit un graphe complet (Un graphe complet est un graphe dont les sommets sont tous reliés deux à deux par une arête....). Un des problèmes centraux de la théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux...) consiste à chercher la clique ( En théorie des graphes, dans les ouvrages de référence, une clique est un ensemble de sommets...) de taille maximum dans un graphe.
Un graphe complet à n sommets contient 
arêtes. On note Kn le graphe complet d'ordre n, c'est-à-dire contenant n sommets.
Le graphe K5 est un exemple minimal de graphe non-planaire.
 K1 |
 K2 |
 K3 |
 K4 |
 K5 |
 K6 |
 K7 |
 K8 |