Сборники трудов ИСП РАН


Исследование максимального размера плотного подграфа случайного графа

Кузюрин Н.Н. (ИСП РАН, Москва, Россия; МФТИ, Московская. обл., Россия)
Лазарев Д.О. (МФТИ, Московская. обл., Россия)

Аннотация

Для описания случайных сетей используется модель случайного графа Эрдёша-Реньи G(n,p). При исследовании современных случайных сетей часто требуется определить размер максимальной плотной подсети. В настоящей статье приводятся оценки максимального размера c-плотного подграфа, асимптотически почти наверно содержащегося в случайном графе  G(n,1/2). Было показано, что при c<1/2 ,  G(n,1/2)  — асимптотически почти наверно c-плотный; получены верхняя и нижняя оценки размера максимального  1/2-плотного подграфа, асимптотически почти наверно. содержащегося в G(n,1/2); а при c>1/2 получена оценка сверху на размер максимального с-плотного подграфа асимптотически почти наверно содержащегося в  G(n,1/2).

Ключевые слова

случайный граф; случайный граф Эрдёша-Реньи; плотность графа; максимальный плотный подграф

Издание

Труды Института системного программирования РАН, том 29, вып. 6, 2017, стр. 213-220.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(6)-12

Полный текст статьи в формате pdf Вернуться к содержанию тома