- Graphe de Desargues
-
Graphe de Desargues 
Le graphe de DesarguesNombre 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
Parfaitmodifier 
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.
Sommaire
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.
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[2]. Avec ses 20 sommets, il est le plus petit graphe cubique nécessitant 6 croisements pour être dessiné sur le plan[3].
Coloriage
Le 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
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[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 du graphe de Desargues est : (x − 3)(x − 2)4(x − 1)5(x + 1)5(x + 2)4(x + 3).
Galerie
-
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
- (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
Catégorie :- Graphe remarquable
-
Wikimedia Foundation. 2010.
