Гашков С.Б. Введение в конструктивную комбинаторику:
Замечательные конструкции современной комбинаторики. Дизайны, двоичные матрицы с экстремальными свойствами, графы с экстремальными свойствами, ортогональные массивы и латинские квадраты, алфавитные и групповые коды

2025. 264 с.

Серия: ФУНДАМЕНТ БУДУЩЕГО: Юбилейная серия в честь 270-летия МГУ имени М.В. Ломоносова

Серия: Книга для школьников... И НЕ ТОЛЬКО!

Онлайн-книга

Аннотация

В настоящей книге будет рассказано о некоторых интересных конструкциях современной комбинаторики. В их числе — блок-схемы (сейчас часто называемые дизайнами) и их частные случаи, например тройки Штейнера и конечные геометрии, тесно связанные с ними двоичные матрицы с экстремальными свойствами, в частности матрицы без прямоугольников с максимальным числом единиц и матрицы Адамара, графы с экстремальными свойствами,... (Подробнее)

Оглавление

Предисловие				4
Глава 1. Несколько олимпиадных задач				5
Глава 2. Разностные множества, конечные геометрии и блок-схемы				8
2.1. Одна теорема о частичных геометриях				15
2.2. Как можно построить конечные плоскости				18
2.3. Неожиданное явление плоскости Фано				21
Глава 3. Примеры разностных множеств и теорема Зингера				23
3.1. Примитивные элементы в конечных полях				24
3.2. Еще два метода построения разностных множеств в циклических группах				29
3.3. Еще некоторые задачи, связанные с разностными множествами				36
Глава 4. Матрицы из нулей и единиц без прямоугольников				38
4.1. Проблема Заранкевича				44
Глава 5. Редкие множества и редкие матрицы				52
Глава 6. Теорема Турана и экстремальные графы				67
6.1. Тройки Штейнера				77
Глава 7. Несколько задач о котах				82
Глава 8. Что такое коды?				87
8.1. Границы для кодов с большими расстояниями				91
8.2. Матрицы Адамара				92
8.3. Эквидистантные и равновесные коды				96
Глава 9. Простейший пример кода, исправляющего одну ошибку				98
Глава 10. Код Хемминга				106
10.1. Двоичные коды Хемминга				106
10.2. q-ичные коды Хемминга				107
Глава 11. Коды Рида—Соломона				110
11.1. Теорема Заранкевича и кодирование				111
Глава 12. Алфавитное кодирование				113
Глава 13. Ортогональные массивы, латинские квадраты и коды				116
Глава 14. Сложность линейных операторов с редкими матрицами				122
Глава 15. Еще не надоели задачи?				133
Глава 16. Графы. Основные понятия				138
Глава 17. Деревья				143
Глава 18. Эйлеровы циклы				148
18.1. Циклы де Брёйна				152
18.2. Гамильтоновы циклы				155
Глава 19. Двудольные графы				160
Глава 20. Булев куб				163
Глава 21. Паросочетания в графах				168
21.1. Реберные раскраски полных графов и замечательное свойство числа 6				177
21.2. Паросочетания в произвольных графах				180
Глава 22. Дружеские отношения и сильно регулярные графы				185
22.1. Задача Московской олимпиады 1960 года				186
22.2. Графы Мура				197
22.3. Теорема о политиках				206
22.4. Задача Московской олимпиады 2012 года				208
22.5. Еще несколько свойств графа Петерсена				211
Глава 23. Теорема Рамсея				217
Глава 24. Потоки и разрезы				229
24.1. Теоремы Менгера и Кёнига				232
24.2. Теорема Дилуорса				234
Глава 25. Независимые множества, диаметры и обхваты				240
Глава 26. Графы-расширители				245
26.1. Пример построения суперконцентраторов				246
26.2. Регулярные (c,d) графы				253
Литература				258

Об авторе

Гашков Сергей Борисович

Доктор физико-математических наук, профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова. Автор и соавтор книг «Примени математику», «Арифметика. Алгоритмы. Сложность вычислений», «Системы счисления и их применения», «Современная элементарная алгебра», «Элементарное введение в эллиптическую криптографию» (URSS; в 2 кн.), «Криптографические методы защиты информации», «Занимательная компьютерная арифметика» (URSS; в 2 кн.), «Геометрические неравенства: Путеводитель в задачах и теоремах» (URSS), «Алгоритмические основы эллиптической криптографии», «Дискретная математика: Учебник и практикум для академического бакалавриата», «Обыкновенные дроби: От Древнего Египта до наших дней» (URSS), «Булев куб, или Булеан: Уникальная комбинаторная конструкция и ее приложения» (URSS), «Введение в конструктивную комбинаторику» (URSS), «Элементарная комбинаторика» (URSS).