Graphe fortement régulier
- Graphe fortement régulier
-
Le
graphe de Paley d'ordre 13, un graphe fortement régulier de type (13,6,2,3).
En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe qui est en particulier un graphe régulier.
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.
Une 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
- Les quatre paramètres (v,k,λ,μ) vérifient toujours la relation suivante :
- (v − k − 1)μ = k(k − λ − 1)
- Un graphe fortement régulier de type (v,k,λ,μ) a exactement trois valeurs propres distinctes :
- k avec multiplicité 1
avec multiplicité ![\frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]](5/0b5677d5798e136f966d853b9cf106cd.png)
avec multiplicité ![\frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]](5/0759d5f04b1526b0baa38b2a4ac6f075.png)
- Les graphes fortement réguliers dont les paramètres vérifient 2k + (v − 1)(λ − μ) = 0 sont nommés graphes de conférence à cause de leur relation avec les matrices de conférence. Leur type est
.
- 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).
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe fortement régulier de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe distance-régulier — En théorie des graphes, un graphe est distance régulier si pour tous sommets , le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.… … Wikipédia en Français
Graphe de Clebsch — Représentation du graphe de Clebsch Nombre de sommets 16 Nombre d arêtes 40 Distribution des degrés 5 régulier Rayon … Wikipédia en Français
Graphe de McLaughlin — Nombre de sommets 275 Nombre d arêtes 15 400 Distribution des degrés 112 régulier Rayon 2 Diamètre 2 Maille 3 Automorphismes 1 796 256 000 … Wikipédia en Français
Graphe D'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 … Wikipédia en Français
Graphe d'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 … Wikipédia en Français
Graphe d'hoffman-singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 … Wikipédia en Français
Graphe de Schläfli — Représentation du graphe de Schläfli. Nombre de sommets 27 Nombre d arêtes 216 Distribution des degrés 16 régulier Rayon 2 … Wikipédia en Français
Graphe local de McLaughlin — Représentation du graphe local de McLaughlin. Nombre de sommets 162 Nombre d arêtes 4 536 Distribution des degrés 56 régulier Rayon … Wikipédia en Français
Graphe de Brouwer-Haemers — Représentations du graphe de Brouwer Haemers. Nombre de sommets 81 Nombre d arêtes 810 Distribution des degrés 20 régulier Rayon … Wikipédia en Français
Graphe régulier — 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… … Wikipédia en Français