436
правок
Изменения
links semi-fix
Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma = \gamma(c)</tex>, что а.п.н. в случайном графе есть ровно одна компонента размера <tex>\geq\gamma n</tex>. Размер остальных компонент не превосходит <tex>b\ln n</tex>. '''Что такое b, его же нет в определении?'''
|proof=
Приведем здесь идеи<ref>Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.{{---}} М.: МЦНМО, 2013 {{---}} C.330-339 {{---}} ISBN 978-5-4439-0040-7</ref>, изложенные А.М. Райгородским [1], основанные на доказательстве <ref>Karp R. The transitive closure of a random digraph//Random structures and algorithms. 1990. V. 1. P. 73–94.</ref> Р. Карпа [2]. Данное доказательство может быть, не настолько строгое, как приведенное в <ref>Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.</ref>[3], однако
отличается лаконичностью и наглядностью. '''Нерабочие ссылки'''
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка хотя
бы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref>Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.</ref>[3], мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки [[th2| предыдущей теоремы]] и почему она совпадает с одноименной константой из той же теоремы.
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
Если <tex>\alpha > 1 - e^{-c\alpha}</tex>, то вероятность, напротив, будет стремиться к единице.
Таким образом, критическое значение <tex>\alpha</tex>, вплоть до которого есть именно стремление к нулю, {{---}} это решение уравнения <tex>\alpha = 1 - e^{-c\alpha}</tex> или, что равносильно, <tex>1 - \alpha = e^{-c\alpha}</tex>. А это и есть уравнение из [[th2| предыдущей теоремы]], если заменить <tex>\lambda</tex> на <tex>c</tex>.
}}
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичности, их, а также более детальный рассказ можно найти в <ref>Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf</ref> [4]. '''Где найти?'''
{{Утверждение
|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> {{---}} константа.
# <tex>m = 1</tex> <tex>\&</tex> <tex>p_1 = 1</tex> {{---}} вероятность исчезновения <tex> = 0</tex>;<br>
# <tex>m > 1</tex> {{---}} вероятность исчезновения <tex> < 1</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
Подробное описание доказательств данного факта, а также самих утверждений можно найти в <ref>Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf</ref>[4].
== Вывод ==
# <tex>d = 1</tex> <tex>\&</tex> <tex>p_1 = 1</tex> {{---}} вероятность завершения<tex> = 0</tex>;<br>
# <tex>d > 1</tex> {{---}} вероятность исчезновения <tex> < 1</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
== См. также ==
* [[Производящая функция]]
* [[Ветвящийся процесс]]
== Литература ==
# Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 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.
# Алон Н., Спенсер Дж. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.
# Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf
== Примечания ==
{{примечания}}
[[Категория: Дискретная математика]]
