4.4 Graphes aléatoires
63
Théorème 4.5 (Loi uniforme sur graphes finis). Pour tout n 1, la loi uniforme sur l’ensemble G n des graphes finis de sommets {1, . . . , n} s’obtient en
rendant les
n
2
=
1
2 n(n − 1) arêtes indépendantes et identiquement distribuées
de loi de Bernoulli Ber(1/2).
Un graphe aléatoire qui suit la loi uniforme sur G n est appelé graphe
aléatoire de Erdős-Rényi de taille n et de paramètre p =
1
2 .
Démonstration. L’ensemble G n est en bijection avec l’ensemble des matrices
n × n symétriques à coefficients dans {0, 1} et à diagonale nulle, lui même
en bijection avec l’ensemble produit {0, 1}
n(n−1)/2 . Or la loi uniforme sur un
ensemble produit est le produit des lois uniformes sur les facteurs, et la loi
uniforme sur {0, 1} est la loi de Bernoulli Ber(1/2).
Dans un graphe fini G = (V, E), le degré d’un sommet i ∈ V est le nombre
noté d i de sommets reliés à i directement par une arête, autrement dit
d i := card{j ∈ V : {i, j} ∈ E}.
On dit que G est un graphe d-régulier, où d 0 est un entier fixé, lorsque
d i = d pour tout i ∈ V . Les graphes 0-réguliers sont constitués de sommets
isolés et ne comportent aucune arête. Les graphes 1-réguliers sont constitués
d’arêtes déconnectées les unes des autres. Les graphes finis 2-réguliers sont
constitués de cycles déconnectés les uns des autres.
Si G est un graphe de sommets {1, . . . , n} de sorte que d 1 · · · d n pour
tout 1 i n, alors les deux propriétés suivantes ont lieu :
1. l’entier d 1 + · · · + d n est pair ;
2. pour tout 1 k n,
d 1 + · · · + d k k(k − 1) + min(k, d k+1 ) + · · · + min(k, d n ).
La parité de la somme vient du fait que chaque arête compte deux fois, tandis
que la quantité k(k − 1) + min(d k+1 , k) + · · · + min(d n , k) est la contribution
maximale à d 1 + · · · + d k des arêtes liées aux sommets 1 à k : on a au plus
k
2
= k(k − 1)/2 arêtes (comptent double) entre les sommets 1 à k, et au plus
min(k, d k+i ) arêtes entre le sommet i > k et les sommets 1 à k.
Un théorème de Erdős-Gallai affirme que pour tous d 1 · · · d n 0, il
existe un graphe à n 1 sommets de degrés d 1 , . . . , d n si et seulement si les
deux conditions ci-dessus sont vérifiés. On dit que d 1 , . . . , d n est la suite de
degrés
8 du graphe. Pour un graphe d-régulier de sommets {1, . . . , n}, nd est
pair et d n − 1 (égalité atteinte pour le graphe complet).
Les multigraphes sont obtenus à partir de la définition des graphes en
relaxant deux contraintes : on accepte les arêtes multiples entre sommets ainsi
que les boucles. Soient d 1 · · · d n 0 des entiers vérifiant les conditions de
Erdős-Gallai, et M d1,...,dn l’ensemble des multigraphes de sommets {1, . . . , n}
8. «Degree sequence» en anglais.
63
Théorème 4.5 (Loi uniforme sur graphes finis). Pour tout n 1, la loi uniforme sur l’ensemble G n des graphes finis de sommets {1, . . . , n} s’obtient en
rendant les
n
2
=
1
2 n(n − 1) arêtes indépendantes et identiquement distribuées
de loi de Bernoulli Ber(1/2).
Un graphe aléatoire qui suit la loi uniforme sur G n est appelé graphe
aléatoire de Erdős-Rényi de taille n et de paramètre p =
1
2 .
Démonstration. L’ensemble G n est en bijection avec l’ensemble des matrices
n × n symétriques à coefficients dans {0, 1} et à diagonale nulle, lui même
en bijection avec l’ensemble produit {0, 1}
n(n−1)/2 . Or la loi uniforme sur un
ensemble produit est le produit des lois uniformes sur les facteurs, et la loi
uniforme sur {0, 1} est la loi de Bernoulli Ber(1/2).
Dans un graphe fini G = (V, E), le degré d’un sommet i ∈ V est le nombre
noté d i de sommets reliés à i directement par une arête, autrement dit
d i := card{j ∈ V : {i, j} ∈ E}.
On dit que G est un graphe d-régulier, où d 0 est un entier fixé, lorsque
d i = d pour tout i ∈ V . Les graphes 0-réguliers sont constitués de sommets
isolés et ne comportent aucune arête. Les graphes 1-réguliers sont constitués
d’arêtes déconnectées les unes des autres. Les graphes finis 2-réguliers sont
constitués de cycles déconnectés les uns des autres.
Si G est un graphe de sommets {1, . . . , n} de sorte que d 1 · · · d n pour
tout 1 i n, alors les deux propriétés suivantes ont lieu :
1. l’entier d 1 + · · · + d n est pair ;
2. pour tout 1 k n,
d 1 + · · · + d k k(k − 1) + min(k, d k+1 ) + · · · + min(k, d n ).
La parité de la somme vient du fait que chaque arête compte deux fois, tandis
que la quantité k(k − 1) + min(d k+1 , k) + · · · + min(d n , k) est la contribution
maximale à d 1 + · · · + d k des arêtes liées aux sommets 1 à k : on a au plus
k
2
= k(k − 1)/2 arêtes (comptent double) entre les sommets 1 à k, et au plus
min(k, d k+i ) arêtes entre le sommet i > k et les sommets 1 à k.
Un théorème de Erdős-Gallai affirme que pour tous d 1 · · · d n 0, il
existe un graphe à n 1 sommets de degrés d 1 , . . . , d n si et seulement si les
deux conditions ci-dessus sont vérifiés. On dit que d 1 , . . . , d n est la suite de
degrés
8 du graphe. Pour un graphe d-régulier de sommets {1, . . . , n}, nd est
pair et d n − 1 (égalité atteinte pour le graphe complet).
Les multigraphes sont obtenus à partir de la définition des graphes en
relaxant deux contraintes : on accepte les arêtes multiples entre sommets ainsi
que les boucles. Soient d 1 · · · d n 0 des entiers vérifiant les conditions de
Erdős-Gallai, et M d1,...,dn l’ensemble des multigraphes de sommets {1, . . . , n}
8. «Degree sequence» en anglais.