436
правок
Изменения
Обход случайного графа -- продолжение рассказа
== Обход случайного графа ==
Воспользуемся полученными в предыдущем разделе знаниями. <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>, размер каждой из компонент связности <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>G</tex> существует клика размером <tex>(2 - \varepsilon )\log n</tex>. Озвученные выше факты будут доказаны далее.<br><br>Чтобы вычислить размер компоненты связности, пройдемся с помощью [[Обход в ширину|БФС]] по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью <tex>p = \frac{d}{n}</tex>). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.<br>[Файл:bfs_problem.png|500px|center|Проблема БФС]]<br>На данном изображении представлены результаты работы БФС, начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Возникающая проблема состоит в том, что, к примеру, Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.
== Литература ==
