Теорема о гигантской компоненте. Поиск в ширину в случайном графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (small changes)
(Image formatting fixed)
(не показана 41 промежуточная версия этого же участника)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
== Теорема о гигантской компоненте ==
 
== Теорема о гигантской компоненте ==
 
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
 
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
Строка 7: Строка 5:
 
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.  
 
<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>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>, соответственно.
 
Говоря в терминах данного выше определения, <tex>Y_i</tex> и <tex>Z_i</tex> {{---}} количество активных и порожденных частиц в момент времени <tex>t</tex>, соответственно.
 
{{Теорема
 
{{Теорема
 
|id = th1
 
|id = th1
 +
|about=1
 
|statement=Пусть <tex>\lambda \leq 1</tex>. Тогда с вероятностью 1 процесс <tex>Y_t</tex> вырождается, т.е. <tex>P(\exists t: Y_t = 0) = 1</tex>.
 
|statement=Пусть <tex>\lambda \leq 1</tex>. Тогда с вероятностью 1 процесс <tex>Y_t</tex> вырождается, т.е. <tex>P(\exists t: Y_t = 0) = 1</tex>.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 
|id = th2
 
|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>.
 
|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>.
 
}}
 
}}
Строка 21: Строка 21:
 
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.  
 
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.  
 
}}
 
}}
Пусть дан граф <tex>G = (V,E)</tex>. Зафиксируем <tex>v_1 \in V</tex>. Пометим ее как активную, а все остальные вершины {{---}} нейтральными. Выберем среди нейтральных вершин всех соседей вершины <tex>v_1</tex>. После этого пометим вершину <tex>v_1</tex> как неактивную , а смежных с ней {{---}} как активных, а все остальные вершины {{---}} нейтральными.
+
В произвольном графе <tex>G = (V,E)</tex> зафиксируем <tex>v_1 \in V</tex>. Пометим ее как активную, а все остальные вершины {{---}} нейтральными. Выберем среди нейтральных вершин всех соседей вершины <tex>v_1</tex>. После этого пометим вершину <tex>v_1</tex> как неактивную , а смежных с ней {{---}} как активных, а все остальные вершины {{---}} нейтральными.
  
Снова зафиксируем какую-нибудь активную вершину <tex>v_2</tex>, и повторим процесс. Не меняем статус остальных уже активных вершин.
+
Снова зафиксируем какую-нибудь активную вершину <tex>v_2</tex>, и повторим процесс, не меняя статус остальных уже активных вершин.
  
 
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.<br>
 
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.<br>
Заметим, что данный процесс очень похож на [[Обход в ширину|поиск в ширину]], данным свойством мы воспользуемся позднее.<br>
+
Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], этим свойством мы воспользуемся позднее.<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>.
+
Обозначим число активных вершин в момент времени <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>.
  
 
Если <tex>G</tex> посчитать случайным, то при любом выборе вершин <tex>v_1,\dotsc</tex> получатся случайные величины <tex>Y_t, N_t, Z_t</tex> на пространстве <tex>G(n, p)</tex>.
 
Если <tex>G</tex> посчитать случайным, то при любом выборе вершин <tex>v_1,\dotsc</tex> получатся случайные величины <tex>Y_t, N_t, Z_t</tex> на пространстве <tex>G(n, p)</tex>.
Строка 37: Строка 37:
 
|about=о гигантской компоненте
 
|about=о гигантской компоненте
 
|statement=Рассмотрим модель <tex>G(n, p)</tex>. Пусть <tex>p = \dfrac{ c }{n}</tex>.
 
|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>\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>.
+
: Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma</tex>, зависящая от <tex>c</tex>, что а.п.н.  в  случайном  графе  есть  ровно  одна  компонента  размера <tex>\geq\gamma n</tex>. Размер остальных компонент не  превосходит <tex>\beta \ln n</tex>.
 
|proof=
 
|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>.
 
Приведем здесь идеи<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>Binomial</tex> {{---}}  биномиальное распределение.
  
 
'''Случай <tex>c < 1</tex>'''.
 
'''Случай <tex>c < 1</tex>'''.
  
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta = \beta(c)</tex> {{---}} константа, которую мы подберем позднее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер <tex>\le t_0</tex>.
+
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta</tex> {{---}} константа, которая будет подобрана далее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер <tex>\le t_0</tex>.
Но размер компоненты {{---}} это момент вырождения процесса <tex>Y_t</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>
<tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \rightarrow 0,  n \rightarrow \infty</tex>
+
<br>
Поскольку <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) = P_{n, p}(\xi_{t_o} \geq t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) \geq t_0) \thickapprox</tex><br>
 
