title: Graphe fortement régulier
text: # Graphe fortement régulier
  
  En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier.
  
  ## Définition
  
  Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que
  
  * Toute paire de sommets adjacents a exactement λ voisins communs.
  * Toute paire de sommets non-adjacents a exactement μ voisins communs.
  
  Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
  
  Lorsque μ n'est pas nul, un tel graphe est en particulier un graphe distance-régulier.
  
  ## Propriétés
  
  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 |
  
  * Les quatre paramètres (v,k,λ,μ) vérifient toujours la relation suivante :
  
      $(v-k-1)\mu =k(k-\lambda -1)$
  * Un graphe fortement régulier de type (v,k,λ,μ) a exactement trois valeurs propres distinctes :
     * $k$ avec multiplicité 1
     * ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$ avec multiplicité ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
     * ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$ avec multiplicité ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
  * Les graphes fortement réguliers dont les paramètres vérifient $2k+(v-1)(\lambda -\mu )=0$ sont nommés graphes de conférence à cause de leur relation avec les matrices de conférence. Leur type est $\left(v,{\frac {v-1}{2}},{\frac {v-5}{4}},{\frac {v-1}{4}}\right)$.
  * Le graphe complémentaire d'un graphe fortement régulier de type (v,k,λ,μ) est aussi fortement régulier, de type (v, v−k−1, v−2−2k+μ, v−2k+λ).
  
  ## Exemples
  
  * Le graphe de Shrikhande de type (16,6,2,2).
  * Le cycle de longueur 5, de type (5,2,0,1).
  * Le graphe de Petersen de type (10,3,0,1).
  * Les graphes de Chang de type (28,12,6,4).
  * Le graphe de Hoffman-Singleton de type (50,7,0,1).
  * Le graphe de Higman-Sims de type (100,22,0,6).
  * Le graphe de Paley d'ordre q dont le type est (q, (q − 1)/2, (q − 5)/4, (q − 1)/4.
  * Le graphe de Brouwer-Haemers de type (81,20,1,6).
  * Le graphe de Schläfli de type (27,16,10,8).
  * Le graphe local de McLaughlin de type (162,56,10,24).
  