- Graphe régulier
-
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é k > est appelé un graphe k-régulier ou graphe régulier de degré k
Sommaire
Cas particuliers
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.
-
graphe 0-régulier
-
graphe 1-régulier
-
graphe 2-régulier
-
graphe de Petersen (graphe cubique particulier)
Un graphe fortement régulier est un graphe régulier où chaque paire de sommets adjacents a le même nombre l de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre n 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 Km est fortement régulier pour tout m
Propriétés
Un théorème de Crispin Nash-Williams affirme que tout graphe k régulier ayant 2k + 1 sommets admet un cycle Hamiltonien.
Soit A la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si
est un vecteur propre de A. Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe.Génération
Des graphes réguliers peuvent être générés en utilisant le logiciel GenReg[1].
Voir aussi
Références
- M. Meringer, J. Graph Theory, 1999, 30, 137.
Liens externes
- (en) Eric W. Weisstein, « Regular Graph », MathWorld
- (en) Eric W. Weisstein, « Strongly Regular Graph », MathWorld
- (en) Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo
Catégories :- Concept en théorie des graphes
- Famille de graphes
-
Wikimedia Foundation. 2010.
