Graphe régulier

Familles de graphes définies par leurs automorphismes
distance-transitif	→	distance-régulier	←	fortement régulier
↓
symétrique (arc-transitif)	←	t-transitif, $(t \geq 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

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

Exemples modifier

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 modifier

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 $K_{m}$ est fortement régulier pour tout $m$

Existence modifier

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

Propriétés modifier

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

Soit $A$ la matrice d'adjacence du graphe. Le graphe est régulier si et seulement si ${\begin{bmatrix}1\\\vdots \\1\end{bmatrix}}$ est un vecteur propre de $A$ . Lorsque c'est un vecteur propre, il correspond à une valeur propre qui est égale au degré du graphe.

Aspects algorithmiques modifier

Optimisation combinatoire modifier

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 modifier

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

Références modifier

↑ (en) Ioan Tomescu, Problems in combinatorics and graph theory, New York, Wiley, 1985, 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,‎ 1969.
↑ 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 modifier

Bibliographie modifier

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 modifier

Graphe birégulier

Liens externes modifier

(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

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

[1]

[2]

[3]

[4]

[5]