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 ≥ 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é est appelé un graphe -régulier ou graphe régulier de degré .
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
Portail de l'informatique théorique
Portail des mathématiques