+
: (с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) </tex><br>
<tex>P_{n, p}(Y_{t_0} > 0) = o\left(\dfrac{1}{n}\right).</tex>
+
: <tex>\thickapprox P_{n, p}(Binomial(n, pt_0) \geq 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>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>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины
Строка 67: Строка 63:
 
'''Случай <tex>c > 1</tex>'''.
 
'''Случай <tex>c > 1</tex>'''.
  
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка хотя
+
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что а.п.н. хотя
бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref name="trueproof" />, мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки предыдущей теоремы и почему она совпадает с одноименной константой из той же теоремы. '''Лучше сделать ссылку на прокрутку статьи вверх, но в целом можно забить. Вообще "предыдущая теорема" - не очень хорошая ссылка'''
+
бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref name="trueproof" />, мы же лишь поясним, откуда в текущей ситуации появляется <tex>\gamma</tex> из формулировки [[#th2|теоремы 2]] и почему она совпадает с одноименной константой из той же теоремы.
  
 
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
 
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
при <tex>t \thickapprox \gamma n</tex>. Иными словами, необходимо, чтобы:
+
при <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} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>
  
 
Так как по условию <tex>p = \dfrac{ c }{n}</tex>, то при  <tex>t \thicksim \alpha n</tex> выполнено:
 
Так как по условию <tex>p = \dfrac{ c }{n}</tex>, то при  <tex>t \thicksim \alpha n</tex> выполнено:
 
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
 
<tex> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</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>P_{n, p}(Y_{t} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).</tex>
Интегрирование пойдет '''переформулируй''' от минус бесконечности до
+
Пределы интегрирования в данном случае: от <tex>-\infty</tex> до <tex>\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}</tex>.
<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 > 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>. А это и есть уравнение из предыдущей теоремы, если заменить <tex>\lambda</tex> на <tex>c</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>.
+
Приведем ряд утверждений, которые будут использованы а дальнейшем. Их доказательство, а также более детальный рассказ можно найти здесь<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> {{---}} константа.
 
|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=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс.
 
|proof=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
 +
|id=th4
 +
|about=4
 
|statement=Пусть <tex>p = \frac{d}{n}, d > 1</tex>. <br>
 
|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>
# Число вершин в компонентах размера <tex>O(\ln n)</tex> а.п.н. <tex>\leq cn, c < 1</tex>. Тогда с <tex>p = 1 - o(1)</tex> существует компонента связности размера <tex>\Omega (n)</tex>.
+
\begin{equation*}
 +
\begin{cases}
 +
    &\text{Найдутся такие $c_1, c_2$, что с $p \leq \frac{1}{n}$ $\exists cc: size(cc) \in (c_1\log n; c_2n)$;} \\
 +
    &\text{Число вершин в компонентах размера $O(\ln n)$ а.п.н. $\leq cn, c < 1$. Тогда с $p = 1 - o(1)$ существует компонента связности размера $\Omega (n)$;} \\
 +
\end{cases}
 +
\end{equation*}
 +
</tex>
 
}}
 
}}
  
 
=== Поиск в ширину  ===
 
=== Поиск в ширину  ===
 
+
Рассмотрим граф <tex>G(n, p)</tex>. Проанализируем его структуру по мере роста <tex>p</tex>:<br>
<br>
+
* <tex>p = 0:</tex> граф состоит только из изолированных вершин. С ростом <tex>p</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> размер каждой из компонент связности '''нельзя пользоваться математическими символами как сокращениями в plain text, пиши равен'''<tex>= \Omega(\log n)</tex>. Число компонент связности, содержащих только один цикл {{---}} константа, зависящая от <tex>n</tex>. Таким образом, граф состоит из леса и компонент, содержащих единственный цикл  без компонент размера <tex>\Omega(\log n)</tex>.<br>
+
* <tex>p = o\left(\frac{1}{n}\right):</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 = \frac{d}{n}:</tex> появляются циклы. При <tex>d < 1</tex> размер каждой из компонент связности равен <tex>\Omega(\log n)</tex>. Число компонент связности, содержащих только один цикл {{---}} константа, зависящая от <tex>n</tex>. Таким образом, граф состоит из леса и компонент, содержащих единственный цикл  без компонент размера <tex>\Omega(\log n)</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>
+
* <tex>p = \frac{1}{n}:</tex> начинает образовываться гигантская компонента. Этот процесс происходит в два этапа:<br>
 +
