Graphe régulier
# 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) |
| $_{(siconnexe)}$ sommet-transitif et arête-transitif | → | régulier et arête-transitif | → | arête-transitif |
| sommet-transitif | → | régulier | → | $_{(sibiparti)}$ 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

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

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

## Propriétés

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

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

### 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é.

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.

### Génération

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

