436
правок
Изменения
м
→Обход в ширину
}}
=== Обход Поиск в ширину ===
Воспользуемся полученными знаниями. <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_on_random_graph.png|300px|center|Проблема БФС]]