** <tex>p = \frac{1}{n}: </tex> возникают компоненты из <tex>n^{\frac{2}{3}}</tex> вершин, а.п.н. являющиеся деревьями;<br>
 +
** <tex>p = \frac{d}{n}, d > 1: </tex> появляется гигантская компонента размером, пропорциональным количеству вершин во всем графе;<br>
 +
* <tex>p \geq \frac{d}{n}:</tex> все неизолированные вершины оказываются в гигантской компоненте;<br>
 +
* <tex>p \geq \frac{\ln n}{2n}:</tex> в графе остаются только изолированные плюс гигантская компонента;<br>
 +
* <tex>p = \frac{\ln n}{n}:</tex> граф становится связным;<br>
 +
* <tex>p = \frac{1}{2}:</tex> <tex>\forall \varepsilon > 0\;\exists C\subseteq G,\quad C</tex> {{---}} клика <tex>: |C| = (2 - \varepsilon )\log n</tex>;<br>
 
<br>
 
<br>
 
Чтобы вычислить размер компоненты связности, пройдемся с помощью [[Обход в ширину|поиска в ширину]] по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью <tex>p = \frac{d}{n}</tex>). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.
 
Чтобы вычислить размер компоненты связности, пройдемся с помощью [[Обход в ширину|поиска в ширину]] по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью <tex>p = \frac{d}{n}</tex>). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.
Строка 110: Строка 121:
  
 
=== Проблема поиска в ширину ===
 
