Graphe complet - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs 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...) 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 \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.

Cet article vous a plu ? Partagez-le sur les réseaux sociaux avec vos amis !
Page générée en 0.058 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