Ê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 Levi
Résumé
En mathématiques, et plus particulièrement en combinatoire, un graphe de Levi ou graphe d'incidence est un graphe biparti associé à une structure d'incidence.
À partir d'un ensemble de points et de droites dans une géométrie d'incidence ou une configuration géométrique, on forme un graphe avec un sommet par point, un sommet par droite et une arête pour chaque incidence entre un point et une droite. Ces graphes sont nommés d'après Friedrich Wilhelm Levi, qui les a décrit dans des publications en 1942.
Le graphe de Levi d'un système de points et de droites a généralement une maille au moins égal à six : un cycle de longueur 4 correspond à deux droites passant par les mêmes points. Inversement, tout graphe bipartite avec une maille d'au moins six peut être considéré comme le graphe de Levi d'une structure d'incidence abstraite. Les graphes de Levi des configurations sont biréguliers, et chaque graphe birégulier avec de maille de six ou plus peut être vu comme le graphe de Levi d'une configuration abstraite.
Des graphes de Levi peuvent également être définis pour d'autres types de structures d'incidence, tels que les incidences entre les points et les plans dans l'espace euclidien. Pour chaque graphe de Levi, il existe un hypergraphe équivalent, et vice versa.
Le graphe de Desargues est le graphe de Levi de la configuration de Desargues, composée de 10 points et 10 droites. Il y a 3 points sur chaque droite et 3 droites passant par chaque point. Le graphe de Desargues peut également être vu comme le graphe de Petersen généralisé G(10,3) ou le graphe de Kneser biparti avec les paramètres 5,2. Il est 3-régulier et a 20 sommets.
Le graphe de Heawood est le graphe de Levi du plan de Fano. Il est également connue sous le nom de (3,6)-cage, et est 3-régulier et a 14 sommets.
Le graphe de Möbius-Kantor est le graphe de Levi de la configuration de Möbius-Kantor, un système de 8 points et 8 droites qui ne peut pas être réalisé par des droites géométriques dans le plan euclidien. Il est 3-régulier et a 16 sommets.
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.