Graphe complet
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 recevoir l'induction de l'inducteur et de la transformer en électricité (générateur) ou en force (moteur).) 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. Dans un graphe G, on nomme clique un sous-graphe complet...). 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 acceptions :) consiste à chercher la clique ( En théorie des graphes, dans les ouvrages de référence, une clique est un ensemble de sommets deux-à-deux adjacents. Dans les armées,...) de taille maximum dans un graphe.

Un graphe complet à n sommets contient \frac{n \cdot (n-1)}{2} 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.

Page générée en 0.040 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique