Graphe aléatoire

Graphe aléatoire

En mathématiques, un graphe aléatoire est un graphe qui est 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[1].

Sommaire

Les deux modèles de base d'Erdös et Rényi

Le modèle d'Erdös et Rényi regroupe en fait deux modèles, formellement différents, mais étroitement liés. Dans les deux modèles,

  • l'ensemble des sommets est \scriptstyle\ \{1,2,3,\dots,n\},\ noté par la suite \scriptstyle\ [\![n]\!]\ ;
  • les arêtes potentiellement présentes sont les \scriptstyle\ n(n-1)/2\ parties à deux éléments de \scriptstyle\ [\![n]\!]\ ; l'ensemble de ces arêtes est parfois noté \scriptstyle\ {[\![n]\!]\choose2}.\ Nous le noterons toutefois J pour des raisons de commodité typographique, et de cohérence avec l'article sur l'inégalité de Harris.
  • ainsi, le graphe aléatoire est non-orienté, et n'a ni boucles, ni arêtes multiples.

Le graphe aléatoire binomial

Dans ce modèle, souvent noté \scriptstyle\ \mathbb{G}(n,p),\ chacune des n(n-1)/2 arêtes est présente avec probabilité p, 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[2]. Le nombre \scriptstyle\ N_p\ d'arêtes de \scriptstyle\ \mathbb{G}(n,p)\ suit la loi binomiale de paramètres n(n-1)/2 et p.

Le graphe aléatoire uniforme

Dans ce modèle, souvent noté \scriptstyle\ \mathbb{G}(n,M),\ on choisit uniformément un sous-ensemble de M arêtes parmi les n(n-1)/2 arêtes possibles. Lorsqu'un graphe G à n sommets possède M arêtes, la probabilité de G est donnée par

\mathbb{P}(G)\ =\ \frac1{{{n\choose2}\choose M}}.

C'est le modèle \scriptstyle\ \mathbb{G}(n,M)\ qui est principalement étudié dans la série d'articles fondateurs publiés par Erdös et Rényi entre 1959 et 1968[3].

Les deux processus aléatoires à valeurs graphe

  • 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, etc ... sans remise. On obtient ainsi une suite \scriptstyle\ \{\mathbb{G}(n,M)\}_{0\le M\le n(n-1)/2},\ 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. Un avantage de cette construction est de voir coexister différents graphes aléatoires de paramètres M différents, sur le même espace probabilisé, et de pouvoir ainsi comparer leurs caractéristiques, non pas en moyenne ou en loi, mais pour chaque élément ω de l'espace probabilisé considéré. Cela permet de raisonner par couplage.
  • On peut aussi associer à chaque arête e de J une variable aléatoire \scriptstyle\ T_{e}\ , le poids de l'arête, de sorte que la famille \scriptstyle\ (T_{e})_{e\in J}\ soit une famille de variables aléatoires i.i.d., par exemple de loi uniforme sur l'intervalle [0,1]. On note alors \scriptstyle\ \mathbb{G}(n,p)\ le graphe formé des arêtes dont le poids est inférieur à p. Pour chaque arête, cela se produit avec probabilité
\mathbb{P}(T_e\le p)\ =\ p.
On obtient ainsi une famille \scriptstyle\ \{\mathbb{G}(n,p)\}_{0\le p\le 1},\ croissante, de graphes aléatoires, qui forme un processus à temps continu, à valeurs dans l'ensemble des graphes. Cette famille est croissante au sens de l'inclusion de l'ensemble des arêtes : une arête e présente dans \scriptstyle\ \mathbb{G}(n,p)\ est aussi présente dans \scriptstyle\ \mathbb{G}(n,p+\varepsilon),\ \varepsilon>0,\ puisque \scriptstyle\ \{T_e\le p\}\ \Rightarrow\ \{T_e\le p+\varepsilon\}.\ Chaque terme de la famille de graphes est un graphe aléatoire binomial défini précédemment.

Métaphore. On peut imaginer les sommets du graphe comme n îles sur un lac, communicant à l'aide de passerelles (les arêtes e ), submergées à des profondeurs respectives \scriptstyle\ T_{e}\ sous la surface de l'eau. Si le lac se vide de son eau graduellement, on va voir émerger progressivement les passerelles, et des composantes connexes regroupant de plus en plus d'îles vont se former.

