Voir la source de Graphe régulier

{{Familles de graphes définies par leurs automorphismes}}
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é (théorie des graphes)|degré]] ou valence. Un graphe régulier dont les sommets sont de degré <math>k</math> est appelé un graphe <math>k</math>-régulier ou graphe régulier de degré <math>k</math>.

== 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 (théorie des graphes)|couplage]] ; enfin, un graphe 2-régulier est un ensemble de [[Cycle (théorie des graphes)|cycles]] déconnectés. Un graphe 3-régulier est aussi appelé [[graphe cubique]].

<gallery>
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
</gallery>

== 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 <math>l</math> de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre <math>n</math> 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]] <math>K_m</math> est fortement régulier pour tout <math>m</math>

== Existence ==
Une condition nécessaire et suffisante pour l'existence d'un graphe <math>k</math>-régulier à <math>n</math> sommets est que <math>nk</math> soit pair et que <math>n \geq k+1</math><ref>{{Ouvrage |langue=en |prénom1=Ioan |nom1=Tomescu |titre=Problems in combinatorics and graph theory |lieu=New York |éditeur=Wiley |année=1985 |pages totales=335 |passage=212-213}}</ref>.

== Propriétés ==

Un théorème de [[Crispin Nash-Williams]] affirme que tout graphe <math>k</math>-régulier ayant <math>2k+1</math> sommets admet un [[cycle hamiltonien]]<ref>[http://vene.ro/blog/nash-williams-theorem-on-the-hamiltonian-property-of-some-regular-graphs.html Une preuve du théorème de Nash-Williams] et l'article original : 
{{article
 | titre=Valency sequences which force graphs to have Hamiltonian circuits
 | auteur = Crispin Nash-Williams
 | journal=University of Waterloo Research Report, Waterloo, Ontario
 | année =1969
}}.</ref>.

Soit <math>A</math> la [[matrice d'adjacence]] du graphe. Le graphe est régulier si et seulement si <math>\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}</math> est un [[vecteur propre]] de <math>A</math>. 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 de graphe|coloration]], le [[problème du voyageur de commerce]] et le [[problème du stable maximum]] sont [[NP-difficile|NP-difficiles]] pour les graphes réguliers et même pour les graphes ''k''-réguliers avec ''k'' fixé<ref>Pour ''k'' bien choisi, typiquement 3, 4 ou plus grand. Voir [http://www.graphclasses.org/classes/gc_1149.html la page ''k-regular, fixed k'' sur Graphclasses.org], pour un résumé et les références.</ref>.

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<ref>Voir {{harvsp|Luks|1982}}. Cet article a permis à {{lien|Eugene Luks}} de recevoir le [[prix Fulkerson]] en 1985. Une description de l'idée de l'algorithme peut être trouvé dans {{harvsp|Fortin|1996}}, section 2.3.</ref>.

=== Génération ===
Des graphes réguliers peuvent être générés en utilisant le logiciel GenReg<ref>M. Meringer, ''J. Graph Theory'', 1999, 30, 137.</ref>.

== Références ==
{{Références}}

== Voir aussi ==
=== Bibliographie ===
*{{article
 | nom1 = Luks
 | prénom1 = Eugene M.
 | titre = Isomorphism of graphs of bounded valence can be tested in polynomial time
 | périodique = Journal of Computer and System Sciences
 | volume = 25 | passage = 42-65
 | année = 1982
 | doi = 10.1016/0022-0000(82)90009-5}}.
*{{ouvrage |langue=en
 | titre = The graph isomorphism problem (Technical Report 96-20)
 | prénom1 = Scott | nom = Fortin
 | année = 1996
 | lieu = University of Alberta, Edmonton, Alberta, Canada
 | lire en ligne = http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=DB79582730C44F734B2FA2162C45C33C?doi=10.1.1.32.9419&rep=rep1&type=pdf
}}

===Articles connexes===
* [[Graphe birégulier]]

=== Liens externes ===
* {{MathWorld|nom_url=RegularGraph|titre=Regular Graph}}
* {{MathWorld|nom_url=StronglyRegularGraph|titre=Strongly Regular Graph}}
* {{en}} Nash-Williams, Crispin ([[1969]]), "Valency Sequences which force graphs to have Hamiltonian Circuits", ''University of Waterloo Research Report'', Waterloo, Ontario: University of Waterloo

{{portail|informatique théorique|mathématiques}}

[[Catégorie:Concept en théorie des graphes|Régulier]]
[[Catégorie:Famille de graphes|Régulier]]