Graphe de Dürer
Le graphe de Dürer est, en théorie des graphes, un graphe possédant 12 sommets et 18 arêtes.
| Graphe de Dürer | |
 Représentation du graphe de Dürer. | |
| Nombre de sommets | 12 |
|---|---|
| Nombre d'arêtes | 18 |
| Distribution des degrés | 3 |
| Diamètre | 4 |
| Maille | 3 |
| Automorphismes | 12 (D6) |
| Nombre chromatique | 3 |
| Indice chromatique | 3 |
| Propriétés | Cubique Planaire Distance-unité |
modifier  |
|
Propriétés
modifierConstruction
modifierLe graphe de Dürer est ainsi nommé en référence au polyèdre représenté dans la Melencolia de Albrecht Dürer. C'est donc le squelette d'un rhomboèdre tronqué en deux de ses coins opposés. Ce solide possède, comme le graphe, six faces pentagonales et deux faces triangulaires.
On peut aussi plus simplement le considérer comme le squelette d'un cube tronqué en deux de ses coins opposés.
Le graphe de Dürer est aussi un cas de graphe de Petersen généralisé : il ressemble au graphe de Petersen en ce qu'on peut le dessiner avec un motif en étoile au centre et un motif en polygone régulier à l'extérieur, mais avec six sommets dans chaque motif au lieu de cinq.
Propriétés générales
modifierLe diamètre du graphe de Dürer, l'excentricité maximale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 3-sommet-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets.
Coloration
modifierLe nombre chromatique du graphe de Dürer est 3. C'est-à-dire qu'il est possible de le colorer avec 3 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 Dürer est 3. Il existe donc une 3-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.
Propriétés algébriques
modifierLe groupe d'automorphismes du graphe de Dürer est un groupe d'ordre 12 isomorphe au groupe diédral D6, le groupe des isométries du plan conservant un hexagone régulier. Ce groupe est constitué de 6 éléments correspondant aux rotations et de 6 autres correspondant aux réflexions.
Voir aussi
modifierLiens internes
modifierLiens externes
modifier- (en) Eric W. Weisstein, Dürer's Graph (MathWorld)