Liens entre les deux modèles

En vertu du théorème central limite, ou de l'inégalité de Hoeffding, la loi binomiale est très concentrée autour de son espérance. Plus précisément, le nombre d'arêtes \scriptstyle\ N_p\ d'un graphe aléatoire de loi \scriptstyle\ \mathbb{G}(n,p)\ est donc très proche de \scriptstyle\ \hat{M}=\left\lfloor p\ {n\choose2}\right\rfloor\ surtout si cette dernière quantité \scriptstyle\ \hat{M}\ est grande devant n : en effet[4],

\forall t>0,\qquad\mathbb{P}\left(\left|N_p-\hat{M}\right|\ge tn\right)\ \le\ 2\,e^{-2t^2}.

De plus, la loi conditionnelle de \scriptstyle\ \mathbb{G}(n,p)\ sachant que \scriptstyle\ N_p=M\ est précisément \scriptstyle\ \mathbb{G}(n,M).\ Pour cette raison, si M est proche de \scriptstyle\ \hat{M}\ , ou, de manière équivalente, si

p\simeq\frac{2M}{n(n-1)}\,,

il est généralement admis (et souvent démontré[5]) que les deux modèles \scriptstyle\ \mathbb{G}(n,p)\ et \scriptstyle\ \mathbb{G}(n,M)\ ont des propriétés très proches.

En poussant plus loin, notons \scriptstyle\ T_{(k)}\ la k-ème valeur de la suite \scriptstyle\ (T_{e})_{e\in J}\ une fois que cette dernière suite est rangée dans l'ordre croissant : la suite \scriptstyle\ (T_{(k)})_{1\le e\le n(n-1)/2}\ est appelée la suite des statistiques d'ordre de la suite \scriptstyle\ (T_{e})_{e\in J}.\ Lorsque p prend la valeur aléatoire \scriptstyle\ T_{(M)}, \ alors \scriptstyle\ \mathbb{G}(n,T_{(M)})\ est exactement \scriptstyle\ \mathbb{G}(n,M).\ Pour corroborer les observations précédentes, notons que \scriptstyle\ T_{(M)}\ est très proche de \scriptstyle\ 2M/n(n-1),\ au sens où, en conséquence de résultats célèbres de Donsker et de Kolmogorov[6], la probabilité

\varphi_n(x)=\mathbb{P}\left(\sup_{1\le M\le n(n-1)/2}\left\{|T_{(M)}-\tfrac{2M}{n(n-1)}|\right\}\ge \tfrac{x\sqrt2}n\right)

satisfait

\exp(-2x^2)\ \le\ \liminf_{n}\varphi_n(x)\ \le\ \limsup_{n}\varphi_n(x)\ \le\ 2\sum_{r=1}^{+\infty} (-1)^{r-1}\exp(-2r^2x^2),

les 1ers et 4e termes étant les queues de distribution des lois de Rayleigh et de Kolmogorov, respectivement : en résumé, le supremum (lorsque M varie) des erreurs \scriptstyle\ |T_{(M)}-2M/n(n-1)|\ est de l'ordre de 1/n.

Ordre et croissance

Un graphe peut être vu comme une partie de l'ensemble J des arêtes, donc l'espace probabilisé est ici l'ensemble Ω des parties de J, qu'on peut parfois identifier à \scriptstyle\ \{0,1\}^J.\ Cette identification est en particulier utile lorsqu'on veut appliquer l'inégalité de Harris.

  • L'inclusion est une relation d'ordre partielle sur Ω.
  • Comme d'ordinaire, une application X définie sur Ω, à valeurs réelles, est dite croissante si
\{\omega\le \omega^{\prime}\}\quad\Rightarrow\quad\{X(\omega)\le X(\omega^{\prime})\}.\
  • Une partie A de Ω est dite croissante si
\{\omega\le \omega^{\prime}\ \text{et}\ \omega\in A\}\quad\Rightarrow\quad\{\omega^{\prime}\in A\}.\
De manière équivalente, une partie A de Ω est dite croissante si sa fonction indicatrice est croissante.
  • La propriété de décroissance d'une application ou d'une partie a une définition analogue.
