Graphe couronne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe couronne
Image illustrative de l'article Graphe couronne
Graphes couronnes avec six, huit ou dix sommets.

Notation S_n^0
Nombre de sommets 2 n
Nombre d'arêtes n (n - 1)
Distribution des degrés (n - 1) \text{ - régulier}
Rayon \left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{sinon}\end{array}\right.
Diamètre \left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{sinon}\end{array}\right.
Maille \left\{\begin{array}{ll}\infty & n \le 2\\ 6 & n = 3\\ 4 & \text{sinon}\end{array}\right.
Nombre chromatique \left\{\begin{array}{ll}1 & n = 1\\ 2 & \text{sinon}\end{array}\right.
Propriétés Régulier
Biparti
Symétrique
Distance-transitif (en)

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.

Exemples[modifier | modifier le code]

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[modifier | modifier le code]

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).

Les graphes couronnes à six, huit ou dix sommets vus comme des graphes bipartis.

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[modifier | modifier le code]

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 (en).

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)).

Applications[modifier | modifier le code]

L'ordre de coloration avec l'algorithme glouton est très important dans le cas du graphe couronne

Les règles traditionnelles de savoir-vivre imposent de placer les convives à table en alternant les hommes et les femmes et de manière à ce qu'aucun couple marié ne soit assis côte à côte. Les façons de placer les convives selon ces règles sont les cycles hamiltoniens d'un graphe couronne, où les sommets représentent les convives et les arêtes représentent les compatibilités entre ces convives. Déterminer toutes ces façons de placer les convives constitue le problème des ménages.

Les graphes couronnes fournissent un bon exemple pour montrer que l'algorithme glouton de coloration de graphe se comporte mal si l'on ne choisit pas bien l'ordre dans lequel on colore les sommets. En effet, si les sommets sont passés à l'algorithme glouton dans l'ordre (u0, v0, u1, v1, …, un, vn), l'algorithme utilisera n couleurs, alors que le nombre optimal de couleurs n'est que de 2. Cette construction est attribuée à D. S. Johnson[2], c'est pourquoi les graphes couronnes sont parfois appelés graphes de Johnson et notés Jn[3].

Références[modifier | modifier le code]

  1. (en) Amitabh Chaudhary et Sundar Vishwanathan, SODA '97: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms,‎ 1997, p. 558-563.
  2. (en) D. S. Johnson, Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae, Winnipeg,‎ 1974, p. 513-527
  3. (en) M. Kubale, Graph Colorings, American Mathematical Society,‎ 2004 (ISBN 0-8218-3458-4)

Lien externe[modifier | modifier le code]

(en) (en) Eric W. Weisstein et Simone Severini, « Crown Graph », MathWorld