Graphe de Dürer

Un article de Wikipédia, l'encyclopédie libre.

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é

Le graphe de Dürer est, en théorie des graphes, un graphe possédant 12 sommets et 18 arêtes.

Propriétés[modifier | modifier le code]

Construction[modifier | modifier le code]

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 | modifier le code]

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 | modifier le code]

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 | modifier le code]

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 | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]