Exemples  :

Parmi les propriétés et paramètres d'un graphe,

  • la connexité est croissante, i.e. la partie A de Ω constituée de tous les graphes connexes, est une partie croissante de Ω : si on ajoute une arête à un graphe connexe, le graphe ainsi obtenu est encore connexe ;
  • la planarité est décroissante : si on enlève une arête à un graphe planaire, le graphe ainsi obtenu est encore planaire ;
  • le nombre chromatique est croissant ;
  • le nombre de stabilité est décroissant ;
  • la propriété triangle-free est décroissante.

On a l'inégalité suivante :

Inégalité de Harris — Dans le cadre du graphe aléatoire binomial,

  • soit deux variables aléatoires X et Y croissantes sur \scriptstyle\ \Omega.\ Alors
\mathbb{E}\left[XY\right] \geq \mathbb{E}\left[X\right] \mathbb{E}\left[Y\right]\,;
  • soit deux parties croissantes A et B de \scriptstyle\ \Omega.\ Alors
\mathbb{P}(A\cap B) \geq \mathbb{P}(A) \mathbb{P}(B).
Remarques  :
  • Cela revient à dire qu'il y a une corrélation positive entre les variables concernées, puisqu'on peut reformuler la première inégalité sous la forme
\text{Cov}\left(X,Y\right)\ \ge \ 0.
  • L'inégalité vaut aussi pour des variables ou des parties décroissantes, mais le sens des inégalités change lorsque les variables ou les parties concernées ont des sens de monotonie opposés.

La connexité

Le seuil de connexité

Théorème (Erdös, Rényi, 1960) — Posons \scriptstyle\ a_n=np(n)-\ln n,\ ou encore :

p(n)\ =\ \frac{\ln n}n\,+\, \frac{a_n}n.
  • Si \scriptstyle\ \lim_{n}a_n=+\infty,\ alors
    \lim_{n}\mathbb{P}\left(\mathbb{G}\left(p(n),n\right)\mathrm{~est~connexe}\right)=1.
  • Si \scriptstyle\ \lim_{n}a_n=-\infty,\ alors
    \lim_{n}\mathbb{P}\left(\mathbb{G}\left(p(n),n\right)\mathrm{~est~connexe}\right)=0.

On dit que \scriptstyle\ \ln(n)/n\ est un seuil étroit pour la propriété de connexité, l'étroitesse faisant référence au fait que la propriété est vérifiée même si \scriptstyle\ a_n\ tend vers l'infini strictement moins vite que \scriptstyle\ \ln n.\

Démonstration

On se donne un graphe aléatoire \scriptstyle\ G_n\ de loi \scriptstyle\ \mathbb{G}\left(p(n),n\right)\ et un graphe aléatoire \scriptstyle\ \tilde{G}_n\ de loi \scriptstyle\ \mathbb{G}\left(\tilde{p}(n),n\right).\ Le théorème découle du théorème double-exponentiel, qui découle lui-même de l'énumération des points isolés effectuée à la section suivante. La connexité est une propriété croissante, donc, dès que n est assez grand pour que

p(n)\ =\ \frac{\ln n}n\,+\, \frac{a_n}n\quad\ge\quad\frac{\ln n}n+\frac cn+\frac{\varepsilon(n)}n\ =\ \tilde{p}(n),

on a aussi

\mathbb{P}\left(G_n\mathrm{~est~connexe}\right)\ge\mathbb{P}\left(\tilde{G}_n \mathrm{~est~connexe}\right).

En effet, quitte à construire \scriptstyle\ G_n\ et \scriptstyle\ \tilde{G}_n\ à l'aide des mêmes variables uniformes i.i.d. \scriptstyle\ (U_e)_{e\in J}\ , sur le même espace probabilisé Ω, comme indiqué à la section « Les deux processus aléatoires à valeurs graphe », on a, pour tout ω de Ω,

G_n(\omega)\supset \tilde{G}_n(\omega),

donc

\left\{\tilde{G}_n(\omega)\mathrm{~est~connexe}\right\}\Rightarrow\left\{G_n(\omega)\mathrm{~est~connexe}\right\},

et

