Graphe roue
De Wikipedia, l'encyclopédie encyclopedia
En théorie des graphes, le graphe roue Wn est un graphe d'ordre 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.
Faits en bref Notation, Nombre de sommets ...
Graphe roue | |
Quelques exemples de graphe roue. | |
Notation | |
---|---|
Nombre de sommets | |
Nombre d'arêtes | |
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 |
modifier |
Fermer