Graphe régulier

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 régulier de degré k

Sommaire

Cas particuliers

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.

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 Km est fortement régulier pour tout m

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.

Génération

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

Voir aussi

Références

  1. M. Meringer, J. Graph Theory, 1999, 30, 137.

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe régulier de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Graphe de Folkman — Représentation du graphe de Folkman Nombre de sommets 20 Nombre d arêtes 40 Distribution des degrés 4 régulier Rayon …   Wikipédia en Français

  • Graphe singleton — Représentation du graphe singleton. Nombre de sommets 1 Nombre d arêtes 0 Distribution des degrés 0 régulier Rayon 0 …   Wikipédia en Français

  • Graphe de Hoffman-Singleton — Schéma du graphe de 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 …   Wikipédia en Français

  • Graphe de Gray — Représentation du graphe de Gray. Nombre de sommets 54 Nombre d arêtes 81 Distribution des degrés 3 régulier Rayon …   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 Frucht — Le graphe de Frucht Nombre de sommets 12 Nombre d arêtes 18 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • Graphe de Harries — Représentation du graphe de Harries. Nombre de sommets 70 Nombre d arêtes 105 Rayon 6 Diamètre 6 …   Wikipédia en Français

  • 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 =… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”