Séminaire Pizza

Le graphe aléatoire

par UNKNOWN Melleray

Europe/Paris
Fokko du Cloux

Fokko du Cloux

Description

Étant donnés deux entiers distincts i et j, tirons à pile ou face pour décider si on place une arête entre i et j; on obtient ainsi un graphe dénombrable. Bien sûr, ce graphe dépend de nos tirages; mais on verra pourquoi, avec probabilité 1, tous les graphes ainsi obtenus sont isomorphes à un même graphe, appelé graphe de Rado, graphe d'Erdös-Rényi, ou graphe aléatoire (comme ces noms ne l'indiquent pas, ce graphe a été construit pour la première fois par Ackermann ).