Колчин В.Ф. Случайные графы

М. : Физматлит, 2004.— 256 с.

Книга посвящена случайным графам, случайным подстановкам, системам случайных линейных уравнений в конечных полях и уравнениям, содержащим неизвестную подстановку. Изложение отличается систематическим использованием обобщённой схемы размещения, при котором многие комбинаторные задачи сводятся к задачам о суммах независимых случайных величин.
Для специалистов в области вероятностной комбинаторики и её применений, инженеров и студентов старших курсов вузов.

2-е изд.
Серия «Теория вероятностей и математическая статистика».
ISBN 5-9221-0486-1.
Предисловие.
Обобщенная схема размещения и компоненты случайных графов.
Вероятностный подход к перечислительным задачам комбинаторики.
Обобщенная схема размещения.
Связность графов и обобщенная схема размещения.
Леса из некорневых деревьев.
Размеры деревьев в случайном лесе.
Максимальный размер деревьев в случайном лесе.
Графы с одноцикловыми компонентами.
Графы с компонентами двух типов.
Замечания и литературные ссылки.
Эволюция случайных графов.
Докритические графы.
Критические графы.
Случайные графы с независимыми ребрами.
Неравновероятные графы.
Замечания и литературные ссылки.
Системы случайных линейных уравнений в GF (2).
Ранг матрицы и критические наборы.
Матрицы с независимыми элементами.
Ранг матрицы с малым числом единиц.
Циклы и совместность систем случайных уравнений.
Гиперциклы и совместность систем случайных уравнений.
Замечания и литературные ссылки.
Случайные подстановки.
Случайные подстановки и обобщенная схема размещения.
Число циклов.
Подстановки с ограничениями на длины циклов.
Замечания и литературные ссылки.
Уравнения, содержащие неизвестную подстановку.
Уравнения второй степени.
Уравнения простой степени.
Уравнения составной степени.
Замечания и литературные ссылки.
Список литературы.
Предметный указатель.