\mathbb{P}\left(\tilde{G}_n\mathrm{~est~connexe}\right)\le\mathbb{P}\left(G_n\mathrm{~est~connexe}\right).

Si \scriptstyle\ \lim_{n}a_n=+\infty,\ il suit que, pour tout nombre réel c,

\liminf_n\mathbb{P}\left(\mathbb{G}\left(p(n),n\right)\mathrm{~est~connexe}\right)\ge e^{-e^{-c}},

ou bien encore

\liminf_n\mathbb{P}\left(\mathbb{G}\left(p(n),n\right)\mathrm{~est~connexe}\right)\ge \sup\left\{e^{-e^{-c}}\,|\,c\in\mathbb R\right\}\ =\ 1.

En revanche, si \scriptstyle\ \lim_{n}a_n=-\infty,\ alors, pour n suffisamment grand, on aura, pour tout ω, \scriptstyle\ G_n(\omega)\subset \tilde{G}_n(\omega),\ et

\mathbb{P}\left(\tilde{G}_n\mathrm{~est~connexe}\right)\ge\mathbb{P}\left(G_n\mathrm{~est~connexe}\right).

Ainsi, pour tout nombre réel c,

\limsup_n\mathbb{P}\left(\mathbb{G}\left(p(n),n\right)\mathrm{~est~connexe}\right)\le \inf\left\{e^{-e^{-c}}\,|\,c\in\mathbb R\right\}\ =\ 0.

Énumération des points isolés

Il est plus facile (plus probable) de réussir à couper les n-1 connections entre un point et son complémentaire, que les k(n-k) connections entre un groupe de k points et son complémentaire, car la fonction f(k)=k(n-k) augmente très rapidement au voisinage de 1, d'où, lorsque k augmente, beaucoup plus d'arêtes à couper, et une probabilité bien plus faible de réussir à les couper toutes. En corollaire, avec le choix du paramètre p fait plus haut, le graphe G(n,p) sera non connexe « presque uniquement » s'il a des points isolés, au sens où la probabilité d'être connexe est très proche de la probabilité de ne pas avoir de points isolés, \scriptstyle\ \mathbb{P}\left(X_n=0\right),\ qui vaut approximativement \scriptstyle\ e^{-e^{-c}}.\ En effet, on a le résultat suivant :

Théorème — Points isolés (Erdös, Rényi, 1960). Supposons que

\tilde{p}(n)\ =\ \frac{\ln n}n+\frac cn+\frac{\varepsilon(n)}n.

Alors le nombre \scriptstyle\ X_n\ de points isolés du graphe \scriptstyle\ G\left(\tilde{p}(n),n\right)\ converge en loi vers une loi de Poisson de paramètre \scriptstyle\ e^{-c}.\

Démonstration

Dans ce qui suit, on abrège \scriptstyle\ G\left(\tilde{p}(n),n\right)\ en \scriptstyle\ \tilde{G}_{n},\ et on pose

μ = e − c.

Soit \scriptstyle\ X_{n}\ le nombre de points isolés de \scriptstyle\ \tilde{G}_{n}.\ On sait que

X_{n}=Y_{1}+Y_{2}+\dots+Y_{n},
où
Y_{i}=1_{\mathrm{le~sommet~}i\mathrm{~est~isol\acute e}}.

Utilisons la méthode des moments factoriels[7]. Soit \scriptstyle\ I_{n,A}\ l'ensemble des injections de \scriptstyle\ [\![1,n]\!]\ dans \scriptstyle\ A.\ Pour tout \scriptstyle\ r\ge 1,\

(X_{n})_{r}=(Y_1+Y_2+\dots+Y_{n})_{r}=\sum_{\varphi\in I_{r,[\![1,n]\!]}}\ \prod_{i=1}^{r}Y_{\varphi(i)}.

Les termes \scriptstyle\ \prod_{i=1}^{r}Y_{\varphi(i)}\ de la somme précédente apparaissent effectivement dans le développement de \scriptstyle\ (Y_1+Y_2+\dots+Y_{n})_{r},\ mais, en dehors de ces termes, ce développement fait apparaître beaucoup d'autres termes, qui, apparemment, se télescopent. En effet, soit

E=\left\{a\in[\![1,n]\!]\,|\,Y_{a}=1\right\}.

