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

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

Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения

Определение:

Простейший ветвящийся процесс. Пусть [math]Z_1,\dotsc Z_n,\dotsc [/math] -- независимые пуассоновские величины с одним и тем же средним [math]\lambda[/math]. Положим [math]Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1[/math].

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

Рассмотрим модель [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

См. также

• Случайные графы