Ê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 Moore
Résumé
En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal.
Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes.
Un graphe de Moore est un graphe régulier de degré d et de diamètre k qui possède un nombre de sommets égal à la borne supérieure :
De façon générale, le nombre de sommets d'un graphe de degré maximal d et de diamètre k est inférieur ou égal à cette valeur. Un graphe de Moore possède donc une valeur maximale de sommets pour un degré et un diamètre donnés.
De façon alternative, un graphe de Moore est un graphe régulier de diamètre k et de maille 2k+1. Cette définition est équivalente à la précédente.
Il est possible de généraliser la définition pour permettre à un graphe de Moore d'être de maille paire. Dans ce cas, un graphe de Moore est un graphe régulier de degré d>2 et de maille m dont le nombre de sommets est égal à :
si m est pair, et
si m est impair.
Les graphes complets (de diamètre 1) sont des graphes de Moore. Parmi ceux-ci, les cycles impairs sont des graphes de Moore de degré 2. Les cliques sont des graphes de Moore de diamètre 1.
Le théorème d'Hoffman-Singleton stipule que tout graphe de Moore de maille 5 (et donc de diamètre 2) ne peut avoir qu'un degré 2, 3, 7 ou 57. Il s'agit du pentagone (degré 2 et 5 sommets), du graphe de Petersen (degré 3 et 10 sommets) et du graphe de Hoffman-Singleton (degré 7 et 50 sommets). L'existence d'un graphe de Moore de maille 5 et de degré 57 n'est pas connue; un tel graphe aurait 3 250 sommets.
Si la définition généralisée des graphes de Moore est prise en considération, ils incluent le graphe biparti complet de Kn,n de maille 4, le graphe de Heawood de degré 3 et de maille 6 et le graphe de Tutte–Coxeter de degré 3 et de maille 8. De façon générale, à part les graphes cités ci-dessus, tous les graphes de Moore sont de maille 5, 6, 8 ou 12.
Graphe régulier
Théorèm
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.