УДК 510.6+519.1+519.7
ББК 22.12
А18
Калягин В. А. — доктор физико-математических наук, профессор НИУ ВШЭ
Петренко А. К. — доктор технических наук, профессор,
заведующий отделом «Технологии программирования»
Рецензенты:
Института системного программирования им. В. П. Иванникова РАН
Научный редактор:
Захаров В. А. — доктор физико-математических наук,
профессор МГУ им. М. В. Ломоносова
А18 Дискретная математика. Алгоритмы: теория и практика. – М.: ДМК Пресс,
2019. – 282 с.: ил.
Авдошин С. М., Набебин А. А.
ISBN 978-5-97060-688-9
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики.
Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты
алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста,
нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов
(мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы,
паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто
используемые в практике алгоритмы на графах. Рассматриваются классические комбинаторные
конфигурации и их производящие функции, рекуррентные последовательности.
В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная
математика» на факультете бизнес-информатики, на факультете компьютерных наук Национального
исследовательского университета Высшая школа экономики и на факультете автоматики
и вычислительной техники Национального исследовательского университета Московский энергетический
институт.
Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01
«Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии»,
09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТспециалистов
и разработчиков программных продуктов.
УДК 510.6+519.1+519.7
ББК 22.12
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев
авторских прав.
ISBN 978-5-97060-688-9
© Авдошин С. М., Набебин А. А., 2019
© Оформление, издание, ДМК Пресс, 2019
Стр.3
Содержание
Предисловие.............................................................................................................................9
Введение ................................................................................................................................... 11
1. Множество ................................................................................................................................ 11
2. Функция .................................................................................................................................... 12
3. Отношение ................................................................................................................................ 14
4. Отношение эквивалентности ............................................................................................. 15
5. Каноническое разложение функции ................................................................................ 16
6. Мощность множества. Счетные и несчетные множества ......................................... 17
7. Мощность континуума ......................................................................................................... 18
8. Кардинальные числа. Сравнение мощностей ............................................................... 19
Часть I. ТЕОРИЯ АЛГОРИТМОВ............................................................................... 23
Глава 1. Частично рекурсивные функции...................................................... 24
1.1. Арифметические функции и операции над ними .................................................... 24
1.2. Примитивно рекурсивные функции ............................................................................ 25
1.3. Функции, представимые термами ................................................................................. 27
1.4. Конечная сумма и произведение .................................................................................... 29
1.5. Примитивно рекурсивные предикаты ......................................................................... 31
1.6. Ограниченные кванторы................................................................................................... 31
1.7. Ограниченный оператор µ ............................................................................................... 32
1.8. Подстановка функций в предикат ................................................................................. 33
1.8.1. Кусочное задание функции ...................................................................................... 34
1.8.2. Примитивная рекурсивность некоторых функций и предикатов ............. 35
1.9. Частично рекурсивные функции ................................................................................... 36
Глава 2. Машины Тьюринга ....................................................................................... 38
2.1. Вычисления на машинах Тьюринга .............................................................................. 38
2.2. Синтез машин Тьюринга................................................................................................... 40
2.2.1. Композиция машин .................................................................................................... 40
2.2.2. Ветвление машин ........................................................................................................ 41
2.2.3. Итерация машины ...................................................................................................... 43
2.3. Машины Тьюринга в однобуквенном алфавите ....................................................... 45
2.4. Правильно вычислимые функции................................................................................. 49
2.4.1. Суперпозиция правильно вычислимых функций ........................................... 49
2.4.2. Примитивная рекурсия правильно вычислимых функций ......................... 50
Стр.4
4 Содержание
2.4.3. Минимизация правильно вычислимых функций ........................................... 50
2.4.4. Правильная вычислимость частично рекурсивных функций ..................... 51
2.5. Частичная рекурсивность правильно вычислимых функций ............................. 51
2.5.1. Геделева нумерация ситуаций машины Тьюринга .......................................... 52
2.5.2. Функции программы машины Тьюринга ........................................................... 53
2.5.3. Функции вычисления по программе машины Тьюринга ............................. 53
2.5.4. Функция ситуаций машины Тьюринга ............................................................... 55
2.6. Универсальная частично рекурсивная функция ...................................................... 57
2.6.1. Геделева нумерация машин Тьюринга ................................................................. 57
2.6.2. Функции ситуации машины Тьюринга с номером k ...................................... 58
2.6.3. Построение универсальной функции .................................................................. 60
2.7. Теорема Клини о неподвижной точке и теорема Райса ......................................... 63
2.8. Сложность алгоритмов ...................................................................................................... 64
Глава 3. Рекурсивная перечислимость и разрешимость ................ 68
3.1. Общерекурсивные функции и предикаты .................................................................. 68
3.2. Нумерации наборов натуральных чисел ..................................................................... 70
3.2.1. Нумерации пар натуральных чисел ...................................................................... 70
3.2.2. Нумерация наборов натуральных чисел длины k ............................................ 72
3.2.3. Нумерация конечных последовательностей натуральных чисел .............. 73
3.3. Рекурсивно перечислимые множества ........................................................................ 74
3.4. Рекурсивно перечислимые множества наборов натуральных чисел ................ 76
3.5. Общерекурсивные предикаты ........................................................................................ 78
3.6. Общерекурсивные множества наборов натуральных чисел ................................ 80
3.7. Функции с рекурсивно перечислимым графиком................................................... 81
3.8. Примеры алгоритмически неразрешимых проблем ............................................... 87
3.9. Варианты уточнения понятия алгоритма ................................................................... 89
3.9.1. Ассоциативные исчисления .................................................................................... 89
3.9.2. Системы подстановок Туэ ........................................................................................ 90
3.9.3. Алгоритмическая неразрешимость проблемы тождества
полугрупп и логики предикатов ....................................................................................... 91
3.9.4. Грамматики .................................................................................................................... 95
3.9.5. Продукции Поста ........................................................................................................ 96
3.9.6. Нормальные алгоритмы Маркова ......................................................................... 97
3.9.7. Операторные алгоритмы .......................................................................................... 98
Глава 4. Гедель о неполноте формальных систем ................................. 99
4.1. Аксиоматическая арифметика ........................................................................................ 99
4.2. Алгоритмическая неразрешимость содержательной арифметики ..................103
4.3. Алгоритмическая неразрешимость логики предикатов второго порядка .....107
4.4. Нумерическая выразимость ..........................................................................................108
Стр.5
Содержание 5
Часть II. АЛГОРИТМЫ НА ГРАФАХ ......................................................................112
Глава 5. Способы задания графов .....................................................................113
5.1. Графы, мультиграфы, псевдографы ............................................................................113
5.2. Задание графов ...................................................................................................................115
5.3. Операции над графами ....................................................................................................117
5.4. Маршруты, цепи, циклы, связность ............................................................................117
5.4.1. Алгоритм построения кратчайшей цепи в графе ..........................................119
5.4.2. Алгоритм поиска кратчайшего пути в ориентированном графе ..............120
Глава 6. Обходы графов .............................................................................................127
6.1. Эйлеровы графы ................................................................................................................127
6.2. Алгоритм построения эйлерова цикла .......................................................................128
6.3. Полные циклы и последовательности де Брюйна .................................................132
6.4. Гамильтоновы графы ........................................................................................................134
6.5. Коды Грея .............................................................................................................................135
Глава 7. Деревья ...............................................................................................................137
7.1. Деревья и лес .......................................................................................................................137
7.2. Характеристические свойства деревьев ....................................................................137
7.3. Каркасы и хорды в связном графе ...............................................................................140
Глава 8. Циклы в графах .............................................................................................142
8.1. Линейное пространство двоичных наборов .............................................................142
8.2. Линейное пространство подграфов данного графа ...............................................143
8.3. Подпространство четных подграфов ..........................................................................144
8.4. Циклический ранг графа ................................................................................................147
8.5. Матричная теорема о деревьях .....................................................................................150
Глава 9. Двудольные графы и паросочетания ........................................151
9.1. Двудольные графы ............................................................................................................151
9.2. Паросочетания ....................................................................................................................152
9.3. Алгоритм построения совершенного паросочетания
для двудольного графа ............................................................................................................154
9.4. Системы различных представителей .........................................................................155
9.5. Сети Петри...........................................................................................................................159
9.5.1. Описание сети Петри ...............................................................................................159
9.5.2. Определение сети Петри ........................................................................................160
Глава 10. Планарные графы ...................................................................................165
10.1. Плоские графы .................................................................................................................165
10.2. Формула Эйлера для плоских графов .....................................................................166
Стр.6
6 Содержание
10.3. Критерий планарности Понтрягина–Куратовского ...........................................168
10.4. Алгоритм построения плоского изображения графа .........................................168
Глава 11. Раскраска графов ...................................................................................172
11.1. Хроматическое число и хроматический класс ......................................................172
11.2. Раскраска вершин ...........................................................................................................172
11.3. Верхняя и нижняя оценки хроматического числа ..............................................173
11.3.1. Внутренне устойчивые множества вершин графа ......................................173
11.3.2. Алгоритм вычисления всех наибольших внутренне
устойчивых множеств вершин графа ............................................................................174
11.3.3. Внешне устойчивые множества вершин графа ............................................175
11.3.4. Алгоритм вычисления всех наименьших внешне устойчивых
множеств вершин графа .....................................................................................................176
11.4. Оптимальная раскраска вершин графа ...................................................................177
11.5. Раскрашивание планарных графов ...........................................................................178
Глава 12. Потоки в транспортных сетях ........................................................181
12.1. Двухполюсные сети ........................................................................................................181
12.2. Дивергенция .....................................................................................................................182
12.3. Потоки в сетях ..................................................................................................................183
12.4. Сечения в сетях ................................................................................................................184
12.5. Величина потока и пропускная способность сети ...............................................185
12.6. Максимальный поток ....................................................................................................186
12.6.1. Алгоритм Форда–Фалкерсона .........................................................................187
12.6.2. Помечивающий алгоритм Форда–Фалкерсона ...........................................191
Глава 13. Перечисление графов .........................................................................196
13.1. Число помеченных графов ...........................................................................................196
13.2. Графы и группы подстановок ......................................................................................197
13.2.1. Группы подстановок и лемма Бернсайда ........................................................197
13.2.2. Теорема Пойа ............................................................................................................201
13.2.3. Раскраска вершин куба .........................................................................................204
13.2.4. Составление ожерелий .........................................................................................206
Часть III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ ......................................................209
Глава 14. Порождение комбинаторных конфигураций
и их пересчет .......................................................................................................................210
14.1. Размещения, перестановки, сочетания ....................................................................210
14.2. Правило суммы и правило произведения ..............................................................211
14.3. Подсчет числа размещений, перестановок, сочетаний ......................................211
14.3.1. Число размещений и перестановок без повторений ..................................211
Стр.7
Содержание 7
14.3.2. Число размещений с повторениями .................................................................212
14.3.3. Число сочетаний без повторений ......................................................................212
14.3.4. Число сочетаний с повторениями .....................................................................212
14.3.5. Число перестановок данной спецификации .................................................213
14.3.6. Число размещений данной спецификации ....................................................213
Глава 15. Производящие функции для комбинаторных
конфигураций и для их чисел ................................................................................215
15.1. Аппарат формальных степенных рядов ..................................................................215
15.2. Производящие функции для сочетаний .................................................................216
15.2.1. Сочетания без повторений ..................................................................................216
15.2.2. Сочетания с повторениями с ограничениями
на число повторений ...........................................................................................................217
15.2.3. Сочетания с повторениями без ограничений
на число повторений ...........................................................................................................218
15.3. Производящие функции для размещений с повторениями ............................219
15.4. Числа Стирлинга, Белла, Каталана ..........................................................................221
Глава 16. Комбинаторно-логический аппарат ........................................223
16.1. Включения и исключения ............................................................................................223
16.2. Приложения формулы включений и исключений ..............................................226
16.2.1. Задача о беспорядках .............................................................................................226
16.2.2. Задача о встречах ....................................................................................................227
Глава 17. Рекуррентные последовательности .......................................228
17.1. Конечные разности .........................................................................................................228
17.2. Рекуррентные уравнения .............................................................................................230
17.3. Линейные рекуррентные уравнения с переменными
коэффициентами .......................................................................................................................231
17.4. Метод Лагранжа вариации произвольных постоянных вычисления
частного решения неоднородного уравнения .................................................................238
17.5. Линейные рекуррентные уравнения с постоянными
коэффициентами .......................................................................................................................243
Глава 18. Частично упорядоченные множества,
решетки, булевы алгебры ........................................................................................249
18.1. Отношение частичного порядка ................................................................................249
18.2. Топологическая сортировка вершин бесконтурного орграфа .........................252
18.3. Решетки ..............................................................................................................................253
18.4. Изоморфизм решеток ....................................................................................................255
18.5. Булевы алгебры ...............................................................................................................256
Стр.8
8 Содержание
Приложения ..........................................................................................................................261
1. Графы ........................................................................................................................................261
2. Комбинаторика ......................................................................................................................268
Литература ............................................................................................................................276
Обозначения ........................................................................................................................279
Стр.9