Graphe de Herschel
| Graphe de Herschel | |
 Représentation du graphe de Herschel | |
| Nombre de sommets | 11 |
|---|---|
| Nombre d'arêtes | 18 |
| Distribution des degrés | 3 (8 sommets) 4 (3 sommets) |
| Rayon | 3 |
| Diamètre | 4 |
| Maille | 4 |
| Automorphismes | 12 |
| Nombre chromatique | 2 |
| Indice chromatique | 4 |
| Propriétés | Biparti Parfait Planaire |
modifier  |
|
Le graphe de Herschel est, en théorie des graphes, un graphe possédant 11 sommets et 18 arêtes.
Origine modifier
Le graphe de Herschel a été nommé en l'honneur de l'astronome Alexander Stewart Herschel (en), qui a écrit très tôt un article sur le jeu icosian game de William Rowan Hamilton. En effet, le graphe de Herschel décrit le graphe des arêtes du plus petit polytope convexe pour lequel ce jeu n'a pas de solution. L'article de Herschel ne décrit néanmoins des solutions du icosian game que pour les graphes des arêtes du tétraèdre régulier et de l'icosaèdre régulier, il ne décrit pas le graphe de Herschel[1].
Propriétés modifier
Propriétés générales modifier
Le diamètre du graphe de Herschel, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 4. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
Coloration modifier
Le nombre chromatique du graphe de Herschel est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.
L'indice chromatique du graphe de Herschel est 4. Il existe donc une 4-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
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 admet pour racines tous les entiers positifs ou nuls strictement inférieurs à 2 et est de degrés 11. Il est égal à : .
Propriétés algébriques modifier
Le groupe d'automorphismes du graphe de Herschel est un groupe d'ordre 12 isomorphe au groupe diédral D6, le groupe des isométries du plan conservant un hexagone. Ce groupe est constitué de 6 éléments correspondant aux rotations et de 6 autres correspondant aux réflexions.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Herschel est : .
Voir aussi modifier
Lien externe modifier
(en) Eric W. Weisstein, « Herschel Graph », sur MathWorld
Référence modifier
- (en) A. S. Herschel, « Sir Wm. Hamilton's Icosian Game », Quarterly Journal of Pure and Applied Mathematics, vol. 5, , p. 305 (lire en ligne)
