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.
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.
Explore les intégrales de surface, en mettant l'accent sur l'interprétation physique et les calculs mathématiques dans les champs et domaines vectoriels.
Analyse un modèle macroéconomique axé sur la part du revenu du travail et les effets des chocs de productivité sur le PIB, la consommation, l’investissement et les cours des actions.
Explore le lemme de régularité Szemerédi, la régularité électronique dans les graphes bipartites, la structure des supergraphes et les techniques d'induction.
This course provides students with a working knowledge of macroeconomic models that explicitly incorporate financial markets. The goal is to develop a broad and analytical framework for analyzing the
En théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle. Le théorème de Mantel, cas particulier du théorème de Turán, est : La famille des graphes sans triangle, contient notamment les graphes acycliques et est contenue dans les graphes sans diamant. Les graphes sans triangle peuvent être reconnus en temps , où est le nombre d'arêtes. De façon plus générale, on peut reconnaître les graphes n'ayant pas de cycles d'une certaine longueur (fixé dans l'algorithme), en temps (avec le nombre de sommets) ou en temps .
We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...
Elsevier2024
Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs.However, research on relational representation learning has so far mostly focused on the ...
This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...