Ê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 régulier
Résumé
En théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré est appelé un graphe -régulier ou graphe régulier de degré .
Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés. Un graphe 3-régulier est aussi appelé graphe cubique.
Image:0-regulární graf na 6 vrcholech.png|graphe 0-régulier
Image:1-regulární graf na 6 vrcholech.svg|graphe 1-régulier
Image:2-regulární graf na 6 vrcholech.svg|graphe 2-régulier
Image:Petersen_graph_blue.svg |[[graphe de Petersen]] (graphe cubique particulier)
Image:Infinite-2-regular-graph.png|graphe infini 2-régulier
Un graphe fortement régulier est un graphe régulier où chaque paire de sommets adjacents a le même nombre de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre de voisins en commun. Les plus petits graphes qui sont réguliers sans être fortement réguliers sont le graphe cycle et le graphe circulant, tous deux à 6 sommets. Le graphe complet est fortement régulier pour tout
Une condition nécessaire et suffisante pour l'existence d'un graphe -régulier à sommets est que soit pair et que .
Un théorème de Crispin Nash-Williams affirme que tout graphe -régulier ayant sommets admet un cycle hamiltonien.
Soit la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si est un vecteur propre de . Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe.
De nombreux problèmes de graphes sont difficiles même si l'on se restreint à la classe des graphes réguliers. Plus précisément, la coloration, le problème du voyageur de commerce et le problème du stable maximum sont NP-difficiles pour les graphes réguliers et même pour les graphes k-réguliers avec k fixé.
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.