Graphe de Herschel

Graphe de Herschel
Graphe de Herschel
Herschel graph LS.svg
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 Consultez la documentation du modèle

Le graphe de Herschel est, en théorie des graphes, un graphe possédant 11 sommets et 18 arêtes. Il doit son nom à l'astronome Alexander Stewart Herschel (en) qui le découvrit en 1862[1].

Sommaire

Propriétés

Propriétés générales

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.

Coloriage

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 tels 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 à : (x − 1)x(x9 − 17x8 + 136x7 − 671x6 + 2254x5 − 5355x4 + 9002x3 − 10306x2 + 7254x − 2371).

Propriétés algébriques

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 du graphe de Herschel est : − x3( − 11 + x2)( − 3 + x2)( − 2 + x2)2.

Voir aussi

Lien externe

(en) Eric W. Weisstein, « Herschel Graph », MathWorld

Référence

  1. ↑ (en) A. S. Herschel, « Sir Wm. Hamilton's Icosian Game », dans Quarterly Journal of Pure and Applied Mathematics, vol. 5, 1862, p. 305 [texte intégral] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Herschel de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Naine Blanche — Traduction terminée White dwarf → …   Wikipédia en Français

  • Naines blanches — Naine blanche Traduction terminée White dwarf → …   Wikipédia en Français

  • PHOTOGRAPHIE — La perception de l’apparence du monde matériel par notre organe visuel a comme support la lumière visible ou les autres radiations électromagnétiques, rendues visibles par l’intermédiaire de phénomènes auxiliaires. L’emploi direct de l’ensemble… …   Encyclopédie Universelle

  • Photography — is the art, science and practice of creating durable images by recording light or other electromagnetic radiation, either electronically by means of an image sensor or chemically by means of a light sensitive material such as photographic… …   Wikipedia

  • Photograph — A photograph (often shortened to photo) is an image created by light falling on a light sensitive surface, usually photographic film or an electronic imager such as a CCD or a CMOS chip. Most photographs are created using a camera, which uses a… …   Wikipedia

  • Hamiltonian path — This article is about the overall graph theory concept of a Hamiltonian path. For the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph, see Hamiltonian path problem. A Hamiltonian cycle in a dodecahedron …   Wikipedia

  • Histoire Des Mathématiques — Article de la série Histoire des sciences Chronologie Chronologie des sciences Chronologie de l astronomie …   Wikipédia en Français

  • Histoire des mathematiques — Histoire des mathématiques Article de la série Histoire des sciences Chronologie Chronologie des sciences Chronologie de l astronomie …   Wikipédia en Français

  • Histoire des mathématiques — L’histoire des mathématiques s étend sur plusieurs millénaires et dans de nombreuses régions du globe allant de la Chine à l’Amérique centrale. Jusqu au XVIIe siècle, le développement des connaissances mathématiques s’effectue… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”