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é ${\displaystyle k}$ est appelé un graphe ${\displaystyle k}$-régulier ou graphe régulier de degré ${\displaystyle k}$.

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

Un graphe fortement régulier est un graphe régulier où chaque paire de sommets adjacents a le même nombre ${\displaystyle l}$ de voisins en commun et où chaque paire de sommets non-adjacents a le même nombre ${\displaystyle 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 ${\displaystyle K_{m}}$ est fortement régulier pour tout ${\displaystyle m}$

Une condition nécessaire et suffisante pour l'existence d'un graphe ${\displaystyle k}$-régulier à ${\displaystyle n}$ sommets est que ${\displaystyle nk}$ soit pair et que ${\displaystyle n\geq k+1}$^[1].

Un théorème de Crispin Nash-Williams affirme que tout graphe ${\displaystyle k}$-régulier ayant ${\displaystyle 2k+1}$ sommets admet un cycle hamiltonien^[2].

Soit ${\displaystyle A}$ la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si ${\displaystyle {\begin{bmatrix}1\\\vdots \\1\end{bmatrix}}}$ est un vecteur propre de ${\displaystyle A}$. 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é^[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].

Des graphes réguliers peuvent être générés en utilisant le logiciel GenReg^[5].

• Eugene M. Luks, « Isomorphism of graphs of bounded valence can be tested in polynomial time », Journal of Computer and System Sciences, vol. 25,‎ 1982, 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, 1996 (lire en ligne)

• Graphe birégulier

• (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

• Portail de l'informatique théorique
• Portail des mathématiques