436
правок
Изменения
м
На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.
[[Файл:Extinction_probability_equation_root_random_graph.png|thumb|300px|center|Решение уравнения f(x)=x]]
Отмена правки 75000)
== Теорема о гигантской компоненте ==
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
{{Определение
|definition='''Простейший ветвящийся процесс.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины<ref>https://ru.wikipedia.org/wiki/Распределение_Пуассона</ref> с одним и тем же [[Математическое ожидание случайной величины | математическим ожиданием]] <tex>\lambda</tex>. Положим
'''Случай <tex>c < 1</tex>'''.
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta</tex> {{---}} константа, которая будет подобрана далее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер , меньший или равный <tex>\le t_0</tex>.
Но размер компоненты {{---}} это момент вырождения процесса <tex>Y_t</tex> на случайном графе. Значит, интересующее нас утверждение можно записать в следующем виде: <tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \rightarrow 0, n \rightarrow \infty</tex>
Поскольку <tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \le nP_{n, p}(Y_{t_0} \ge 0)</tex>, достаточно найти такое <tex>\beta</tex>, при котором <tex>P_{n, p}(Y_{t_0} > 0) = o\left(\frac{1}{n}\right).</tex><br>
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а в дальнейшем. Их доказательство, а также более детальный рассказ можно найти здесь<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>.
{{Лемма
|id=lemma1
<tex>
\begin{equation*}
\begin{cases} &\text{1) Найдутся такие $c_1, c_2$, что с $p \leq \frac{1}{n}$ $\exists cc: size(cc) \in (c_1\log n; c_2n)$;} \\ &\text{2) Число вершин в компонентах размера $O(\ln n)$ а.п.н. $\leq cn, c < 1$. } \\ & \quad\:\text{Тогда с $p = 1 - o(1)$ существует компонента связности размера $\Omega (n)$;} \\
\end{cases}
\end{equation*}
=== Проблема поиска в ширину ===
[[Файл:Bfs_problem_on_random_graph.png|300px|thumb|left|Проблема поиска в ширину на случайном графе]]
На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.
<br>
<br>
<br>
<br>
<br>
=== Неоткрытые вершины ===
\begin{equation*}
\begin{cases}
k \le 1 &\text{—$\;$ вероятность исчезновения равна 1, если вероятность } \\ & \;\;\;\;\;\,\text{появления ровно одного ребенка равна $1$;}\\ k > 1 &\text{—$\;$ вероятность исчезновения — единственное решение является }\\&\;\;\;\;\;\,\text{единственным решением $f(x) = x,\; x \in [0, 1)$;}
\end{cases}
\end{equation*}
Благодаря чему, <tex>q</tex> является корнем уравнения:<br>
<tex>x = \sum_{i = 0..\infty}p_ix^i \Leftrightarrow f(x) = x</tex><br>
[[Файл:Extinction_probability_equation_root_random_graph.png|thumb|300px|right|Решение уравнения f(x)=x]]
<br>
Рассмотрим решение данного уравнения на <tex>[0; 1]</tex>. <br>
Введем обозначения: <tex>k</tex> {{---}} количество потомков вершины, а <tex>m = f'(1)</tex>, тогда <tex>m = f'(1) = \sum_{i = 1..\infty}ip_i = E(k)</tex>.<br>
Кажется, что при <tex>m > 1</tex> дерево будет расти вечно, так как каждая вершина в момент времени <tex>j</tex> должна иметь потомков, однако при <tex>p_0 > 0</tex> с положительной вероятностью у корня может вообще не быть потомков. В исходном <tex>G(n,\frac{d}{n})</tex> <tex>m</tex> играет роль <tex>d</tex>, ввиду того, что <tex>d = E(k)</tex>.<br>
Пользуясь [[#lemma2|леммой 2]] и [[#th5|теоремой 5]], можно доказать, что:<br>
# <tex>m < 1 \vee m = 1 \wedge p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br>
d < 1\;\vee\; d = 1\;\wedge\; p_1 < 1&\text{—$\;$ процесс завершится с вероятностью один;}\\
d = 1\;\wedge\; p_1 = 1&\text{—$\;$ процесс будет протекать бесконечно;}\\
d > 1&\text{—$\;$ вероятность исчезновения меньше единицы, но, если $p_0 = 0$, процесс не завершится, так как у каждой вершины }\\&\;\;\;\;\;\,\text{найдется по крайней мере один потомок;}\\
\end{cases}
\end{equation*}
