Graphe couronne
From Wikipedia, the free encyclopedia
| Graphe couronne | |
 Graphes couronnes avec six, huit ou dix sommets. | |
| Notation | |
|---|---|
| Nombre de sommets | |
| Nombre d'arêtes | |
| Distribution des degrés | |
| Rayon | |
| Diamètre | |
| Maille | |
| Nombre chromatique | |
| Propriétés | Régulier Biparti Symétrique Distance-transitif |
modifier  |
|
En théorie des graphes, une branche des mathématiques, un graphe couronne à 2 n sommets est un graphe non orienté comportant deux jeux de sommets ui et vi reliés par une arête de ui à vj à chaque fois que i ≠ j.
Le graphe couronne à six sommets est un graphe cycle.
Le graphe couronne à huit sommets est le graphe hexaédrique, celui qui décrit les sommets et les arêtes d'un cube.
Autres façons de voir le graphe couronne
Le graphe couronne peut être vu comme un graphe biparti complet d'où l'on aurait retiré les arêtes formant un couplage parfait (les arêtes horizontales absentes sur la figure).
On peut aussi le voir comme la double couverture bipartie (en) d'un graphe complet.
Si l'on considère un ensemble à n éléments et tous ses sous-ensembles à 1 ou à n - 1 éléments, le graphe couronne montre toutes les possibilités qu'un de ces sous-ensembles en contienne un autre. Cela fait du graphe couronne un graphe biparti de Kneser Hn, 1.
Propriétés
Le nombre d'arêtes d'un graphe couronne est le nombre oblong n (n − 1).
Le nombre achromatique est n : on obtient une coloration complète en attribuant n couleurs aux sommets d'une des partitions, les mêmes n couleurs aux sommets de l'autre partition et en prenant des couleurs identiques pour les sommets non reliés[1].
Les graphes couronne sont symétriques et distance-transitifs.
Le graphe complémentaire du graphe couronne à 2 n sommets est le graphe qui décrirait les mouvements possibles d'une tour sur un échiquier à n rangées et à 2 colonnes (graphe de la tour (en)).
