Graphe de Desargues

Graphe de Desargues
Graphe de Desargues
DesarguesGraph.svg
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 Consultez la documentation du modèle

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

  1. ↑ (en) Weisstein, Eric W. "Desargues Graph" From MathWorld--A Wolfram Web Resource
  2. ↑ (en) Weisstein, Eric W. "Graph Crossing Number" From MathWorld--A Wolfram Web Resource
  3. ↑ (en) Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009
  4. ↑ (en) Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002
  5. ↑ (en) Weisstein, Eric W. "Cubic Symmetric Graph" From MathWorld--A Wolfram Web Resource

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Desargues de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Graphe de Nauru — Représentation du graphe de Nauru. Notation F24A Nombre de sommets 24 Nombre d arêtes 36 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe dodécaédrique — Représentation du graphe dodécaédrique. Nombre de sommets 20 Nombre d arêtes 30 Distribution des degrés 3 régulier Rayon …   Wikipédia en Français

  • Graphe symétrique — Le Graphe de Petersen est un graphe cubique symétrique. En théorie des graphes un graphe G est symétrique (ou arc transitif) si, étant donné deux paires de sommets reliés par une arête u1 v1 et u2 v2 de G, il existe un automorphisme de… …   Wikipédia en Français

  • Graphe distance-régulier — En théorie des graphes, un graphe est distance régulier si pour tous sommets , le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.… …   Wikipédia en Français

  • Graphe intégral — En théorie des graphes, un graphe intégral est un graphe dont le spectre de la matrice d adjacence ne contient que des entiers[1]. En d autres termes, les racines de son polynôme caractéristiques sont toutes entières. Leur étude fut introduite… …   Wikipédia en Français

  • Coloration de graphe (arêtes) — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

  • Coloration des aretes d'un graphe — Coloration des arêtes d un graphe Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une… …   Wikipédia en Français

  • Coloration des arêtes d'un graphe — Coloration des arêtes du graphe de Desargues avec trois couleurs. La coloration des arêtes d’un graphe entre dans la catégorie plus générale des problèmes de coloration de graphes, le but étant d’attribuer une couleur à chaque arête du graphe… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”