Graphe aléatoire

vignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme. Dans les deux modèles, il s'agit d'un graphe aléatoire non orienté, qui n'a ni boucles, ni arêtes multiples. On utilise les notations suivantes : l'ensemble des sommets est {1, 2, 3, ..., n} noté par la suite ; les arêtes potentiellement présentes sont les n(n–1)/2 parties à deux éléments de ; l'ensemble de ces arêtes est parfois noté Il sera noté toutefois J pour des raisons de commodité typographique, et de cohérence avec l'article sur l'inégalité de Harris. Dans ce modèle, souvent noté chacune des n(n–1)/2 arêtes potentielles est présente avec probabilité p, et absente avec probabilité 1-p, cela indépendamment du statut des autres arêtes. Le cas p = 0,5 a été étudié par Erdős dès 1947. Le nombre N d'arêtes de suit la loi binomiale de paramètres n(n–1)/2 et p. Dans ce modèle, souvent noté on choisit uniformément un sous-ensemble de M arêtes parmi les n(n–1)/2 arêtes possibles. Si on considère un graphe G à n sommets possède M arêtes, la probabilité d'obtenir G est donnée par C'est le modèle qui est principalement étudié dans la série d'articles fondateurs publiés par Erdős et Rényi entre 1959 et 1968. On peut partir d'un graphe sans arêtes, donc totalement déconnecté, et ajouter une arête tirée au hasard uniformément, puis une autre, sans remise. On obtient ainsi une suite croissante (au sens de l'inclusion de l'ensemble des arêtes), de 1 + n(n–1)/2 graphes aléatoires, qui forme un processus à temps discret à valeurs dans l'ensemble des graphes. Chaque terme de la suite est un graphe aléatoire uniforme défini à la section précédente.