Теорема о гигантской компоненте. Поиск в ширину в случайном графе — различия между версиями
Cuciev (обсуждение | вклад) (Image formatting fixed) |
Cuciev (обсуждение | вклад) (Image formatting fixed) |
||
Строка 185: | Строка 185: | ||
Благодаря чему, <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>. <br> | Рассмотрим решение данного уравнения на <tex>[0; 1]</tex>. <br> | ||
Строка 190: | Строка 191: | ||
Введем обозначения: <tex>k</tex> {{---}} количество потомков вершины, а <tex>m = f'(1)</tex>, тогда <tex>m = f'(1) = \sum_{i = 1..\infty}ip_i = E(k)</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> | Кажется, что при <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> | Пользуясь [[#lemma2|леммой 2]] и [[#th5|теоремой 5]], можно доказать, что:<br> | ||
# <tex>m < 1 \vee m = 1 \wedge p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br> | # <tex>m < 1 \vee m = 1 \wedge p_1 < 1</tex> {{---}} вероятность исчезновения <tex> = 1</tex>;<br> |
Версия 02:38, 25 июня 2020
Содержание
Теорема о гигантской компоненте
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
Определение: |
Простейший ветвящийся процесс. Пусть [1] с одним и тем же математическим ожиданием . Положим . | — независимые пуассоновские величины
Представлять себе описанный только что процесс можно так: в начальный момент времени есть одна активная частица. Затем она создает
Говоря в терминах данного выше определения, и — количество активных и порожденных частиц в момент времени , соответственно.
Теорема (1): |
Пусть . Тогда с вероятностью 1 процесс вырождается, т.е. . |
Теорема (2): |
Пусть . Пусть — единственное решение уравнения . Тогда процесс вырождается с вероятностью , т.е. . |
Определение: |
Ветвящийся процесс на случайном графе. Пусть математическим ожиданием . Положим . | — независимые пуассоновские величины с одним и тем же
В произвольном графе
зафиксируем . Пометим ее как активную, а все остальные вершины — нейтральными. Выберем среди нейтральных вершин всех соседей вершины . После этого пометим вершину как неактивную , а смежных с ней — как активных, а все остальные вершины — нейтральными.Снова зафиксируем какую-нибудь активную вершину
, и повторим процесс, не меняя статус остальных уже активных вершин.Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую
Данный процесс очень похож на поиск в ширину, этим свойством мы воспользуемся позднее.
Обозначим число активных вершин в момент времени
через , число нейтральных вершин — через , а число соседей вершины, которую собираемся пометить как неактивную, — через . Тогда . Все введенные величины зависят от графа и от последовательности выбираемых вершин .Если
посчитать случайным, то при любом выборе вершин получатся случайные величины на пространстве .Теорема о гигантской компоненте
Теорема (о гигантской компоненте): |
Рассмотрим модель . Пусть .
|
Доказательство: |
Приведем здесь идеи[2], изложенные А.М. Райгородским, основанные на доказательстве[3] Р. Карпа. Такой формат позволит понять основные идеи и логику рассуждений. Строгий вариант приведен в [4]. Здесь и далее: — биномиальное распределение.Случай .Положим
Поскольку Случай .В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что а.п.н. хотя бы в одном запуске возникнет гигантская компонента. Подробности можно найти в [4], мы же лишь поясним, откуда в текущей ситуации появляется из формулировки теоремы 2 и почему она совпадает с одноименной константой из той же теоремы. Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
при Так как по условию , то при выполнено: Применим центральную предельную теорему к Пределы интегрирования в данном случае: от до .Если , то мы получим искомое стремление вероятности к нулю.Если Таким образом, критическое значение , то вероятность, напротив, будет стремиться к единице. , вплоть до которого есть именно стремление к нулю, — это решение уравнения или, что равносильно, . А это и есть уравнение из теоремы 2, если заменить на . |
Обход случайного графа
Приведем ряд утверждений, которые будут использованы а дальнейшем. Их доказательство, а также более детальный рассказ можно найти здесь[5].
Лемма (1): |
Пусть . Тогда вероятность , что ( — компонента связности, содержащая ): — константа. |
Доказательство: |
Главная идея доказательства, которую мы будем использовать в дальнейшем — изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в ветвящийся процесс. |
Теорема (4): |
Пусть . |
Поиск в ширину
Рассмотрим граф
- компоненты связности получающегося леса объединяются.
-
-
-
начинает образовываться гигантская компонента. Этот процесс происходит в два этапа: -
-
-
-
-
Чтобы вычислить размер компоненты связности, пройдемся с помощью поиска в ширину по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью ). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.
Проблема поиска в ширину
На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине
Неоткрытые вершины
Будем считать шагом алгоритма поиска открытие новой вершины. После первых
Вероятность исчезновения
От поиска в ширину к ветвящимся процессам
Пользуясь идеями, изложенными в доказательстве леммы 1, перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.
Определение: |
Вероятность исчезновения (extinction probability) — вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время). |
Рассмотрим натуральное случайное число
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее потомки. Данный процесс может продолжаться бесконечно.
Пусть:
Тогда
— вероятность, что производит потомков, а значит:
и .
Глубина дерева не меньше количества вершин, поэтому вероятность того, что процесс закончится с деревом глубины , вычисляется по следующей формуле:
Вычисление вероятности исчезновения
Лемма (2): |
Пусть . Пусть — единственный корень на . Тогда для . |
Теорема (5): |
Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть — производящая функция числа потомков каждой вершины, а — ожидаемое количество потомков в каждой вершине. Тогда верно следующее:. |
В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины.
Обозначим:
Для того, чтобы вычислить вероятность исчезновения, воспользуемся производящей функцией:
где — вероятность того, что
Так как — вероятность конечности алгоритма, то, если у корневой вершины потомков, построение каждого из поддеревьев должно завершиться, и это произойдет с вероятностью :
Благодаря чему, является корнем уравнения:
Рассмотрим решение данного уравнения на .
— всегда решение данного уравнения, так как .
Введем обозначения: — количество потомков вершины, а , тогда .
Кажется, что при дерево будет расти вечно, так как каждая вершина в момент времени должна иметь потомков, однако при с положительной вероятностью у корня может вообще не быть потомков. В исходном играет роль , ввиду того, что .
Пользуясь леммой 2 и теоремой 5, можно доказать, что:
Подробное описание доказательства данного факта, а также самих утверждений можно найти здесь[5].
Вывод
Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе
См. также
Литература
- ↑ https://ru.wikipedia.org/wiki/Распределение_Пуассона
- ↑ Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.— М.: МЦНМО, 2013 — C.330-339 — ISBN 978-5-4439-0040-7
- ↑ Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.
- ↑ 4,0 4,1 Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.
- ↑ 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