Alors

\forall\,\varphi\in I_{r,[\![1,n]\!]},\qquad\prod_{i=1}^{r}Y_{\varphi(i)}=1_{\varphi\in I_{r,E}},

donc

\sum_{\varphi\in I_{r,[\![1,n]\!]}}\ \prod_{i=1}^{r}Y_{\varphi(i)}\ =\ |I_{r,E}|\ =\ (|E|)_{r}\ =\ (X_{n})_{r}.

Par ailleurs, par symétrie,

\mathbb{E}\left[\prod_{i=1}^{r}Y_{\varphi(i)}\right]\ =\ \mathbb{E}\left[\prod_{i=1}^{r}Y_{i}\right]=(1-\tilde{p}(n))^{r(n-1)-r(r-1)/2},

où \scriptstyle\ r(n-1)\ est le nombre d'arêtes potentiellement issues d'un sommet de \scriptstyle\ E,\ et où \scriptstyle\ r(r-1)/2\ est le nombre d'arêtes entre 2 sommets de \scriptstyle\ E,\ i.e. celles qui sont comptées double dans le total \scriptstyle\ r(n-1).\ Ainsi

\begin{align} \mathbb{E}\left[(X_{n})_{r}\right] &= (n)_{r}(1-\tilde{p}(n))^{r(n-1)-r(r-1)/2} \\ &\simeq n^{r}(1-\tilde{p}(n))^{r(n-1)} \\ &=\left( n(1-\tilde{p}(n))^{n-1}\right)^{r} \\ &\simeq \mu^{r}. \end{align}

Donc, par la méthode des moments[7], \scriptstyle\ X_{n}\ converge en loi vers une loi de Poisson de paramètre \scriptstyle\ \mu,\ et

\lim \mathbb{P}\left(X_{n}=0\right)\ =\ e^{-\mu}\ =\ e^{-e^{-c}}.

Ce théorème est une illustration frappante du paradigme de Poisson, selon lequel, lorsque se présente un grand nombre d'opportunités d'observer un évènement rare (i.e. peu probable), alors le nombre total d'évènements rares effectivement observés suit une loi de Poisson.

Le théorème double-exponentiel

Erdös et Rényi en déduisent un résultat plus précis que la propriété de seuil étroit :

Théorème double-exponentiel (Erdös, Rényi, 1960) —  Supposons que

\tilde{p}(n)\ =\ \frac{\ln n}n+\frac cn+\frac{\varepsilon(n)}n.
Alors
\lim_{n}\mathbb{P}\left(\mathbb{G}\left(\tilde{p}(n),n\right)\mathrm{~est~connexe}\right)=e^{-e^{-c}}.
Démonstration
Si \scriptstyle\ X_{n}=0,\ \scriptstyle\ \tilde{G}_{n}\ est sans point isolé, et il y a alors peu de chances que \scriptstyle\ \tilde{G}_{n}\ soit autre chose que connexe (cf. Spencer, 10 lectures on random graphs). En effet, soit \scriptstyle\ B\ une partie de \scriptstyle\ [\![1,n]\!]\ et soit \scriptstyle\ k\ son cardinal. Notons \scriptstyle\ \mathcal{C}_{B}\ l'évènement « \scriptstyle\ B\ est une composante connexe de \scriptstyle\ \tilde{G}_{n}\  ». L'évènement \scriptstyle\ \mathcal{C}_{B}\ peut être vu comme la réunion (non disjointe) de \scriptstyle\ k^{k-2}\ sous-ensembles de probabilités
\tilde{p}(n)^{k-1}(1-\tilde{p}(n))^{k(n-k)},

ce qui conduit à la majoration suivante :

\mathbb{P}(\mathcal{C}_{B})\ \le\ k^{k-2}\tilde{p}(n)^{k-1}(1-\tilde{p}(n))^{k(n-k)}.