=== Проблема поиска в ширину ===
[[Файл:Bfs_problem_on_random_graph.png|300px|thumb|center|Проблема поиска в ширину на случайном графе]]
+
[[Файл: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>
 
<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>
 
Будем считать шагом алгоритма поиска открытие новой вершины. После первых <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>
+
Пользуясь идеями, изложенными в доказательстве [[#lemma1|леммы 1]], перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.<br>
Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество детей у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.<br>
+
{{Определение
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее "дети" '''Почему сначала не в кавычках, а потом в кавычках? Дай тогда формальное определение. Общая просьба к тексту, кстати, писать чуть более научно, использовать меньше вводных слов и предложений в 3 слова'''. Данный процесс может продолжаться бесконечно. <br>
+
|definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).
Пусть <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>y</tex>, обозначающее количество потомков у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.<br>
 +
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее потомки. Данный процесс может продолжаться бесконечно. <br>
 +
Пусть:
 +
* <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex>.<br>
 +
* <tex>p′</tex> {{---}} вероятность того, что <tex>size(cc(v)) = O(\log n)</tex> в модифицированном поиске в ширину.<br>
 +
* <tex>q</tex> {{---}} вероятность окончания процесса.<br>
 +
Тогда <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>
 
<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>
+
<br>
 +
Глубина дерева не меньше количества вершин, поэтому вероятность того, что процесс закончится с деревом глубины <tex>t</tex>, вычисляется по следующей формуле:<br>
 
<tex>a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}</tex><br>
 
<tex>a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}</tex><br>
  
=== Вероятность исчезновения ===
+
=== Вычисление вероятности исчезновения ===
{{Определение
+
{{Лемма
|definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).
+
|id=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>.
 
|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>
+
|about=5
# Если ожидаемое количество детей в каждой вершине <tex>\le 1</tex>, тогда вероятность исчезновения {{---}} 1, если вероятность появления ровно одного ребенка равна <tex>1</tex>.
+
|id=th5
# Если ожидаемое количество детей в каждой вершине <tex>> 1</tex>, тогда вероятность исчезновения {{---}} единственное решение <tex>f(x) = x</tex> на <tex>[0, 1)</tex>.
+
|statement=Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть <tex>f(x)</tex> {{---}} производящая функция числа потомков каждой вершины, а <tex>k</tex> {{---}} ожидаемое количество потомков в каждой вершине. Тогда верно следующее:<br>
 +
<tex>
 +
\begin{equation*}
 +
\begin{cases}
 +
  k \le 1 &\text{—$\;$ вероятность исчезновения равна 1, если вероятность появления ровно одного ребенка равна $1$;}\\
 +
  k > 1 &\text{—$\;$ вероятность исчезновения единственное решение $f(x) = x,\; x \in [0, 1)$;}
 +
\end{cases}
 +
\end{equation*}
 +
</tex>.
 
}}
 
}}
<br>
 
 
В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины. <br>
 
В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины. <br>
 
Обозначим:
 
Обозначим:
* <tex>q</tex> - вероятность исчезновения;<br>
+
* <tex>q</tex> {{---}} вероятность исчезновения;<br>
* <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</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>
+
* <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>
 
Для того, чтобы вычислить вероятность исчезновения, воспользуемся [[Производящая функция|производящей функцией]]:<br>
<br>
 
 
<tex>f(x) = \sum_{i = 0..\infty}p_ix^i,</tex> где <tex>p_i</tex> {{---}} вероятность того, что <tex>y = i</tex><br>
 
<tex>f(x) = \sum_{i = 0..\infty}p_ix^i,</tex> где <tex>p_i</tex> {{---}} вероятность того, что <tex>y = i</tex><br>
 
<br>
 
<br>
Так как <tex>q</tex> {{---}} вероятность конечности алгоритма, то, если у корневой вершины <tex>i</tex> потомков, то построение каждого из поддеревьев должно завершиться, и это произойдет с вероятностью <tex>q^i</tex>. Таким образом, <br>
+
Так как <tex>q</tex> {{---}} вероятность конечности алгоритма, то, если у корневой вершины <tex>i</tex> потомков, построение каждого из поддеревьев должно завершиться, и это произойдет с вероятностью <tex>q^i</tex>: <br>
 
<tex>q = \sum_{i = 0..\infty}p_iq^i</tex><br>
 
<tex>q = \sum_{i = 0..\infty}p_iq^i</tex><br>
Таким образом, '''Либо убери вводное слово, либо придумай другое'''<tex>q</tex> является корнем уравнения:<br>
+
Благодаря чему, <tex>q</tex> является корнем уравнения:<br>
 
<tex>x = \sum_{i = 0..\infty}p_ix^i \Leftrightarrow f(x) = x</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>
 
<br>
Рассмотрим решение данного уравнения на <tex>[0; 1]</tex>
+
Рассмотрим решение данного уравнения на <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>
 
<tex>x = 1</tex> {{---}} всегда решение данного уравнения, так как <tex>\sum_{i = 0..\infty}p_i1^i = \sum_{i = 0..\infty}p_i = 1 = x</tex>.<br>
В поисках другого, меньшего корня, рассмотрим <tex>m = f'(1) = \sum_{i = 1..\infty}ip_i</tex>, другими словами <tex>m = E(</tex>количество потомков вершины '''оформи по-другому, введи переменную, нельзя просто обернуть русский текст в тех'''<tex>)</tex>
+
Введем обозначения: <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>d</tex> {{---}} ожидаемое количество потомков, <tex>m</tex> играет роль <tex>d</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>
[[Файл:Extinction_probability_equation_root_random_graph.png|thumb|300px|center|Решение уравнения f(x)=x]]
+
Пользуясь [[#lemma2|леммой 2]] и [[#th5|теоремой 5]], можно доказать, что:<br>
Далее, '''Ещё одно бессмысленное вводное слово, старайся не использовать их там, где не нужно''' пользуясь описанными выше утверждениями, можно доказать, что:<br>
+
# <tex>m < 1 \vee m = 1 \wedge p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br>
# <tex>m < 1</tex> <tex>||</tex> <tex>m = 1</tex> <tex>\&</tex> <tex>p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br>
+
# <tex>m = 1 \wedge p_1 = 1</tex> {{---}} вероятность исчезновения <tex> = 0</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>
 
# <tex>m > 1</tex> {{---}} вероятность исчезновения <tex> < 1</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
Подробное описание доказательств данного факта, а также самих утверждений можно найти здесь<ref name="chap4" />.
+
Подробное описание доказательства данного факта, а также самих утверждений можно найти здесь<ref name="chap4" />.
  
 
== Вывод ==
 
== Вывод ==
 
Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе <tex>G(n, \frac{d}{n})</tex>. Рассчитав <tex>p_0</tex> и <tex>p_1</tex>, можно сделать следующие выводы:<br>
 
Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе <tex>G(n, \frac{d}{n})</tex>. Рассчитав <tex>p_0</tex> и <tex>p_1</tex>, можно сделать следующие выводы:<br>
# <tex>d < 1</tex> <tex>||</tex> <tex>d = 1</tex> <tex>\&</tex> <tex>p_1 < 1</tex> {{---}} вероятность завершения<tex> = 1</tex>;<br>
+
<tex>
# <tex>d = 1</tex> <tex>\&</tex> <tex>p_1 = 1</tex> {{---}} вероятность завершения '''напиши словами и это и выше и ниже'''<tex> = 0</tex>;<br>
+
\begin{equation*}
# <tex>d > 1</tex> {{---}} вероятность исчезновения <tex> < 1</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
+
\begin{cases}
 +
  d < 1\;\vee\;  d = 1\;\wedge\; p_1 < 1&\text{—$\;$ процесс завершится с вероятностью один;}\\
 +
  d = 1\;\wedge\; p_1 = 1&\text{—$\;$ процесс будет протекать бесконечно;}\\
 +
  d > 1&\text{—$\;$ вероятность исчезновения меньше единицы, но, если $p_0 = 0$, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;}\\
 +
\end{cases}
 +
\end{equation*}
 +
</tex>
  
 
== См. также ==
 
== См. также ==
Строка 181: Строка 218:
  
 
[[Категория: Дискретная математика]]
 
[[Категория: Дискретная математика]]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Обходы графов]]
 +
[[Категория: Связность в графах]]

Версия 02:38, 25 июня 2020

Теорема о гигантской компоненте

Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.

Определение:
Простейший ветвящийся процесс. Пусть [math]Z_1,\dotsc Z_n,\dotsc [/math] — независимые пуассоновские величины[1] с одним и тем же математическим ожиданием [math]\lambda[/math]. Положим [math]Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1[/math].

Представлять себе описанный только что процесс можно так: в начальный момент времени есть одна активная частица. Затем она создает [math]Z_1 \geq 0[/math] (может быть достигнуто, так как величина [math]Z_1[/math] равна нулю с положительной вероятностью) активных потомков и перестает быть активной. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает [math]Z_2[/math] новых частиц, а сама перестает быть активной, и так далее. Данный процесс может как завершиться (частицы перестанут быть активными), так и продолжаться бесконечно.
Говоря в терминах данного выше определения, [math]Y_i[/math] и [math]Z_i[/math] — количество активных и порожденных частиц в момент времени [math]t[/math], соответственно.

Теорема (1):
Пусть [math]\lambda \leq 1[/math]. Тогда с вероятностью 1 процесс [math]Y_t[/math] вырождается, т.е. [math]P(\exists t: Y_t = 0) = 1[/math].
Теорема (2):
Пусть [math]\lambda \ge 1[/math]. Пусть [math]\gamma \in (0, 1)[/math] — единственное решение уравнения [math]1 - \gamma = e^{-\lambda \gamma}[/math]. Тогда процесс [math]Y_t[/math] вырождается с вероятностью [math]1 - \gamma[/math], т.е. [math]P(\exists t: Y_t \leq 0) = 1 - \gamma[/math].
Определение:
Ветвящийся процесс на случайном графе. Пусть [math]Z_1,\dotsc Z_n,\dotsc [/math] — независимые пуассоновские величины с одним и тем же математическим ожиданием [math]\lambda[/math]. Положим [math]Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1[/math].

В произвольном графе [math]G = (V,E)[/math] зафиксируем [math]v_1 \in V[/math]. Пометим ее как активную, а все остальные вершины — нейтральными. Выберем среди нейтральных вершин всех соседей вершины [math]v_1[/math]. После этого пометим вершину [math]v_1[/math] как неактивную , а смежных с ней — как активных, а все остальные вершины — нейтральными.

Снова зафиксируем какую-нибудь активную вершину [math]v_2[/math], и повторим процесс, не меняя статус остальных уже активных вершин.

Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую [math]v_1[/math]) и нейтральные вершины.
Данный процесс очень похож на поиск в ширину, этим свойством мы воспользуемся позднее.

Обозначим число активных вершин в момент времени [math]t[/math] через [math]Y_t[/math], число нейтральных вершин — через [math]N_t[/math], а число соседей вершины, которую собираемся пометить как неактивную, — через [math]Z_t[/math]. Тогда [math]Y_0 = 1,Y_t = Y_{t − 1} + Z_t − 1[/math]. Все введенные величины зависят от графа [math]G[/math] и от последовательности выбираемых вершин [math]v_1,\dotsc[/math].

Если [math]G[/math] посчитать случайным, то при любом выборе вершин [math]v_1,\dotsc[/math] получатся случайные величины [math]Y_t, N_t, Z_t[/math] на пространстве [math]G(n, p)[/math].

Теорема о гигантской компоненте

Теорема (о гигантской компоненте):
Рассмотрим модель [math]G(n, p)[/math]. Пусть [math]p = \dfrac{ c }{n}[/math].
Если [math]c \lt 1[/math], то найдется такая константа [math]\beta[/math], зависящая от [math]c[/math], что а.п.н. (асимптотически почти наверное) размер каждой связной компоненты случайного графа не превосходит [math]\beta \ln n[/math].
Если же [math]c \gt 1[/math], то найдется такая константа [math]\gamma[/math], зависящая от [math]c[/math], что а.п.н. в случайном графе есть ровно одна компонента размера [math]\geq\gamma n[/math]. Размер остальных компонент не превосходит [math]\beta \ln n[/math].
Доказательство:
[math]\triangleright[/math]

Приведем здесь идеи[2], изложенные А.М. Райгородским, основанные на доказательстве[3] Р. Карпа. Такой формат позволит понять основные идеи и логику рассуждений. Строгий вариант приведен в [4].

Здесь и далее: [math]Binomial[/math] — биномиальное распределение.

Случай [math]c \lt 1[/math].

Положим [math]t_0=[\beta \ln n][/math], где [math]\beta[/math] — константа, которая будет подобрана далее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер [math]\le t_0[/math]. Но размер компоненты — это момент вырождения процесса [math]Y_t[/math] на случайном графе. Значит, интересующее нас утверждение можно записать в следующем виде: [math]P_{n, p}(\exists v_1 : Y_{t_0} \gt 0) \rightarrow 0, n \rightarrow \infty[/math] Поскольку [math]P_{n, p}(\exists v_1 : Y_{t_0} \gt 0) \le nP_{n, p}(Y_{t_0} \ge 0)[/math], достаточно найти такое [math]\beta[/math], при котором [math]P_{n, p}(Y_{t_0} \gt 0) = o\left(\frac{1}{n}\right).[/math]

[math]P_{n, p}(Y_{t_0} \gt 0) = P_{n, p}(\xi_{t_o} \geq t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) \geq t_0) \thickapprox[/math]
(с учетом асимптотики [math]1 - (1 - p)^{t_0} \thicksim pt_0) [/math]
[math]\thickapprox P_{n, p}(Binomial(n, pt_0) \geq t_0) \thickapprox[/math]
(с учетом центральной предельной теоремы)
[math] \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[/math].

Поскольку [math]c \lt 1[/math], нижний предел интегрирования имеет порядок [math]\sqrt{t_0}[/math]. Таким образом, весь интеграл не превосходит величины [math]e^{−\delta t_0}[/math]. Выберем [math]\beta[/math] таким, чтобы [math]e^{−\delta t_0}[/math] оказалось меньше, чем [math]e^{-2 \ln n} = \dfrac{1}{n^2}[/math], и в случае [math]c \lt 1[/math] теорема доказана.

Случай [math]c \gt 1[/math].

В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что а.п.н. хотя бы в одном запуске возникнет гигантская компонента. Подробности можно найти в [4], мы же лишь поясним, откуда в текущей ситуации появляется [math]\gamma[/math] из формулировки теоремы 2 и почему она совпадает с одноименной константой из той же теоремы.

Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже при [math]t \thickapprox \gamma n[/math], то есть:
[math]P_{n, p}(Y_{t} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty[/math]

Так как по условию [math]p = \dfrac{ c }{n}[/math], то при [math]t \thicksim \alpha n[/math] выполнено: [math] 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}[/math] Применим центральную предельную теорему к [math]P_{n, p}(Y_{t} \le 0)\thickapprox P_{n, p}(Binomial(n, 1 - e^{-c\alpha}) \le \alpha n).[/math] Пределы интегрирования в данном случае: от [math]-\infty[/math] до [math]\dfrac{\alpha n - n(1 - e^{-c\alpha})}{\sqrt{n(1 - e^{-c\alpha})e^{-c\alpha}}}[/math].

Если [math]\alpha \lt 1 - e^{-c\alpha}[/math], то мы получим искомое стремление вероятности к нулю.

Если [math]\alpha \gt 1 - e^{-c\alpha}[/math], то вероятность, напротив, будет стремиться к единице.

Таким образом, критическое значение [math]\alpha[/math], вплоть до которого есть именно стремление к нулю, — это решение уравнения [math]\alpha = 1 - e^{-c\alpha}[/math] или, что равносильно, [math]1 - \alpha = e^{-c\alpha}[/math]. А это и есть уравнение из теоремы 2, если заменить [math]\lambda[/math] на [math]c[/math].
[math]\triangleleft[/math]

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

Приведем ряд утверждений, которые будут использованы а дальнейшем. Их доказательство, а также более детальный рассказ можно найти здесь[5].

Лемма (1):
Пусть [math]d \gt 1[/math]. Тогда вероятность [math]p[/math], что [math]size(cc(v)) = O(\log n)[/math] ([math]cc[/math] — компонента связности, содержащая [math]v[/math]): [math]p \lt 1[/math] — константа.
Доказательство:
[math]\triangleright[/math]
Главная идея доказательства, которую мы будем использовать в дальнейшем — изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс.
[math]\triangleleft[/math]
Теорема (4):
Пусть [math]p = \frac{d}{n}, d \gt 1[/math].
[math] \begin{equation*} \begin{cases} &\text{Найдутся такие $c_1, c_2$, что с $p \leq \frac{1}{n}$ $\exists cc: size(cc) \in (c_1\log n; c_2n)$;} \\ &\text{Число вершин в компонентах размера $O(\ln n)$ а.п.н. $\leq cn, c \lt 1$. Тогда с $p = 1 - o(1)$ существует компонента связности размера $\Omega (n)$;} \\ \end{cases} \end{equation*} [/math]

Поиск в ширину

Рассмотрим граф [math]G(n, p)[/math]. Проанализируем его структуру по мере роста [math]p[/math]:

  • [math]p = 0:[/math] граф состоит только из изолированных вершин. С ростом [math]p[/math] в нем появляются ребра, компоненты связности получающегося леса объединяются.
  • [math]p = o\left(\frac{1}{n}\right):[/math] граф а.п.н. является лесом;
  • [math]p = \frac{d}{n}:[/math] появляются циклы. При [math]d \lt 1[/math] размер каждой из компонент связности равен [math]\Omega(\log n)[/math]. Число компонент связности, содержащих только один цикл — константа, зависящая от [math]n[/math]. Таким образом, граф состоит из леса и компонент, содержащих единственный цикл без компонент размера [math]\Omega(\log n)[/math];
  • [math]p = \frac{1}{n}:[/math] начинает образовываться гигантская компонента. Этот процесс происходит в два этапа:
    • [math]p = \frac{1}{n}: [/math] возникают компоненты из [math]n^{\frac{2}{3}}[/math] вершин, а.п.н. являющиеся деревьями;
    • [math]p = \frac{d}{n}, d \gt 1: [/math] появляется гигантская компонента размером, пропорциональным количеству вершин во всем графе;
  • [math]p \geq \frac{d}{n}:[/math] все неизолированные вершины оказываются в гигантской компоненте;
  • [math]p \geq \frac{\ln n}{2n}:[/math] в графе остаются только изолированные плюс гигантская компонента;
  • [math]p = \frac{\ln n}{n}:[/math] граф становится связным;
  • [math]p = \frac{1}{2}:[/math] [math]\forall \varepsilon \gt 0\;\exists C\subseteq G,\quad C[/math] — клика [math]: |C| = (2 - \varepsilon )\log n[/math];


Чтобы вычислить размер компоненты связности, пройдемся с помощью поиска в ширину по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью [math]p = \frac{d}{n}[/math]). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.

Проблема поиска в ширину

Проблема поиска в ширину на случайном графе

На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине [math]1[/math] на двух графах: в первом у всех ребер [math]p = 1[/math], во втором же факт существования ребра определялся по ходу работы алгоритма — ребра, отмеченные пунктиром, не существуют. Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине [math]2[/math], алгоритм не делал запрос о ребре [math](2, 3)[/math], так как у этому моменту вершина [math]3[/math] уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.





Неоткрытые вершины

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

Вероятность исчезновения

От поиска в ширину к ветвящимся процессам

Пользуясь идеями, изложенными в доказательстве леммы 1, перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.

Определение:
Вероятность исчезновения (extinction probability) — вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время).

Рассмотрим натуральное случайное число [math]y[/math], обозначающее количество потомков у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее потомки. Данный процесс может продолжаться бесконечно.
Пусть:

  • [math]y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})[/math].
  • [math]p′[/math] — вероятность того, что [math]size(cc(v)) = O(\log n)[/math] в модифицированном поиске в ширину.
  • [math]q[/math] — вероятность окончания процесса.

Тогда [math]q \geq p′[/math], поскольку поиск в ширину, заканчивающийся с [math] \le c_1\log n[/math] вершинами, приводит к окончанию построения дерева.

[math]p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}[/math] — вероятность, что [math]y[/math] производит [math]i[/math] потомков, а значит:
[math]\sum_{i = 0..s}p_i = 1[/math] и [math]\sum_{i = 0..s}ip_i = E(y) = \frac{ds}{n} \gt 1[/math].

Глубина дерева не меньше количества вершин, поэтому вероятность того, что процесс закончится с деревом глубины [math]t[/math], вычисляется по следующей формуле:
[math]a_t = p_0 + \sum_{i = 1..s}p_ia^i_{t - 1}[/math]

Вычисление вероятности исчезновения

Лемма (2):
Пусть [math]m \gt 1[/math]. Пусть [math]q[/math] — единственный корень [math]f(x) = x[/math] на [math][0, 1)[/math]. Тогда [math]f_j(x) = \lim_{j \to \infty}p(j) = q[/math] для [math]x\in [0,1)[/math].
Теорема (5):
Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть [math]f(x)[/math] — производящая функция числа потомков каждой вершины, а [math]k[/math] — ожидаемое количество потомков в каждой вершине. Тогда верно следующее:
[math] \begin{equation*} \begin{cases} k \le 1 &\text{—$\;$ вероятность исчезновения равна 1, если вероятность появления ровно одного ребенка равна $1$;}\\ k \gt 1 &\text{—$\;$ вероятность исчезновения — единственное решение $f(x) = x,\; x \in [0, 1)$;} \end{cases} \end{equation*} [/math].

В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины.
Обозначим:

  • [math]q[/math] — вероятность исчезновения;
  • [math]y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})[/math] — количество потомков у очередной исследованной вершины;
  • [math]p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}[/math] — вероятность, что [math]y[/math] производит [math]i[/math] потомков.


Для того, чтобы вычислить вероятность исчезновения, воспользуемся производящей функцией:
[math]f(x) = \sum_{i = 0..\infty}p_ix^i,[/math] где [math]p_i[/math] — вероятность того, что [math]y = i[/math]

Так как [math]q[/math] — вероятность конечности алгоритма, то, если у корневой вершины [math]i[/math] потомков, построение каждого из поддеревьев должно завершиться, и это произойдет с вероятностью [math]q^i[/math]:
[math]q = \sum_{i = 0..\infty}p_iq^i[/math]
Благодаря чему, [math]q[/math] является корнем уравнения:
[math]x = \sum_{i = 0..\infty}p_ix^i \Leftrightarrow f(x) = x[/math]

Решение уравнения f(x)=x


Рассмотрим решение данного уравнения на [math][0; 1][/math].
[math]x = 1[/math] — всегда решение данного уравнения, так как [math]\sum_{i = 0..\infty}p_i1^i = \sum_{i = 0..\infty}p_i = 1 = x[/math].
Введем обозначения: [math]k[/math] — количество потомков вершины, а [math]m = f'(1)[/math], тогда [math]m = f'(1) = \sum_{i = 1..\infty}ip_i = E(k)[/math].
Кажется, что при [math]m \gt 1[/math] дерево будет расти вечно, так как каждая вершина в момент времени [math]j[/math] должна иметь потомков, однако при [math]p_0 \gt 0[/math] с положительной вероятностью у корня может вообще не быть потомков. В исходном [math]G(n,\frac{d}{n})[/math] [math]m[/math] играет роль [math]d[/math], ввиду того, что [math]d = E(k)[/math].
Пользуясь леммой 2 и теоремой 5, можно доказать, что:

  1. [math]m \lt 1 \vee m = 1 \wedge p_1 \lt 1[/math] — вероятность исчезновения [math] = 1[/math];
  2. [math]m = 1 \wedge p_1 = 1[/math] — вероятность исчезновения [math] = 0[/math];
  3. [math]m \gt 1[/math] — вероятность исчезновения [math] \lt 1[/math], но, если [math]p_0 = 0[/math], процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;

Подробное описание доказательства данного факта, а также самих утверждений можно найти здесь[5].

Вывод

Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе [math]G(n, \frac{d}{n})[/math]. Рассчитав [math]p_0[/math] и [math]p_1[/math], можно сделать следующие выводы:
[math] \begin{equation*} \begin{cases} d \lt 1\;\vee\; d = 1\;\wedge\; p_1 \lt 1&\text{—$\;$ процесс завершится с вероятностью один;}\\ d = 1\;\wedge\; p_1 = 1&\text{—$\;$ процесс будет протекать бесконечно;}\\ d \gt 1&\text{—$\;$ вероятность исчезновения меньше единицы, но, если $p_0 = 0$, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;}\\ \end{cases} \end{equation*} [/math]

См. также

Литература

  1. https://ru.wikipedia.org/wiki/Распределение_Пуассона
  2. Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.— М.: МЦНМО, 2013 — C.330-339 — ISBN 978-5-4439-0040-7
  3. Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.
  4. 4,0 4,1 Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.
  5. 5,0 5,1 Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf