Обложка Колчин В.Ф. Случайные графы
Id: 265219
799 руб.

Случайные графы. Изд. 3

URSS. 2021. 256 с. ISBN 978-5-9710-8042-8.
  • Твердый переплет

Аннотация

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

Книга рекомендуется специалистам в области ...(Подробнее)вероятностной комбинаторики и ее применений, инженерам, студентам старших курсов физико-математических и технических вузов.


Содержание
Предисловие5
Глава 1. Обобщенная схема размещения и компоненты случайных графов9
1.1. Вероятностный подход к перечислительным задачам комбинаторики9
1.2. Обобщенная схема размещения25
1.3. Связность графов и обобщенная схема размещения34
1.4. Леса из некорневых деревьев43
1.5. Размеры деревьев в случайном лесе55
1.6. Максимальный размер деревьев в случайном лесе62
1.7. Графы с одноцикловыми компонентами73
1.8. Графы с компонентами двух типов85
1.9. Замечания и литературные ссылки102
Глава 2. Эволюция случайных графов108
2.1. Докритические графы108
2.2. Критические графы114
2.3. Случайные графы с независимыми ребрами119
2.4. Неравновероятные графы128
2.5. Замечания и литературные ссылки140
Глава 3. Системы случайных линейных уравнений в GF(2)143
3.1. Ранг матрицы и критические наборы143
3.2. Матрицы с независимыми элементами148
3.3. Ранг матрицы с малым числом единиц156
3.4. Циклы и совместность систем случайных уравнений165
3.5. Гиперциклы и совместность систем случайных уравнений178
3.6. Замечания и литературные ссылки187
Глава 4. Случайные подстановки195
4.1. Случайные подстановки и обобщенная схема размещения195
4.2. Число циклов197
4.3. Подстановки с ограничениями на длины циклов207
4.4. Замечания и литературные ссылки211
Глава 5. Уравнения, содержащие неизвестную подстановку220
5.1. Уравнения второй степени220
5.2. Уравнения простой степени226
5.3. Уравнения составной степени237
5.4. Замечания и литературные ссылки241
Литература244
Предметный указатель253

Об авторе
Колчин Валентин Федорович
Доктор физико-математических наук, действительный член Академии криптографии РФ. Окончил механико-математический факультет МГУ и аспирантуру Математического института имени В. А. Стеклова АН СССР, в котором работал с 1961 г. Был заместителем главного редактора журнала «Математические заметки», членом редколлегии журнала «Random structures and algorithms». Организовал журнал «Дискретная математика»; заместитель главного редактора, а в 2004–2013 гг. — главный редактор. Организатор Петрозаводских конференций по вероятностным методам в дискретной математике; активно участвовал в создании и организации работы Института прикладных математических исследований Карельского научного центра РАН.

В. Ф. Колчин — признанный специалист по теории случайных размещений, случайных графов и системам случайных уравнений над конечными полями; автор работ по теории случайных размещений частиц по ячейкам, случайным подстановкам и отображениям, системам дискретных уравнений, локальным предельным теоремам для сумм случайных величин. Он разработал эффективный метод доказательства предельных теорем в комбинаторных схемах, основанный на представлении изучаемых распределений как условных распределений сумм независимых случайных величин. Автор около 40 статей и трех монографий.


Страницы (пролистать)