436
правок
Изменения
м
Пусть дан граф В произвольном графе <tex>G = (V,E)</tex>. Зафиксируем зафиксируем <tex>v_1 \in V</tex>. Пометим ее как активную, а все остальные вершины {{---}} нейтральными. Выберем среди нейтральных вершин всех соседей вершины <tex>v_1</tex>. После этого пометим вершину <tex>v_1</tex> как неактивную , а смежных с ней {{---}} как активных, а все остальные вершины {{---}} нейтральными.
Заметим, что данный Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], данным этим свойством мы воспользуемся позднее.<br>
<br>
<br>
<br>
Таким образомБлагодаря чему, '''Либо убери вводное слово, либо придумай другое'''<tex>q</tex> является корнем уравнения:<br>
В поисках другогоВведем обозначения: <tex>k</tex> {{---}} количество потомков вершины, меньшего корняа <tex>m = f'(1)</tex>, рассмотрим тогда <tex>m = f'(1) = \sum_{i = 1..\infty}ip_i</tex>, другими словами <tex>m = E(k)</tex>количество потомков вершины '''оформи по-другому, введи переменную, нельзя просто обернуть русский текст в тех'''<tex>).</texbr>Кажется, что при <tex>m > 1</tex> дерево будет расти вечно, так как каждая вершина в момент времени <tex>j</tex> должна иметь потомков, однако при <tex>p_0 > 0</tex> с положительной вероятность вероятностью у корня может вообще не быть потомков. Вспоминая об В исходном <tex>G(n,\frac{d}{n})</tex>б ввиду того, что <tex>dm</tex> {{---}} ожидаемое количество потомков, играет роль <tex>md</tex> играет роль , ввиду того, что <tex>d= E(k)</tex>.<br>
Далее, '''Ещё одно бессмысленное вводное слово, старайся не использовать их там, где не нужно''' пользуясь описанными выше утверждениямиПользуясь [[#lemma2|леммой 2]] и [[#th5|теоремой 5]], можно доказать, что:<br>
small changes
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Представлять себе описанный только что процесс можно так. В : в начальный момент времени есть одна активная частица. Затем она создает <tex>Z_1 \geq 0</tex> (может быть достигнуто, так как величина <tex>Z_1</tex> равна нулю с положительной вероятностью) активных потомков и перестает быть активной. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает <tex>Z_2</tex> новых частиц, а сама перестает быть активной. И , и так далее. Данный процесс может как завершиться (частицы перестанут быть активными), так и продолжаться бесконечно.<br>
Говоря в терминах данного выше определения, <tex>Y_i</tex> и <tex>Z_i</tex> {{---}} количество активных и порожденных частиц в момент времени <tex>t</tex>, соответственно.
{{Теорема
|id = th1
|about=1
|statement=Пусть <tex>\lambda \leq 1</tex>. Тогда с вероятностью 1 процесс <tex>Y_t</tex> вырождается, т.е. <tex>P(\exists t: Y_t = 0) = 1</tex>.
}}
{{Теорема
|id = th2
|about=2
|statement=Пусть <tex>\lambda \ge 1</tex>. Пусть <tex>\gamma \in (0, 1)</tex> {{---}} единственное решение уравнения <tex>1 - \gamma = e^{-\lambda \gamma}</tex>. Тогда процесс <tex>Y_t</tex> вырождается с вероятностью <tex>1 - \gamma</tex>, т.е. <tex>P(\exists t: Y_t \leq 0) = 1 - \gamma</tex>.
}}
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Снова зафиксируем какую-нибудь активную вершину <tex>v_2</tex>, и повторим процесс. Не меняем , не меняя статус остальных уже активных вершин.
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.<br>
Обозначим число активных вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число соседей вершины, которую собираемся пометить как неактивную, {{---}} через <tex>Z_t</tex>. Тогда <tex>Y_0 = 1,Y_t = Y_t−1 + Z_t − 1</tex>. Все введенные величины зависят от графа <tex>G</tex> и от последовательности выбираемых вершин <tex>v_1,\dotsc</tex>.
|about=о гигантской компоненте
|statement=Рассмотрим модель <tex>G(n, p)</tex>. Пусть <tex>p = \dfrac{ c }{n}</tex>.
: Если <tex>c < 1</tex>, то найдется такая константа <tex>\beta</tex>, зависящая от <tex>c</tex>, что а.п.н. (асимптотически почти наверное) размер каждой связной компоненты случайного графа не превосходит <tex>\beta \ln n</tex>.: Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma</tex>, зависящая от <tex>c</tex>, что а.п.н. в случайном графе есть ровно одна компонента размера <tex>\geq\gamma n</tex>. Размер остальных компонент не превосходит <tex>\beta \ln n</tex>.
|proof=
Приведем здесь идеи<ref>Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.{{---}} М.: МЦНМО, 2013 {{---}} C.330-339 {{---}} ISBN 978-5-4439-0040-7</ref>, изложенные А.М. Райгородским, основанные на доказательстве<ref>Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.</ref> Р. Карпа. Такой формат позволит понять основные идеи и логику рассуждений. Строгий вариант приведен в <ref name="trueproof">Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.</ref>.
'''Случай <tex>c < 1</tex>'''.
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta = \beta(c)</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(\dfracfrac{1}{n}\right).</tex><br><br>Далее: <tex>P_{n, p}(Y_{t_0} > 0) = P_{n, p}(\xi_{t_o} > t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) > t_0) \thickapprox</tex><br>: (с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) </tex><br>: <tex>\thickapprox P_{n, p}(Binomial(n, pt_0) > t_0) \thickapprox</tex><br>: (с учетом центральной предельной теоремы) <br>: <tex> \thickapprox \int\limits_{\frac{t_0 - npt_0}{\sqrt{npt_0(1 - pt_0)}}}^\infty \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}dx</tex>.
Поскольку <tex>c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины
'''Случай <tex>c > 1</tex>'''.
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка а.п.н. хотябы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref name="trueproof" />, мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки '''предыдущей''' [[#th2|теоремы 2]] и почему она совпадает с одноименной константой из той же теоремы. '''Лучше сделать ссылку на прокрутку статьи вверх, но в целом можно забить. Вообще "предыдущая теорема" - не очень хорошая ссылка'''
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
при <tex>t \thickapprox \gamma n</tex>. Иными словами, необходимо, чтобыто есть:<br>
<tex>P_{n, p}(Y_{t_0} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>
Применим центральную предельную теорему к
<tex>P_{n, p}(Y_{t_0} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
Пределы интегрирования в данном случае: от <tex>-\infty</tex> lj до <tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</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|теоремы2]], если заменить <tex>\lambda</tex> на <tex>c</tex>.
}}
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичности, ихИх доказательство, а также более детальный рассказ можно найти здесь<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|about=1
|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=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс.
}}
{{Теорема
|id=th4
|about=4
|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>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>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>
== Ветвящийся процесс Вероятность исчезновения =='''Наверное, лучше придумать другой заголовок'''=== От поиска в ширину к ветвящимся процессам ===Пользуясь идеями, изложенными в доказательстве [[#lemma1|леммы1]], перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.<br>{{Определение|definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).}}
Рассмотрим натуральное случайное число <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>
<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>
<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>
=== Вероятность Вычисление вероятности исчезновения ==={{ОпределениеЛемма|definitionid='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).lemma2}}{{Утверждение|about=2
|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>.
}}
{{Теорема
|about=5
|id=th5
|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>
Обозначим:
* <tex>q</tex> {{- --}} вероятность исчезновения;<br>
* <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{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>
<br>
Для того, чтобы вычислить вероятность исчезновения, воспользуемся [[Производящая функция|производящей функцией]]:<br>
<tex>f(x) = \sum_{i = 0..\infty}p_ix^i,</tex> где <tex>p_i</tex> {{---}} вероятность того, что <tex>y = i</tex><br>
<br>
Так как <tex>q</tex> {{---}} вероятность конечности алгоритма, то, если у корневой вершины <tex>i</tex> потомков, то построение каждого из поддеревьев должно завершиться, и это произойдет с вероятностью <tex>q^i</tex>. Таким образом, : <br>
<tex>q = \sum_{i = 0..\infty}p_iq^i</tex><br>
<tex>x = \sum_{i = 0..\infty}p_ix^i \Leftrightarrow f(x) = x</tex><br>
<br>
Рассмотрим решение данного уравнения на <tex>[0; 1]</tex>. <br>
<tex>x = 1</tex> {{---}} всегда решение данного уравнения, так как <tex>\sum_{i = 0..\infty}p_i1^i = \sum_{i = 0..\infty}p_i = 1 = x</tex>.<br>
[[Файл:Extinction_probability_equation_root_random_graph.png|thumb|300px|center|Решение уравнения f(x)=x]]
# <tex>m < 1</tex> <tex>||</tex> <tex>m = 1</tex> <tex>\&</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> < 1</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
Подробное описание доказательств доказательства данного факта, а также самих утверждений можно найти здесь<ref name="chap4" />.
== Вывод ==
