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