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