Graphe complet
Un article de Wikipédia, l'encyclopédie libre.
 |
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.
|
Pour les graphes simples non-orientés, il n'existe – à isomorphisme près – qu'un graphe complet avec n sommets ; on note ce graphe Kn. C'est le graphe dont les sommets sont tous reliés deux à deux par une arête (voir les figures ci-dessous).
 K1 |
 K2 |
 K3 |
 K4 |
 K5 |
 K6 |
 K7 |
 K8 |
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.
Le nombre d'arêtes de Kn est
.
Le premier terme s'obtient en remarquant que la suppression d'un premier sommet de Kn entraine la suppression de n − 1 arêtes, la suppression d'un deuxième sommet, la suppression de n − 2 arêtes, et celle d'un i-ème sommet n − i 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 n − 1 marquages par sommet (c'est la formule générale de la demi-somme des degrés).
Le graphe K5 sert à la caractérisation des graphes non-planaires.
