436
правок
Изменения
Image formatting fixed
== Теорема о гигантской компоненте ==
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], этим свойством мы воспользуемся позднее.<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 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>.
|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>Binomial</tex> {{---}} биномиальное распределение.
'''Случай <tex>c < 1</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>
<br>
: <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>\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>t \thickapprox \gamma n</tex>, то есть:<br>
<tex>P_{n, p}(Y_{t_0t} \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> 1 - (1 - p)^t \thicksim 1 - e^{-pt} \thicksim 1 - e^{-c\alpha}</tex>
Применим центральную предельную теорему к
<tex>P_{n, p}(Y_{t_0t} \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>.
|about=4
|statement=Пусть <tex>p = \frac{d}{n}, d > 1</tex>. <br>
}}
=== Поиск в ширину ===
Рассмотрим граф <tex>G(n, p)</tex>. Проанализируем его структуру по мере роста <tex>p</tex>. При :<br>* <tex>p = 0:</tex> граф состоит только из изолированных вершин. С ростом <tex>p</tex> в нем появляются ребра, [[Отношение связности, компоненты связности|компоненты связности]] получающегося леса объединяются. При достижении <br>* <tex>p = o\left(\frac{1}{n}\right):</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 = \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</tex> значения <tex>\geq \frac{d}{n}:</tex>, все неизолированные вершины оказываются в гигантской компоненте. При достижении ;<br>* <tex>p \geq \frac{\ln n}{2n}:</tex>, в графе остаются только изолированные плюс гигантская компонента. Когда ;<texbr>p</tex> становится равной* <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>
Чтобы вычислить размер компоненты связности, пройдемся с помощью [[Обход в ширину|поиска в ширину]] по ней, стартуя из произвольной вершины и переходя к очередной неисследованной вершине, только если ребро между ними существует (данный факт необходимо установить независимо от других ребер, с вероятностью <tex>p = \frac{d}{n}</tex>). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым.
=== Проблема поиска в ширину ===
[[Файл:Bfs_problem_on_random_graph.png|300px|thumb|centerleft|Проблема поиска в ширину на случайном графе]]На данном изображении представлены результаты работы поиска в ширину , начавшемся в вершине <tex>1</tex> на двух графах: в первом у всех ребер <tex>p = 1</tex>, во втором же факт существования ребра определялся по ходу работы алгоритма {{---}} ребра, отмеченные пунктиром, не существуют. Проблема возникает, когда алгоритм просто не доходит до каких-то ребер, не выясняя, существуют они или нет: находясь в вершине <tex>2</tex>, алгоритм не делал запрос о ребре <tex>(2, 3)</tex>, так как у этому моменту вершина <tex>3</tex> уже была исследована. Ребра, которые потенциально могли быть не изученными, помечены на рисунке точечным пунктиром.<br><br>
<br>
=== Неоткрытые вершины ===
Благодаря чему, <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>
[[Категория: Дискретная математика]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Обходы графов]]
[[Категория: Связность в графах]]
