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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Создание страницы. Формулировка теоремы о гигантской компоненте)
 
м (Разобрался с API, расширен спискок источников, исправление опечаток)
Строка 1: Строка 1:
 
== Теорема о гигантской компоненте ==
 
== Теорема о гигантской компоненте ==
−
{{Теорема о гигантской компоненте
+
{{Теорема
−
|statement=Рассмотрим модель <tex>G(n, p)</tex>, то <tex>G(n, p)</tex>. Пусть <tex>p = \dfrac{с}{n}</tex>. Если <tex>c < 1</tex>, то найдется такая константа <tex>\beta = \beta(с)</tex>(c), что а.п.н. размер каждой  связной  компоненты  случайного  графа  не  превосходит <tex>b\ln n</tex>. Если же <tex>c > 1</tex>,то найдется такая константа <tex>\gamma = \gamma(c)</tex>, что а.п.н.  в  случайном  графе  есть  ровно  одна  компонента  размера <tex>\geq\gamma n</tex>.
+
|about=о гигантской компоненте
 +
|statement=Рассмотрим модель <tex>G(n, p)</tex>. Пусть <tex>p = \dfrac{ c }{n}</tex>.
 +
Если <tex>c < 1</tex>, то найдется такая константа <tex>\beta = \beta(с)</tex>, что а.п.н. размер каждой  связной  компоненты  случайного  графа  не  превосходит <tex>b\ln n</tex>.
 +
Если же <tex>c > 1</tex>, то найдется такая константа <tex>\gamma = \gamma(c)</tex>, что а.п.н.  в  случайном  графе  есть  ровно  одна  компонента  размера <tex>\geq\gamma n</tex>. Размер остальных компонент не  превосходит <tex>b\ln n</tex>.
 
|proof=
 
|proof=
 
}}
 
}}
 +
 +
== Литература ==
 +
* Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.{{---}} М.: МЦНМО, 2013 {{---}} C.330-339 {{---}} ISBN 978-5-4439-0040-7
 +
 +
== См. также ==
 +
* [[Случайные графы]]
 +
 +
[[Категория: Дискретная математика]]

Версия 04:33, 20 мая 2020

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

Теорема (о гигантской компоненте):
Рассмотрим модель [math]G(n, p)[/math]. Пусть [math]p = \dfrac{ c }{n}[/math].

Если [math]c \lt 1[/math], то найдется такая константа [math]\beta = \beta(с)[/math], что а.п.н. размер каждой связной компоненты случайного графа не превосходит [math]b\ln n[/math].

Если же [math]c \gt 1[/math], то найдется такая константа [math]\gamma = \gamma(c)[/math], что а.п.н. в случайном графе есть ровно одна компонента размера [math]\geq\gamma n[/math]. Размер остальных компонент не превосходит [math]b\ln n[/math].

Литература

  • Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.— М.: МЦНМО, 2013 — C.330-339 — ISBN 978-5-4439-0040-7

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_гигантской_компоненте._Поиск_в_ширину_в_случайном_графе&oldid=74170»