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}$.

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 ${\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}$

Existence

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].

Propriétés

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.

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

1. (en) Ioan Tomescu, Problems in combinatorics and graph theory, New York, Wiley, 1985, 335 p., p. 212-213
2. 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,‎ 1969.
3. 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.
4. 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.
5. 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,‎ 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)

Articles connexes

• Graphe birégulier

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

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