title: Graphe régulier
text: # 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.
  
  