$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Dénombrements et probabilités > Théorie des graphes >

Graphe régulier

Définition : Un graphe est dit régulier s'il est simple, et si tous ses sommets ont le même degré, c'est-à-dire si de chaque sommet il part le même nombre d'arêtes.
  Il n'existe pas toujours de graphe régulier dont le degré de chaque sommet est fixé à l'avance. Par exemple, si on s'intéresse aux graphes réguliers de degré 3, c'est-à-dire que chaque sommet est de degré 3, alors, il est facile de prouver que le nombre de sommets doit être supérieur ou égal à 4, et qu'il doit être un nombre pair. Réciproquement, on peut toujours construire un graphe régulier de degré 3 de cardinal 2p, avec p>1. Pour p=2, on considère le graphe complet à 4 sommets. Pour p>2, on procède comme suit. On partage l'ensemble des sommets en 2, d'une part {a1,...,ap}, d'autre part {ap+1,...,a2p}. Les arêtes sont les suivantes :
  • a1 est relié à ap+1, ap+2 et ap+3;
  • a2 est relié à ap+2, ap+3 et ap+4;
  • ...
  • ap-2 est reliés à a2p-2, a2p-1 et a2p;
  • ap-1 est relié à a2p-1, a2p et a1;
  • ap est relié à a2p, a1 et a2.