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
Image illustrative de l’article 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é

Propriétés

modifier

Construction

modifier

Le 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

modifier

Le 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

modifier

Le 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

modifier

Le 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

modifier

Liens internes

modifier

Liens externes

modifier

Références

modifier