Graphe de Desargues
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En théorie des graphes, le graphe de Desargues est un graphe cubique symétrique possédant 20 sommets et 30 arêtes[1]. Il doit son nom à Girard Desargues.
| Graphe de Desargues | |
 Le 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  |
|
Construction
modifierLe graphe de Desargues est isomorphe au graphe biparti de Kneser 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.
Propriétés
modifierPropriétés générales
modifierLe 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[2]. Avec ses 20 sommets, il est le plus petit graphe cubique nécessitant 6 croisements pour être dessiné sur le plan[3].
Coloration
modifierLe nombre chromatique du graphe de Desargues 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 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 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 graphe de Desargues est symétrique, c'est-à-dire que son groupe d'automorphismes 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[4]. 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[5].
Le polynôme caractéristique de la matrice d'adjacence du graphe de Desargues est : . Le graphe de Desargues est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.
Galerie
modifier-
Le graphe de Desargues coloré de façon à mettre en valeur certains cycles. -
Les arêtes du graphe de Desargues peuvent être colorées avec 3 couleurs. -
Le nombre chromatique du graphe de Desargues est 2.
Références
modifier- (en) Weisstein, Eric W. "Desargues Graph" From MathWorld--A Wolfram Web Resource
- (en) Weisstein, Eric W. "Graph Crossing Number" From MathWorld--A Wolfram Web Resource
- (en) Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
- (en) Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002
- (en) Weisstein, Eric W. "Cubic Symmetric Graph" From MathWorld--A Wolfram Web Resource
