Изменения

== Обход случайного графа ==

Приведем ряд утверждений, которые будут использованы а дальнейшем. Их доказательство, а также более детальный рассказ можно найти здесь<ref name="chap4">Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf</ref>.

|statement=Пусть <tex>d > 1</tex>. Тогда вероятность <tex>p</tex>, что <tex>size(cc(v)) = O(\log n)</tex> (<tex>cc</tex> {{---}} компонента связности, содержащая <tex>v</tex>): <tex>p < 1</tex> {{---}} константа.

|proof=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс.

}}

{{Теорема

|statement=Пусть <tex>p = \frac{d}{n}, d > 1</tex>. <br>

# Найдутся такие <tex>c_1, c_2</tex>, что с <tex>p \leq \frac{1}{n}</tex> <tex>\exists cc: size(cc) \in (c_1\log n; c_2n)</tex>.

Будем считать шагом алгоритма поиска открытие новой вершины. После первых <tex>i</tex> шагов алгоритма, любая из вершин, кроме стартовой, может быть неоткрытой с вероятностью <tex>p = (1 - \frac{d}{n})^i</tex>. Пусть <tex>z_i</tex> {{---}} число вершин, открытых за первые <tex>i</tex> шагов алгоритма поиска. <tex>z_i</tex> распределены как <tex>Binomial(n − 1,1 − (1 - \frac{d}{n})^i)</tex>.<br>

Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество потомков у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.<br>

Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее потомки. Данный процесс может продолжаться бесконечно. <br>

|definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).

}}

|statement=Пусть <tex>m > 1</tex>. Пусть <tex>q</tex> {{---}} единственный корень <tex>f(x) = x</tex> на <tex>[0, 1)</tex>. Тогда <tex>f_j(x) = \lim_{j \to \infty}p(j) = q</tex> для <tex>x\in [0,1)</tex>.

}}

{{Теорема

|statement=Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть <tex>f(x)</tex> {{---}} производящая функция числа потомков каждой вершины. Тогда:<br>

# Если ожидаемое количество потомков в каждой вершине <tex>\le 1</tex>, тогда вероятность исчезновения {{---}} 1, если вероятность появления ровно одного ребенка равна <tex>1</tex>.