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Ă© est appelĂ© un graphe -rĂ©gulier ou graphe rĂ©gulier de degrĂ© .
Familles de graphes définies par leurs automorphismes | ||||
---|---|---|---|---|
distance-transitif | â | distance-rĂ©gulier | â | fortement rĂ©gulier |
â | ||||
symĂ©trique (arc-transitif) | â | t-transitif, (t â„ 2) | symĂ©trique gauche (en) | |
â | ||||
(si connexe) sommet-transitif et arĂȘte-transitif |
â | rĂ©gulier et arĂȘte-transitif | â | arĂȘte-transitif |
â | â | â | ||
sommet-transitif | â | rĂ©gulier | â | (si biparti) birĂ©gulier |
â | ||||
graphe de Cayley | â | zĂ©ro-symĂ©trique | asymĂ©trique |
Exemples
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)
- graphe infini 2-régulier
Graphes fortement réguliers
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
Existence
Une condition nécessaire et suffisante pour l'existence d'un graphe -régulier à sommets est que soit pair et que [1].
Propriétés
Un théorÚme de Crispin Nash-Williams affirme que tout graphe -régulier ayant sommets admet un cycle hamiltonien[2].
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.
Aspects algorithmiques
Optimisation combinatoire
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Ă©[3].
Par contre le problĂšme de l'isomorphisme de graphes peut ĂȘtre dĂ©cidĂ© en temps polynomial sur les graphes de degrĂ© bornĂ©, par exemple les graphes rĂ©guliers[4].
Génération
Des graphes rĂ©guliers peuvent ĂȘtre gĂ©nĂ©rĂ©s en utilisant le logiciel GenReg[5].
Références
- (en) Ioan Tomescu, Problems in combinatorics and graph theory, New York, Wiley, , 335 p., p. 212-213
- Une preuve du thĂ©orĂšme de Nash-Williams et l'article original : Crispin Nash-Williams, « Valency sequences which force graphs to have Hamiltonian circuits », University of Waterloo Research Report, Waterloo, Ontario,â .
- Pour k bien choisi, typiquement 3, 4 ou plus grand. Voir la page k-regular, fixed k sur Graphclasses.org, pour un résumé et les références.
- Voir Luks 1982. Cet article a permis Ă Eugene Luks (en) de recevoir le prix Fulkerson en 1985. Une description de l'idĂ©e de l'algorithme peut ĂȘtre trouvĂ© dans Fortin 1996, section 2.3.
- M. Meringer, J. Graph Theory, 1999, 30, 137.
Voir aussi
Bibliographie
- Eugene M. Luks, « Isomorphism of graphs of bounded valence can be tested in polynomial time », Journal of Computer and System Sciences, vol. 25,â , p. 42-65 (DOI 10.1016/0022-0000(82)90009-5).
- (en) Scott Fortin, The graph isomorphism problem (Technical Report 96-20), University of Alberta, Edmonton, Alberta, Canada, (lire en ligne)
Articles connexes
Liens externes
- (en) Eric W. Weisstein, « Regular Graph », sur MathWorld
- (en) Eric W. Weisstein, « Strongly Regular Graph », sur 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