Graphe complet

Graphe complet
Graphe complet
Complete graph K5.svg
K5
Notation Kn
Nombre de sommets n
Nombre d'arêtes n(n − 1) / 2
Distribution des degrés (n-1)-régulier
Diamètre 1
Maille ∞ si n = 1 ou 2
3 si n > 2
Nombre chromatique n
Propriétés Hamiltonien, symétrique, régulier
modifier Consultez la documentation du modèle

En théorie des graphes, le graphe complet Kn est l'unique graphe à isomorphisme près possédant n sommets tous reliés deux à deux par une arête.

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. Il est NP-complet.

Le graphe K5 est le plus petit graphe non planaire. Il sert dans les caractérisations des graphes planaires de Kazimierz Kuratowski et de Klaus Wagner.

La notion de graphe biparti complet existe également. Mais un graphe biparti complet n'est pas un graphe complet.

Propriétés

Le nombre d'arêtes de Kn est :

\sum_{i=1}^{n} \left(n-i\right) = \frac{n(n-1)}{2}.

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 complet Kn est symétrique : il est sommet-transitifs, arête-transitif et arc-transitif. Cela signifie que son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets, de ses arêtes et de ses arcs. Ce groupe d'automorphismes est de cardinal n! et est isomorphe au groupe symétrique Sn.

Galerie

Pour chacun des graphes complets de 1 à 12 sommets, est indiqué le nombre de ses arêtes.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe complet de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Graphe Complet — K5 Notation Kn Nombre de sommets n Nombre d arêtes n(n − 1) / 2 …   Wikipédia en Français

  • Graphe Planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… …   Wikipédia en Français

  • Graphe biparti complet — K3,2 Notation Km,n Nombre de sommets m + n …   Wikipédia en Français

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe roue — Quelques exemples de graphe roue. Notation Wn Nombre de sommets n Nombre d arêtes 2(n …   Wikipédia en Français

  • Graphe triangle — Représentation du graphe triangle. Notation C3, K3 Nombre de sommets 3 Nombre d arêtes 3 Distribution des degrés 2 ré …   Wikipédia en Français

  • Graphe Petersen — Graphe de Petersen Graphe de Petersen Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier… …   Wikipédia en Français

  • Graphe tétraédrique — Représentation du graphe tétraédrique. Nombre de sommets 4 Nombre d arêtes 6 Distribution des degrés 3 régulier Rayon 1 …   Wikipédia en Français

  • Graphe de Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes …   Wikipédia en Français

  • Graphe singleton — Représentation du graphe singleton. Nombre de sommets 1 Nombre d arêtes 0 Distribution des degrés 0 régulier Rayon 0 …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”