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

Description

Книга посвящена случайным графам, случайным подстановкам, системам случайных линейных уравнений в конечных полях и уравнениям, содержащим неизвестную подстановку. Изложение отличается систематическим использованием обобщенной схемы размещения, при котором многие комбинаторные задачи сводятся к задачам о суммах независимых случайных величин. Предисловие......Page 3 Вероятностный подход к перечислительным задачам комбинаторики......Page 7 Обобщенная схема размещения......Page 22 Связность графов и обобщенная схема размещения......Page 31 Леса из некорневых деревьев......Page 40 Размеры деревьев в случайном лесе......Page 52 Максимальный размер деревьев в случайном лесе......Page 60 Графы с одноцикловыми компонентами......Page 71 Графы с компонентами двух типов......Page 83 Замечания и литературные ссылки......Page 101 Докритические графы......Page 107 Критические графы......Page 113 Случайные графы с независимыми ребрами......Page 118 Неравновероятные графы......Page 128 Замечания и литературные ссылки......Page 139 Ранг матрицы и критические наборы......Page 142 Матрицы с независимыми элементами......Page 147 Ранг матрицы с малым числом единиц......Page 155 Циклы и совместность систем случайных уравнений......Page 165 Гиперциклы и совместность систем случайных уравнений......Page 177 Замечания и литературные ссылки......Page 186 Случайные подстановки и обобщенная схема размещения......Page 194 Число циклов......Page 196 Подстановки с ограничениями на длины циклов......Page 206 Замечания и литературные ссылки......Page 210 Уравнения второй степени......Page 219 Уравнения простой степени......Page 226 Уравнения составной степени......Page 236 Замечания и литературные ссылки......Page 241 Список литературы......Page 243