Ici \scriptstyle\ k^{k-2}\ désigne le nombre d'arbres couvrants possibles[8] pour un graphe connexe dont les sommets seraient les éléments de \scriptstyle\ B,\ ou bien encore, de manière équivalente, le nombre de choix possibles d'une famille de k-1 arêtes qui rend l'ensemble B connexe. Par ailleurs, \scriptstyle\ \tilde{p}(n)^{k-1}\ est la probabilité que les \scriptstyle\ k-1\ arêtes de l'arbre couvrant considéré soient effectivement présentes, et \scriptstyle\ (1-\tilde{p}(n))^{k(n-k)}\ est la probabilité qu'aucune arête reliant un sommet de \scriptstyle\ B\ à un sommet de \scriptstyle\ B^{c}\ ne soit présente, de telle sorte que B soit non seulement connexe, mais aussi maximale parmi les parties connexes du graphe.

L'évènement

D_{n}=\{X_{n}=0\mathrm{~mais~}\tilde{G}_{n}\mathrm{~n}^{\prime}\mathrm{est~pas~connexe}\}

vérifie

D_{n}\subset \bigcup_{2\le|B|\le n/2}\mathcal{C}_{B}.

En effet, sous l'hypothèse \scriptstyle\ D_{n},\ \scriptstyle\ \tilde{G}_{n}\ a plusieurs composantes connexes, donc la plus petite d'entre elles (au sens du nombre de sommets) a au plus \scriptstyle\ n/2\ sommets, mais cette plus petite composante connexe a au moins deux sommets, puisque \scriptstyle\ X_{n}=0.\ Ainsi

\begin{align} \mathbb{P}(D_{n}) &\le \sum_{2\le|B|\le n/2}\mathbb{P}(\mathcal{C}_{B}) \\ &\le \sum_{2\le k\le n/2}{n\choose k}k^{k-2}\tilde{p}(n)^{k-1}(1-\tilde{p}(n))^{k(n-k)} \\ &\le \sum_{2\le k\le n/2}u_{k}. \end{align}

Or, pour \scriptstyle\ \alpha>0,\

\begin{align}u_{2}&\le n^{-1+\alpha}\,\ln n \end{align}

dès que

\ln n\ge \max\left[c+\varepsilon(n)\,,(-2c-2\varepsilon(n)+4\tilde{p}(n))/\alpha\right].

De même qu'une composante connexe de taille supérieure à 2 est bien moins probable qu'une composante connexe de taille 1, une composante connexe de taille supérieure à 3 est bien moins probable qu'une composante connexe de taille 2, ce qui se traduit par

Propriété —  Quand n tends vers l'infini

u_2(n)\ \gg\ \sum_{3\le k\le n/2}u_{k}(n).

Quelques calculs un peu pénibles, sans être toutefois franchement difficiles, conduisent à ce résultat.

Démonstration

La borne donnée plus haut pour \scriptstyle\ u_2(n)\ n'est pas seulement une majoration, mais donne en fait l'ordre de grandeur de \scriptstyle\ u_2(n).\ Pour ce qui est du reste de la somme, on est contraint de le couper en deux avant de majorer chacun des deux morceaux :

\begin{align} \frac{u_{k+1}}{u_{k}} &= (n-k)\,(1+\tfrac1k)^{k-2}\, \tilde{p}(n)\times (1-\tilde{p}(n))^{n-2k-1} \\ &= (n-k)\,(e+\hat{\varepsilon}(k))\, \tilde{p}(n)\times (1-\tilde{p}(n))^{n-2k-1} \\ &\le \hat{c}\, \ln n\ (1-\tilde{p}(n))^{n-2k-1} \end{align}

où

\forall n,k,\quad \hat{c}\ge (e+\hat{\varepsilon}(k))\, \frac{n\tilde{p}(n)}{\ln n}.

Pour \scriptstyle\ 0<\beta<(1-\gamma)/2<0.5,\ et \scriptstyle\ k\le\beta n,\

\begin{align} \frac{u_{k+1}}{u_{k}} &\le \hat{c}\, \ln n\ \exp\left[-\tilde{p}(n)(n-2k-1)\right] \\ &\le \hat{c}n^{-\gamma}\ln n, \end{align}

dès que

\ln n\ge \frac{\tilde{p}(n)+(c+\varepsilon(n))(2\beta-1)}{1-2\beta-\gamma}.

Donc, pour \scriptstyle\ n\ assez grand, \scriptstyle\ u_{k}\ décroit plus vite qu'une suite exponentielle de raison \scriptstyle\ \hat{c}n^{-\gamma}\ln n,\ lorsque \scriptstyle\ 2\le k\le 1+\beta n,\ et

