Теорема о гигантской компоненте. Поиск в ширину в случайном графе
Теорема о гигантской компоненте
Перед формулировкой основной теоремы данного раздела, дадим определение некоторых понятий, которые будут использованы в дальнейшем, а также приведем необходимые далее утверждения
Определение: |
Простейший ветвящийся процесс. Пусть | -- независимые пуассоновские величины с одним и тем же средним . Положим .
Теорема (о гигантской компоненте): |
Рассмотрим модель . Пусть .
Если Если же , то найдется такая константа , что а.п.н. размер каждой связной компоненты случайного графа не превосходит . , то найдется такая константа , что а.п.н. в случайном графе есть ровно одна компонента размера . Размер остальных компонент не превосходит . |
Литература
- Введение в математическое моделирование транспортных потоков: Учебное пособие/Издание 2-е, испр. и доп. А. В. Гасников и др. Под ред. А. В. Гасникова.— М.: МЦНМО, 2013 — C.330-339 — ISBN 978-5-4439-0040-7