Graphe roue

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe roue
Image illustrative de l'article Graphe roue
Quelques exemples de graphe roue.

Notation W_n
Nombre de sommets n
Nombre d'arêtes 2(n-1)
Distribution des degrés n-1 sommets de degré 3
1 sommet de degré n-1
Diamètre 2 pour n>4
1 pour n=4
Maille 3
Nombre chromatique 3 si n est impair
4 si n est pair
Propriétés Hamiltonien
Planaire
Autodual

En théorie des graphes, le graphe roue Wn est un graphe d'ordre n\geq 4 formé en ajoutant un sommet "centre" connecté à tous les sommets du graphe cycle Cn-1[1]. La notation Wn provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent Wn-1, faisant référence à la longueur du cycle.

Propriétés[modifier | modifier le code]

Propriétés générales[modifier | modifier le code]

Pour les valeurs impaires de n, le graphe Wn est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue Wn n'est pas parfait.

Le nombre de cycles dans le graphe roue Wn est égal à n^2-3n+3 (suite A002061 de l'OEIS) : 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, 273, 307, 343, 381, 421, 463, 507 (pour n=4, 5, 6,…). De plus le graphe roue contient toujours un cycle hamiltonien. Quel que soit n, sa maille, la longueur de son plus court cycle, est 3.

Les cycles du graphe roue W4 (le graphe tétraédrique).

Le graphe roue est planaire. Il a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête n'en croise une autre. À partir de cette représentation, il est possible de définir son graphe dual. C'est le graphe dont les sommets correspondent aux faces du graphe roue et où deux sommets sont adjacents s'ils correspondent à deux faces adjacentes. Le dual du graphe roue Wn est Wn lui-même, faisant du graphe roue un graphe autodual. Tout graphe planaire maximal autre que le graphe complet K4 = W4, contient comme sous-graphe ou W5 ou W6.

W7 est le seul graphe roue à être distance-unité[2].

Le graphe roue W6 est un contre-exemple à une conjecture de Paul Erdős sur la théorie de Ramsey. Erdős avait conjecturé que le graphe complet avait le plus petit nombre de Ramsey parmi tous les graphes avec le même nombre chromatique, mais Faudree et McKay montrèrent en 1993 que W6 a un nombre de Ramsey égal à 17 alors que le graphe complet avec le même nombre chromatique, K4, a un nombre de Ramsey égal à 18[3]. En effet, pour tout graphe G d'ordre 17, G ou son complément contient un sous-graphe isomorphe à W6, alors que ni le graphe de Paley d'ordre 17 ni son complément ne contiennent un sous-graphe isomorphe à K4.

Coloration[modifier | modifier le code]

Pour les valeurs impaires de n, le graphe Wn a un nombre chromatique de 3 : les sommets du cycle Cn-1 peuvent être colorées avec deux couleurs et le centre se voit attribuer la troisième couleur. Pour n pair le graphe à un nombre chromatique égal à 4 : les sommets du cycle Cn-1 nécessitent trois couleurs et le centre se voit attribuer la quatrième couleur.

Il est possible de compter les colorations distinctes d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs à au nombre chromatique du graphe et est de degrés n. Il est égal à :

P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n(x-2)})

Voir aussi[modifier | modifier le code]

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

  1. (en) Eric W. Weisstein, « Wheel Graph », MathWorld
  2. (en) Fred Buckley et Frank Harary, On the euclidean dimension of a wheel, vol. 4,‎ 1988 (DOI 10.1007/BF01864150), p. 23–30
  3. (en) Ralph J. Faudree et Brendan D. McKay, A conjecture of Erdős and the Ramsey number r(W, vol. 13,‎ 1993 (lire en ligne), p. 23–31