\sum_{k=2}^{1+\beta n}u_{k}\ \le\ \frac{u_{2}}{1-\hat{c}n^{-\gamma}\ln n}\ \le\ 2n^{-1+\alpha}\,\ln n.

Par ailleurs, pour \scriptstyle\ 0<\alpha<1/4,\ on peut trouver \scriptstyle\ c\ et \scriptstyle\ \rho,\ positifs, tels que, pour tout \scriptstyle\ n\ge 1,\

\begin{align} u_{n/2}&\le c\,\rho^{n}\,n^{-\alpha n}. \end{align}

Pour \scriptstyle\ 0<\beta<(1-\gamma)/2<0.5,\ et \scriptstyle\ k\ge\beta n,\

\begin{align} \frac{u_{k-1}}{u_{k}} &\le \frac{d}{\ln n}\ \exp\left[\tilde{p}(n)(n-2k+1)\right] \\ &\le \frac{d\,n^{(1-2\beta)^{2}/\gamma}}{\ln n} \\ &\le d\,n^{(1-2\beta)^{2}/\gamma}, \end{align}

dès que \scriptstyle\ n\ est assez grand. Par conséquent, pour \scriptstyle\ n/2\ge k\ge\beta n,\ et \scriptstyle\ \beta\ assez proche de 0.5, \scriptstyle\ (1-2\beta)/\gamma\ assez proche de 1,

\begin{align} -\alpha+((1-2\beta)^{3}/2\gamma)&<0,\\ \frac{u_{k}}{u_{n/2}} &\le d^{(1-2\beta)n/2}n^{n(1-2\beta)^{3}/2\gamma},\\ u_{k} &\le c\,\tilde{\rho}^{n}\,n^{(-\alpha+((1-2\beta)^{3}/2\gamma)) n},\end{align}

et

\sum_{k=\beta n}^{n/2}u_{k}\ \le\ c\,\hat{\rho}^{n}\,n^{(-\alpha+((1-2\beta)^{3}/2\gamma)) n}\ \ll\ u_2.

Par conséquent

\lim_{n}\mathbb{P}\left(\tilde{G}_{n}\mathrm{~est~connexe}\right)=\lim_{n}\mathbb{P}\left(X_{n}=0\right).

Notons \scriptstyle\ T_n\ le premier instant t où le graphe \scriptstyle\ \mathbb{G}\left(t,n\right)\ est connexe :

T_n\ =\ \inf\left\{t\ge 0\ |\ \mathbb{G}\left(t,n\right)\mathrm{~est~connexe}\right\},

de sorte que

\left\{\mathbb{G}\left(t,n\right)\mathrm{~est~connexe}\right\}\quad\Rightarrow\quad\left\{T_{n}\le t\right\}\quad\Rightarrow\quad\left\{\forall\varepsilon>0,\quad \mathbb{G}\left(t+\varepsilon,n\right)\mathrm{~est~connexe}\right\}.

On peut alors voir le théorème double-exponentiel comme un résultat sur le développement asymptotique de \scriptstyle\ T_n\  : si \scriptstyle\ Z_n\ est défini par la relation suivante :

T_n\ =\ \frac{\ln n}{n}\ +\ \frac{Z_n}{n},

alors le théorème double-exponentiel stipule que \scriptstyle\ Z_n\ converge en loi vers la distribution de Gumbel, ce qui pourrait se traduire, dans une version probabiliste de la notation de Landau, par :

T_n\ =\ \frac{\ln n}{n}\ +\ \Theta\left(\frac{1}{n}\right).

A voir

