Теорема о гигантской компоненте. Поиск в ширину в случайном графе — различия между версиями
Cuciev (обсуждение | вклад) м (Опечатки) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 82 промежуточные версии 4 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
== Теорема о гигантской компоненте == | == Теорема о гигантской компоненте == | ||
− | Перед формулировкой основной теоремы данного раздела | + | Перед формулировкой основной теоремы данного раздела дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения. |
{{Определение | {{Определение | ||
− | |definition='''Простейший ветвящийся процесс.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины | + | |definition='''Простейший ветвящийся процесс.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины<ref>https://ru.wikipedia.org/wiki/Распределение_Пуассона</ref> с одним и тем же [[Математическое ожидание случайной величины | математическим ожиданием]] <tex>\lambda</tex>. Положим |
<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>Y_i</tex> и <tex>Z_i</tex> {{---}} количество активных и порожденных частиц в момент времени <tex>t</tex>, соответственно. | ||
{{Теорема | {{Теорема | ||
|id = th1 | |id = th1 | ||
− | |statement=Пусть <tex>\lambda \leq 1</tex>. Тогда с вероятностью 1 процесс <tex>Y_t</tex> вырождается, т.е. <tex>P(\exists t: Y_t | + | |about=1 |
+ | |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>. | ||
}} | }} | ||
{{Определение | {{Определение | ||
− | |definition='''Ветвящийся процесс на случайном графе.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины с одним и тем же | + | |definition='''Ветвящийся процесс на случайном графе.''' Пусть <tex>Z_1,\dotsc Z_n,\dotsc </tex> {{---}} независимые пуассоновские величины с одним и тем же [[Математическое ожидание случайной величины | математическим ожиданием]] <tex>\lambda</tex>. Положим |
<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>v_2</tex>, и повторим процесс | + | Снова зафиксируем какую-нибудь активную вершину <tex>v_2</tex>, и повторим процесс, не меняя статус остальных уже активных вершин. |
− | Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины. | + | Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.<br> |
+ | Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], этим свойством мы воспользуемся позднее.<br> | ||
− | Обозначим число активных вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число соседей вершины, которую собираемся пометить как неактивную, {{---}} через <tex>Z_t</tex>. Тогда <tex>Y_0 = 1,Y_t = | + | Обозначим число активных вершин в момент времени <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>. | ||
Строка 35: | Строка 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>c < 1</tex>, то найдется такая константа <tex>\beta</tex>, зависящая от <tex>c</tex>, что а.п.н. (асимптотически почти наверное) размер каждой связной компоненты случайного графа не превосходит <tex>\beta \ln n</tex>. |
− | Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma | + | : Если же <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>Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 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 | + | Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta</tex> {{---}} константа, которая будет подобрана далее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер, меньший или равный <tex>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}(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>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \le nP_{n, p}(Y_{t_0} \ge 0)</tex>, достаточно найти такое <tex>\beta</tex>, при котором | + | : (с учетом асимптотики <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> | |
− | <tex>P_{n, p}(Y_{t_0} > 0) = o\left(\ | + | : (с учетом центральной предельной теоремы) <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} | ||
− | < | ||
− | <tex>\int\limits_{\ | ||
− | |||
− | |||
Поскольку <tex>c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины | Поскольку <tex>c < 1</tex>, нижний предел интегрирования имеет порядок <tex>\sqrt{t_0}</tex>. Таким образом, весь интеграл не превосходит величины | ||
<tex>e^{−\delta t_0}</tex>. Выберем <tex>\beta</tex> таким, чтобы <tex>e^{−\delta t_0}</tex> оказалось меньше, чем | <tex>e^{−\delta t_0}</tex>. Выберем <tex>\beta</tex> таким, чтобы <tex>e^{−\delta t_0}</tex> оказалось меньше, чем | ||
− | <tex>e^{-2 \ln n} = \dfrac{1}{n^2}</tex>, и в случае <tex>c < 1</tex> теорема доказана. | + | <tex>e^{-2 \ln n} = \dfrac{1}{n^2}</tex>, и в случае <tex>c < 1</tex> теорема доказана.<br> |
− | + | <br> | |
− | |||
− | |||
'''Случай <tex>c > 1</tex>'''. | '''Случай <tex>c > 1</tex>'''. | ||
− | В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что | + | В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что а.п.н. хотя |
− | бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref name="trueproof" /> | + | бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <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_{ | + | <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_{ | + | <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>\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> {{---}} константа. | |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> | |
− | + | \begin{equation*} | |
+ | \begin{cases} | ||
+ | & \text{1) Найдутся такие $c_1, c_2$, что с $p \leq \frac{1}{n}$ $\exists cc: size(cc) \in (c_1\log n; c_2n)$;} \\ | ||
+ | & \text{2) Число вершин в компонентах размера $O(\ln n)$ а.п.н. $\leq cn, c < 1$.} \\ & \quad\:\text{Тогда с $p = 1 - o(1)$ существует компонента связности размера $\Omega (n)$;} \\ | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex> | ||
}} | }} | ||
=== Поиск в ширину === | === Поиск в ширину === | ||
− | + | Рассмотрим граф <tex>G(n, p)</tex>. Проанализируем его структуру по мере роста <tex>p</tex>:<br> | |
− | + | * <tex>p = 0:</tex> граф состоит только из изолированных вершин. С ростом <tex>p</tex> в нем появляются ребра, [[Отношение связности, компоненты связности|компоненты связности]] получающегося леса объединяются.<br> | |
− | Рассмотрим граф <tex>G(n, p)</tex>. Проанализируем его структуру по мере роста <tex>p</tex> | + | * <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 \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>). Если ребро существует, пометим следующую вершину как "открытую". Алгоритм закончит свою работу (обойдет всю компоненту связности), когда множество неисследованных "открытых" вершин станет пустым. | ||
Строка 112: | Строка 121: | ||
=== Проблема поиска в ширину === | === Проблема поиска в ширину === | ||
− | [[Файл:Bfs_problem_on_random_graph.png|300px|thumb| | + | [[Файл: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>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> | ||
− | == | + | == Вероятность исчезновения == |
− | Пользуясь идеями, изложенными в доказательстве леммы, | + | === От поиска в ширину к ветвящимся процессам === |
− | Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество | + | Пользуясь идеями, изложенными в доказательстве [[#lemma1|леммы 1]], перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.<br> |
− | Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее | + | {{Определение |
− | Пусть <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex>. | + | |definition='''Вероятность исчезновения''' (extinction probability) {{---}} вероятность, того, что дерево ветвящегося процесса будет конечным (процесс завершится через конечное время). |
− | + | }} | |
+ | Рассмотрим натуральное случайное число <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> | ||
− | Глубина дерева | + | <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> | ||
− | === | + | === Вычисление вероятности исчезновения === |
− | {{ | + | {{Лемма |
− | | | + | |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> {{---}} производящая функция числа | + | |about=5 |
− | + | |id=th5 | |
− | + | |statement=Рассмотрим дерево, сгенерированное ветвящимся процессом. Пусть <tex>f(x)</tex> {{---}} производящая функция числа потомков каждой вершины, а <tex>k</tex> {{---}} ожидаемое количество потомков в каждой вершине. Тогда верно следующее:<br> | |
+ | <tex> | ||
+ | \begin{equation*} | ||
+ | \begin{cases} | ||
+ | k \le 1 &\text{—$\;$ вероятность исчезновения равна 1, если вероятность} \\ & \;\;\;\;\;\,\text{появления ровно одного ребенка равна $1$;}\\ | ||
+ | k > 1 &\text{—$\;$ вероятность исчезновения является }\\&\;\;\;\;\;\,\text{единственным решением $f(x) = x,\; x \in [0, 1)$;} | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex>. | ||
}} | }} | ||
− | |||
В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины. <br> | В данной статье нами рассматривается простой случай ветвящегося процесса, в котором распределение количества потомков одинаково для каждой вершины. <br> | ||
Обозначим: | Обозначим: | ||
− | * <tex>q</tex> - вероятность исчезновения;<br> | + | * <tex>q</tex> {{---}} вероятность исчезновения;<br> |
− | * <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex> {{---}} количество | + | * <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> | + | * <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> | ||
− | |||
<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</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>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>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>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> | |
− | # <tex>m < 1 | + | # <tex>m = 1 \wedge p_1 = 1</tex> {{---}} вероятность исчезновения <tex> = 0</tex>;<br> |
− | # <tex>m = 1 | ||
# <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" />. |
== Вывод == | == Вывод == | ||
Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе <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> | |
− | + | \begin{equation*} | |
− | + | \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$, процесс не завершится, так как у каждой вершины}\\&\;\;\;\;\;\,\text{найдется по крайней мере один потомок;}\\ | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex> | ||
== См. также == | == См. также == | ||
* [[Случайная величина]] | * [[Случайная величина]] | ||
− | |||
* [[Случайные графы]] | * [[Случайные графы]] | ||
* [[Обход в ширину]] | * [[Обход в ширину]] | ||
* [[Производящая функция]] | * [[Производящая функция]] | ||
− | |||
== Литература == | == Литература == | ||
[[Категория: Дискретная математика]] | [[Категория: Дискретная математика]] | ||
+ | [[Категория: Дискретная математика и алгоритмы]] | ||
+ | [[Категория: Обходы графов]] | ||
+ | [[Категория: Связность в графах]] |
Текущая версия на 19:24, 4 сентября 2022
Теорема о гигантской компоненте
Перед формулировкой основной теоремы данного раздела дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения.
Определение: |
Простейший ветвящийся процесс. Пусть [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