436
правок
Изменения
Добавлена теория по ветвящимся процессам и extinction probability
Если <tex>G</tex> посчитать случайным, то при любом выборе вершин <tex>v_1,\dotsc</tex> получатся случайные величины <tex>Y_t, N_t, Z_t</tex> на пространстве <tex>G(n, p)</tex>.
=== Теорема о гигантской компоненте ===
{{Теорема
Если <tex>\alpha < 1 - e^{-c\alpha}</tex>, то мы получим искомое стремление вероятности к нулю.
Если <tex>\alpha > 1 - e^{-c\alpha}</tex>, то вероятность, напротив, будет стрметиться стремиться к единице.
Таким образом, критическое значение <tex>\alpha</tex>, вплоть до которого есть именно стремление к нулю, {{---}} это решение уравнения <tex>\alpha = 1 - e^{-c\alpha}</tex> или, что равносильно, <tex>1 - \alpha = e^{-c\alpha}</tex>. А это и есть уравнение из [[th2| предыдущей теоремы]], если заменить <tex>\lambda</tex> на <tex>c</tex>.
}}
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичиности, их, а также более детальный рассказ можно найти в [4].{{Утверждение|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>O(\ln n)</tex> а.п.н. <tex>\leq cn, c < 1</tex>. Тогда с <tex>p = 1 - o(1)</tex> существует компонента связности размера <tex>\Omega (n)</tex>.}} === Обход в ширину === Воспользуемся полученными в предыдущем разделе знаниями. <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_on_random_graph.png|300px|center|Проблема БФС]]
<br>
На данном изображении представлены результаты работы БФС, начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Возникающая проблема состоит в том, что, к примеру, Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</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>
== Ветвящийся процесс ==
Пользуясь идеями, изложенными в доказательстве леммы, переходим от модифицированного БФС к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.<br>
Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество детей у очередной исследованной вершины. Каждый раз это значение выбирется случайно и независимо.<br>
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее "дети". Данный процесс может продолжаться бесконечно. <br>
Пусть <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex>. Пусть <tex>p′</tex> {{---}} вероятность того, что <tex>size(cc(v)) = O(\log n)</tex> в модицированном БФС. Пусть <tex>q</tex> {{---}} вероятность окончания процесса. Тогда <tex>q \geq p′</tex>, поскольку БФС, заканчивающийся с <tex> \le c_1\log n</tex> вершинами, приводит к окончанию построения дерева.<br>
Пусть <tex>p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}</tex> {{---}} вероятность, что <tex>y</tex> производит <tex>i</tex> детей. Тогда:<br>
<tex>\sum_{i = 0..s}p_i = 1</tex> и <tex>\sum_{i = 0..s}ip_i = E(y) = \frac{ds}{n} > 1</tex>.<br>
Глубина дерева <tex>\geq</tex> количеству вершин. Пусть <tex>a_i</tex> {{---}} вероятность того, что процесс закончится с деревом глубины <tex>t</tex>. Имеем:<br>
<tex>a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}</tex><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>.
# Если ожидаемое количество детей в каждой вершине <tex>> 1</tex>, тогда вероятность исчезновения {{---}} единственное решение <tex>f(x) = x</tex> на <tex>[0, 1)</tex>.
}}
<br>
В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины. <br>
Для того, чтобы вычислить вероятность исчезновения, воспользуемся [[Производящая функция|производящей функцией]]:<br>
<tex>f(x) = \sum_{i = 0..\infty}p_ix^i,</tex> где <tex>p_i</tex> {{---}} вероятность того, что <tex>y = i</tex><br>
{{В разработке}}
== Вывод ==
Сделайем вывод о вероятности исчезновения рассматриваемой версии ветвящегося процесса:<br>
# <tex>m < 1</tex> <tex>||</tex> <tex>m = 1</tex> & <tex>p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br>
# <tex>m = 1</tex> <tex>&</tex> <tex>p_1 = 1</tex> {{---}} вероятность исчезновения <tex> = 0</tex>;<br>
# <tex>m > 1</tex> {{---}} вероятность исчезновения <tex> < 0</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
== Литература ==
== См. также ==
* [[Случайная величина]]
* [[Центральная предельная теорема]]
* [[Случайные графы]]
* [[Обход в ширину]]
* [[Производящая функция]]
* [[Ветвящийся процесс]]
[[Категория: Дискретная математика]]
