Graphe de Desargues

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. Le 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. 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. 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. Le 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (16)

Cours associés (1)

Séances de cours associées (2)

Graphe de Desargues

Graphe de Nauru

En mathématiques, et plus précisément en théorie des graphes, le graphe de Nauru est un graphe 3-régulier possédant 24 sommets et 36 arêtes. Il a été nommé ainsi par David Eppstein d'après l'étoile à 12 branches ornant le drapeau de Nauru. Le diamètre du graphe de Nauru, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 6.

Desargues configuration

In geometry, the Desargues configuration is a configuration of ten points and ten lines, with three points per line and three lines per point. It is named after Girard Desargues. The Desargues configuration can be constructed in two dimensions from the points and lines occurring in Desargues's theorem, in three dimensions from five planes in general position, or in four dimensions from the 5-cell, the four-dimensional regular simplex. It has a large group of symmetries, taking any point to any other point and any line to any other line.

MATH-124: Geometry for architects I

Ce cours entend exposer les fondements de la géométrie à un triple titre : 1/ de technique mathématique essentielle au processus de conception du projet, 2/ d'objet privilégié des logiciels de concept

Explore les transformations géométriques, les propriétés invariantes et les relations moyennes dans la géométrie moderne.

Explore l'unicité des arbres, des groupes d'automorphisme, des graphiques Cayley-Abels et la construction de sous-groupes vertex-transitifs avec des actions locales prescrites.