Graphe de Desargues - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
| Graphe de Desargues | |
|---|---|
| Nombre de sommets | 20 |
| Nombre d'arêtes | 30 |
| Distribution des degrés | 3-régulier |
| Rayon | 5 |
| Diamètre | 5 |
| Maille | 6 |
| Automorphismes | 240 (S5× Z/2Z) |
| Nombre chromatique | 2 |
| Indice chromatique | 3 |
| Propriétés | Hamiltonien Cubique Symétrique Parfait |
| modifier | |
En théorie des graphes, le graphe de Desargues est un graphe cubique symétrique possédant 20 sommets et 30 arêtes. Il doit son nom à Girard Desargues.
Construction
Le graphe de Desargues est isomorphe au graphe biparti de Kneser H(5,2) et au graphe généralisé de Petersen GP(10,3). C'est aussi le graphe d'incidence de la configuration de Desargues.
Le graphe de Desargues est hamiltonien et peut être décrit par la notation LCF : [5,−5,9,−9]5.
Galerie
| Le graphe de Desargues coloré de façon à mettre en valeur certains cycles. | Les arêtes du graphe de Desargues peuvent êtres colorées avec 3 couleurs. | Le nombre chromatique du graphe de Desargues est 2. |
Propriétés
Propriétés générales
Le diamètre du graphe de Desargues, l'excentricité maximale de ses sommets, est 5, son rayon, l'excentricité minimale de ses sommets, est 5 et sa maille, la longueur de son plus court cycle, est 6. 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.
Le graphe de Desargues n'est pas planaire. En fait pour le dessiner sur un plan il faut nécessairement que plusieurs arêtes se croisent. Il est possible de le dessiner avec seulement 6 croisements et ce nombre est minimal. Avec ses 20 sommets, il est le plus petit graphe cubique nécessitant 6 croisements pour être dessiné sur le plan.
Coloriage
Le nombre chromatique du graphe de Desargues est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de tel façon que deux sommets reliés par une arêtes soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 1-coloration valide du graphe.
L'indice chromatique du graphe de Desargues est 3. Il existe donc une 3-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommets soient toujours de couleurs différentes. Ce nombre est minimal.
Propriétés algébriques
Le graphe de Desargues est symétrique, c'est-à-dire que son groupe d'automorphisme agit transitivement sur ses arêtes, ses sommets et ses arcs. Son groupe d'automorphisme est d'ordre 240 et est isomorphe à S5× Z/2Z, le produit direct du groupe symétrique S5 avec l'unique groupe d'ordre 2. Seuls deux graphes cubiques symétriques à 20 sommets existent et 20 est le plus petit ordre où il existe deux graphes cubiques symétriques distincts : F20A et F20B selon la notation du Foster Census. F20A est le graphe dodécaédrique, F20B est le graphe de Desargues. Aux ordres 4, 6, 8, 10, 14, 16 et 18 il n'existe qu'un seul graphe cubique symétrique.
Le polynôme caractéristique du graphe de Desargues est : (x − 3)(x − 2)4(x − 1)5(x + 1)5(x + 2)4(x + 3).