Notes

  1. ↑ Le premier article, publié en 1959, est "On Random Graphs I", Publ. Math. Debrecen 6, 290.
  2. ↑ (en) Pal Erdös, « Some remarks on the theory of graphs », dans Bull. Amer. Math. Soc., vol. 53, no 4, 1947, p. 292-294 [texte intégral] . On considère souvent cet article comme marquant la naissance de la « méthode probabiliste » pour l'étude des graphes non aléatoires, en particulier pour la théorie de Ramsey.
  3. ↑ Pour un historique, voir Karonski et Rucinski, The origins of the theory of random graphs, 1997.
  4. ↑ voir (en) Svante Janson, Tomasz Luczak et Andrzej Rucinski, Random Graphs, Wiley-Interscience, 15 mai 2000, 1re éd. (1re éd. 2000), hardcover, 333 p. (ISBN 0471175412 et 978-0471175414) , Ch. 2, Exponentially small probabilities, pour plus de détails.
  5. ↑ voir (en) Svante Janson, Tomasz Luczak et Andrzej Rucinski, Random Graphs, Wiley-Interscience, 15 mai 2000, 1re éd. (1re éd. 2000), hardcover, 333 p. (ISBN 0471175412 et 978-0471175414) , section 1.4, Asymptotic equivalence, p.14.
  6. ↑ voir (en) Galen R. Shorack et Jon A. Wellner, Empirical Processes With Applications to Statistics, Society for Industrial & Applied Mathematics, 4 septembre 2009, 998 p. (ISBN 0898716845 et 978-0898716849) , Section 3.8, Limiting distributions under the null hypothesis, p. 142, et Ch. 18, The Standardized Quantile Process, p. 637.
  7. ↑ a et b Th. 6.7, p. 144 de (en) Svante Janson, Tomasz Luczak et Andrzej Rucinski, Random Graphs, Wiley-Interscience, 15 mai 2000, 1re éd. (1re éd. 2000), hardcover, 333 p. (ISBN 0471175412 et 978-0471175414) .
  8. ↑ voir l'article Bijection de Joyal, ou bien (fr) Martin Aigner et Günter M. Ziegler, Raisonnements divins, 2e édition, 2006, pp. 195-201, La formule de Cayley pour le nombre d’arbres.

Bibliographie

  • (en) Béla Bollobas, Random Graphs, Cambridge University Press, 15 janvier 2001, 2e éd. (1re éd. 1985), 516 p. (ISBN 0521797225 et 978-0521797221) .
  • (en) Svante Janson, Tomasz Luczak et Andrzej Rucinski, Random Graphs, Wiley-Interscience, 15 mai 2000, 1re éd. (1re éd. 2000), hardcover, 333 p. (ISBN 0471175412 et 978-0471175414) .
  • Ecole d'Eté de Probabilités de Saint-Flour XXI-1991, Lecture Notes in Math., 1541, Springer, 1993. Partie 3 : Joel Spencer, Nine lectures on random graphs (pp. 293-347).

Autres pages



Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Graphe Aléatoire — En mathématiques, un graphe aléatoire est un graphe qui est généré par un processus aléatoire. Histoire Les graphes aléatoires ont été définis par Paul Erdős et Alfréd Rényi dans un article de 1959 intitulé On Random Graphs I , dans Publ. Math.… …   Wikipédia en Français

  • Graphe aleatoire — Graphe aléatoire En mathématiques, un graphe aléatoire est un graphe qui est généré par un processus aléatoire. Histoire Les graphes aléatoires ont été définis par Paul Erdős et Alfréd Rényi dans un article de 1959 intitulé On Random Graphs I ,… …   Wikipédia en Français

  • Graphe (mathématiques) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe d'une chaîne de Markov — et classification des états Le graphe d une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états …   Wikipédia en Français

  • Graphe d'une chaîne de Markov et classification des états — Le graphe d une chaîne de Markov et la classification des états sont des notions de la théorie des graphes utilisées en calcul des probabilités. Sommaire 1 Graphe d une chaîne de Markov 2 Classification des états 3 Lexi …   Wikipédia en Français

  • Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Graphe circulant — Matrice circulante En algèbre linéaire, une matrice circulante est une matrice carrée dans laquelle on passe d une ligne à la suivante par permutation circulaire (décalage vers la droite) des coefficients. Une matrice circulante de taille n est… …   Wikipédia en Français

  • Marche aléatoire — Trois marches aléatoires (indépendantes) isotropes sur le réseau  ; 10 000 pas. En mathématiques, en économie, et en physique théorique, une marche au hasard est un modèle mathématique d un système possédant une dynamique discrète… …   Wikipédia en Français

  • Lexique (graphe) — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

Share the article and excerpts

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