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

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

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

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

См. также

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