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 |