Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe de Clebsch
Résumé
Le graphe de Clebsch est, en théorie des graphes, un graphe 5-régulier possédant 16 sommets et 40 arêtes. Il a été nommé ainsi à cause de son lien avec la découverte par Alfred Clebsch en 1868. On le connait aussi sous le nom de graphe de Greenwood–Gleason, à cause des travaux de Robert E. Greenwood et Andrew Gleason en 1955.
vignette|gauche|Construction du graphe de Clebsch depuis l'hypercube.
On peut construire le graphe de Clebsch en reliant par huit nouvelles arêtes les sommets opposés d'un hypercube en quatre dimensions (c'est-à-dire les sommets à distance quatre l'un de l'autre).
Une autre construction est de fusionner les sommets opposés de l'hypercube en cinq dimensions (donc les sommets à une distance cinq l'un de l'autre).
La construction historique est la suivante :
on représente les 16 droites contenues dans la quartique de Clebsch par 16 sommets d'un graphe ;
on relie deux de ces sommets si et seulement si les droites correspondantes ne sont ni parallèles ni sécantes.
On obtient également le graphe de Clebsch en représentant les éléments du corps fini GF(16) par des sommets, et en les reliant lorsque leur différence dans GF(16) est un nombre cubique.
vignette|Le graphe de Clebsch est hamiltonien.
Le graphe de Clebsch est un graphe fortement régulier de paramètres .
Le diamètre du graphe de Clebsch, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 4, c'est donc un graphe sans triangle. Il s'agit d'un graphe 5-sommet-connexe et d'un graphe 5-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 5 sommets ou de 5 arêtes.
Le graphe de Clebsch est également un graphe non-planaire, un graphe non-eulérien et un hamiltonien.
Le nombre chromatique du graphe de Clebsch est 4. C'est-à-dire qu'il est possible de le colorer avec 4 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.
Source officielle
À 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.