Изменения

Рассмотрим граф <tex>G(n, p)</tex>. Проанализируем его структуру по мере роста <tex>p</tex>. При :<br>* <tex>p = 0:</tex> граф состоит только из изолированных вершин. С ростом <tex>p</tex> в нем появляются ребра, [[Отношение связности, компоненты связности|компоненты связности]] получающегося леса объединяются. При достижении <br>* <tex>p = o\left(\frac{1}{n}\right):</tex> граф а.п.н. является лесом. Когда ;<br>* <tex>p = \frac{d}{n}:</tex>, появляются циклы. При <tex>d < 1</tex> размер каждой из компонент связности равен <tex>\Omega(\log n)</tex>. Число компонент связности, содержащих только один цикл {{---}} константа, зависящая от <tex>n</tex>. Таким образом, граф состоит из леса и компонент, содержащих единственный цикл без компонент размера <tex>\Omega(\log n)</tex>.;<br>Когда * <tex>p = \frac{1}{n}:</tex> начинает образовываться гигантская компонента. Этот процесс происходит в два этапа: при <br>** <tex>p = \frac{1}{n}: </tex> возникают компоненты из <tex>n^{\frac{2}{3}}</tex> вершин, а.п.н. являющиеся деревьями. При ;<br>** <tex>p = \frac{d}{n}, d > 1: </tex>, появляется гигантская компонента размером, пропорциональным количеству вершин во всем графе.;<br>После превышения * <tex>p</tex> значения <tex>\geq \frac{d}{n}:</tex>, все неизолированные вершины оказываются в гигантской компоненте. При достижении ;<br>* <tex>p \geq \frac{\ln n}{2n}:</tex>, в графе остаются только изолированные плюс гигантская компонента. Когда ;<texbr>p</tex> становится равной* <tex>p = \frac{\ln n}{n}:</tex>граф становится связным. При ;<br>* <tex>p = \frac{1}{2}:</tex> верно: <tex>\forall \varepsilon > 0\;\exists C\subseteq G,\quad C</tex> {{---}} клика <tex>: |C| = (2 - \varepsilon )\log n</tex>.;<br>