Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Глава 1. Множества и отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.1. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.1.1. Элементы и множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.1.2. Задание множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.1.3. Парадокс Рассела . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.1.4. Мультимножества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.1.5. Конечные последовательности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2. Алгебра подмножеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2.1. Сравнение множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.2.2. Равномощные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.3. Конечные и бесконечные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.2.4. Счётные и несчётные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.2.5. Мощность конечного множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.2.6. Операции над множествами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.2.7. Разбиения и покрытия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.2.8. Булеан . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.2.9. Свойства операций над множествами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3. Представление множеств в программах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.3.1. Битовые шкалы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.3.2. Представление натуральных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.3.3. Перебор подмножеств заданного множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.3.4. Алгоритм построения бинарного кода Грея . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.3.5. Представление множеств упорядоченными списками . . . . . . . . . . . . . . . . . . . . . . . 47
1.3.6. Проверка включения слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.3.7. Вычисление объединения слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.3.8. Вычисление пересечения слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.3.9. Представление множеств итераторами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.4. Отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.4.1. Упорядоченные пары и наборы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
1.4.2. Прямое произведение множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.4.3. Размеченное объединение множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.4.4. Бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.4.5. Композиция отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.4.6. Свойства отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
1.4.7. Степень отношения и циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.4.8. Ядро отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.4.9. Представление отношений в программах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
1.5. Замыкание и сокращение отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
1.5.1. Транзитивное и рефлексивное замыкание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.5.2. Алгоритм Уоршалла вычисления транзитивного замыкания отношения . . . . . . . . . . 64
1.5.3. Транзитивное сокращение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.5.4. Диаграммы Хассе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
1.6. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
1.6.1. Функциональные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1.6.2. Инъекция, сюръекция и биекция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1.6.3. Образы и прообразы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
1.6.4. Суперпозиция функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.6.5. Степень функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
1.6.6. Представление функций в программах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
1.7. Отношения эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
1.7.1. Классы эквивалентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
1.7.2. Ядро функционального отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1.7.3. Фактормножество . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
1.7.4. Множества уровня . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.7.5. Толерантность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.7.6. Гомоморфизмы и изоморфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.8. Отношения порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.8.1. Предпорядок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.8.2. Частичный и линейный порядок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
1.8.3. Минимальные и наименьшие элементы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
1.8.4. Алгоритм топологической сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
1.8.5. Верхние и нижние границы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
1.8.6. Монотонные и непрерывные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
1.8.7. Наименьшая неподвижная точка функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
1.8.8. Вполне упорядоченные множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
1.8.9. Индукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
1.9. Характеристические функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
1.9.1. Классификация характеристических функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
1.9.2. Характеристические функции множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
1.9.3. Характеристические функции отношений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
1.9.4. Характеристические функции мультимножеств . . . . . . . . . . . . . . . . . . . . . . . . . . . .100
1.9.5. Классификаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100
1.9.6. Нечёткие множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102
Глава 2. Алгебраические структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104
2.1. Алгебры и морфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104
2.1.1. Операции и их носители . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104
2.1.2. Замыкания и подалгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .105
2.1.3. Система образующих . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .106
2.1.4. Свойства операций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107
2.1.5. Гомоморфизмы и изоморфизмы алгебр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108
2.2. Алгебры с одной операцией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .110
2.2.1. Полугруппы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .110
2.2.2. Определяющие соотношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111
2.2.3. Системы подстановок термов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112
2.2.4. Алгоритм Кнута–Бендикса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .114
2.2.5. Моноиды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .116
2.2.6. Группы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117
2.2.7. Действие группы на множестве . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .119
2.2.8. Группа перестановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .119
2.2.9. Перестановочные матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121
2.3. Алгебры с двумя операциями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122
2.3.1. Кольца . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122
2.3.2. Области целостности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123
2.3.3. Поля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .124
2.4. Элементарная теория чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .125
2.4.1. Делимость чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126
2.4.2. Наибольший общий делитель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .127
2.4.3. Наименьшее общее кратное . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129
2.4.4. Простые числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .130
2.4.5. Сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .133
2.4.6. Системы вычетов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .134
2.4.7. Китайская теорема об остатках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .135
2.4.8. Вычисления в остаточных классах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .136
2.4.9. Функция Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .136
2.5. Векторные пространства и модули . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .138
2.5.1. Векторные пространства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .138
2.5.2. Линейные комбинации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .139
2.5.3. Базис и размерность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140
2.5.4. Конечные поля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .141
2.5.5. Модули . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143
2.6. Решётки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144
2.6.1. Дистрибутивные и ограниченные решётки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .144
2.6.2. Решётки с дополнением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .145
2.6.3. Частичный порядок в решётке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .146
2.6.4. Полные решётки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .147
2.6.5. Полурешётки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .147
2.6.6. Булевы алгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149
2.7. Матроиды и жадные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149
2.7.1. Матроиды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .150
2.7.2. Максимальные независимые подмножества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .150
2.7.3. Базисы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151
2.7.4. Жадный алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152
2.7.5. Примеры матроидов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153
Глава 3. Булевы функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155
3.1. Элементарные булевы функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155
3.1.1. Функции алгебры логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155
3.1.2. Существенные и несущественные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . .156
3.1.3. Булевы функции одной переменной . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .157
3.1.4. Булевы функции двух переменных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .157
3.2. Функции k-значной логики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .158
3.2.1. Формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159
3.2.2. Реализация функций формулами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159
3.2.3. Равносильные формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162
3.2.4. Подстановка и замена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163
3.2.5. Алгебра булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .164
3.3. Двойственность и симметрия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165
3.3.1. Двойственные и самодвойственные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165
3.3.2. Реализация двойственной функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .167
3.3.3. Принцип двойственности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .167
3.3.4. Симметрические функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .168
3.4. Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .168
3.4.1. Разложение булевых функций по переменным . . . . . . . . . . . . . . . . . . . . . . . . . . . .168
3.4.2. Минимальные термы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .169
3.4.3. Совершенные нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .170
3.4.4. Эквивалентные преобразования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172
3.4.5. Минимальные дизъюнктивные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .174
3.4.6. Геометрическая интерпретация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .175
3.4.7. Сокращённые дизъюнктивные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .176
3.5. Представление булевых функций в программах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .177
3.5.1. Табличные представления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .177
3.5.2. Строковые представления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .178
3.5.3. Алгоритм вычисления значения булевой функции . . . . . . . . . . . . . . . . . . . . . . . . . .179
3.5.4. Представление булевых функций арифметическими полиномами . . . . . . . . . . . . . .180
3.5.5. Карты Карно . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183
3.5.6. Представление булевой функции на карте Карно . . . . . . . . . . . . . . . . . . . . . . . . . .185
3.5.7. Минимизация формул картами Карно . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .186
3.5.8. Деревья решений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .189
3.6. Полные системы булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192
3.6.1. Замкнутые классы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .192
3.6.2. Полные системы функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .194
3.6.3. Полнота двойственной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195
3.6.4. Теорема Поста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .195
Глава 4. Логические исчисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .198
4.1. Логические связки и кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .199
4.1.1. Высказывания и связки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .199
4.1.2. Формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .199
4.1.3. Интерпретация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .200
4.1.4. Логическое следование и логическая эквивалентность . . . . . . . . . . . . . . . . . . . . . .201
4.1.5. Подстановка и замена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202
4.1.6. Кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202
4.2. Формальные теории . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .206
4.2.1. Определение формальной теории . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .206
4.2.2. Выводимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .207
4.2.3. Интерпретация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .207
4.2.4. Общезначимость и непротиворечивость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
4.2.5. Полнота, независимость и разрешимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
4.3. Исчисление высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
4.3.1. Классическое определение исчисления высказываний . . . . . . . . . . . . . . . . . . . . . .209
4.3.2. Частный случай формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
4.3.3. Алгоритмы унификации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210
4.3.4. Конструктивное определение исчисления высказываний . . . . . . . . . . . . . . . . . . . .212
4.3.5. Производные правила вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .213
4.3.6. Дедукция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .214
4.3.7. Некоторые теоремы исчисления высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . .215
4.3.8. Множество теорем исчисления высказываний . . . . . . . . . . . . . . . . . . . . . . . . . . . .217
4.3.9. Другие аксиоматизации исчисления высказываний . . . . . . . . . . . . . . . . . . . . . . . .218
4.4. Исчисление предикатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
4.4.1. Определение исчисления предикатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
4.4.2. Интерпретация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222
4.4.3. Общезначимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223
4.4.4. Непротиворечивость и полнота чистого исчисления предикатов . . . . . . . . . . . . . . .223
4.4.5. Логическое следование и логическая эквивалентность . . . . . . . . . . . . . . . . . . . . . .224
4.4.6. Теория равенства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225
4.4.7. Формальная арифметика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225
4.4.8. Неаксиоматизируемые теории . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .226
4.4.9. Теоремы Гёделя о неполноте . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .227
4.5. Наивная теория алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .228
4.5.1. Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .228
4.5.2. Вычислимые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .230
4.5.3. Перечислимые множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .231
4.5.4. Разрешимые множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .234
4.5.5. Протокол выполнения алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .235
4.5.6. Программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .236
4.5.7. Невычислимые функции и неразрешимые множества . . . . . . . . . . . . . . . . . . . . . . .238
4.5.8. Истинность и доказуемость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .240
4.5.9. Множество истин арифметики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .242
4.6. Автоматическое доказательство теорем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .244
4.6.1. Постановка задачи автоматического доказательства теорем . . . . . . . . . . . . . . . . .244
4.6.2. Доказательство от противного . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .245
4.6.3. Сведение к дизъюнктам . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .245
4.6.4. Правило резолюции для исчисления высказываний . . . . . . . . . . . . . . . . . . . . . . . .246
4.6.5. Правило резолюции для исчисления предикатов . . . . . . . . . . . . . . . . . . . . . . . . . .247
4.6.6. Опровержение методом резолюций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .248
4.6.7. Дерево вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .249
4.6.8. Алгоритм метода резолюций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .251
Глава 5. Комбинаторный анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252
5.1. Комбинаторные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
5.1.1. Комбинаторные конфигурации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
5.1.2. Размещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254
5.1.3. Размещения без повторений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .254
5.1.4. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .255
5.1.5. Сочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .256
5.1.6. Сочетания с повторениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .257
5.1.7. Дискретная вероятность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .258
5.2. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .259
5.2.1. Циклы в перестановках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .260
5.2.2. Порядок перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262
5.2.3. Инверсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .263
5.2.4. Генерация перестановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .263
5.2.5. Двойные факториалы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265
5.2.6. Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .266
5.2.7. Трудоёмкость в среднем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .268
5.2.8. Гармонические числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269
5.2.9. Оценка в среднем для быстрой сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269
5.3. Биномиальные коэффициенты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .270
5.3.1. Элементарные тождества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271
5.3.2. Бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271
5.3.3. Свойства биномиальных коэффициентов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .272
5.3.4. Треугольник Паскаля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .273
5.3.5. Генерация подмножеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .275
5.3.6. Расширенные биномиальные коэффициенты . . . . . . . . . . . . . . . . . . . . . . . . . . . . .277
5.3.7. Мультимножества и последовательности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .278
5.3.8. Мультиномиальные коэффициенты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .279
5.3.9. Биномиальная система счисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .280
5.4. Разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .281
5.4.1. Числа Стирлинга второго рода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .281
5.4.2. Числа Стирлинга первого рода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .282
5.4.3. Вычисление чисел Стирлинга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .283
5.4.4. Число Белла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .284
5.4.5. Треугольник Белла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .284
5.5. Включения и исключения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .286
5.5.1. Объединение конфигураций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .286
5.5.2. Формула включений и исключений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .287
5.5.3. Число булевых функций, существенно зависящих от всех своих переменных . . . . .288
5.5.4. Комбинации свойств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .289
5.5.5. Беспорядки и субфакториал . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .289
5.6. Формулы обращения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .290
5.6.1. Теорема обращения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .291
5.6.2. Формулы обращения для биномиальных коэффициентов . . . . . . . . . . . . . . . . . . . .291
5.6.3. Формулы для чисел Стирлинга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .292
5.7. Производящие функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .292
5.7.1. Формальные степенные ряды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293
5.7.2. Метод неопределённых коэффициентов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293
5.7.3. Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .294
5.7.4. Числа Каталана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .295
Глава 6. Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .298
6.1. Алфавитное кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .299
6.1.1. Таблица кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .299
6.1.2. Разделимые схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300
6.1.3. Префиксные схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300
6.1.4. Неравенство Крафта–Макмиллана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .301
6.2. Кодирование с минимальной избыточностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .303
6.2.1. Минимизация длины кода сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .303
6.2.2. Цена кодирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .304
6.2.3. Алгоритм Фано . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305
6.2.4. Оптимальное кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .306
6.2.5. Алгоритм Хаффмена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .308
6.3. Помехоустойчивое кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .310
6.3.1. Кодирование с исправлением ошибок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .310
6.3.2. Возможность исправления всех ошибок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .312
6.3.3. Расстояния Левенштейна и Хэмминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .314
6.3.4. Кодовое расстояние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .315
6.3.5. Мощность кодирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .316
6.3.6. Виды кодирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .318
6.3.7. Систематическая форма кодовых сообщений . . . . . . . . . . . . . . . . . . . . . . . . . . . . .320
6.3.8. Коды Хэмминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .321
6.3.9. Исправление одного замещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323
6.4. Сжатие и шифрование данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .324
6.4.1. Сжатие текстов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .324
6.4.2. Предварительное построение словаря . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .324
6.4.3. Алгоритм Лемпела–Зива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .325
6.4.4. Криптография . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .328
6.4.5. Шифрование с помощью случайных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .329
6.4.6. Криптостойкость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .329
6.4.7. Шифрование с открытым ключом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .330
6.4.8. Цифровая подпись . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .332
Глава 7. Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .333
7.1. Определения графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .333
7.1.1. История теории графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .333
7.1.2. Основное определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335
7.1.3. Инцидентность, смежность и дополнение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .336
7.1.4. Диаграмма графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .336
7.1.5. Орграфы, псевдографы, мультиграфы и гиперграфы . . . . . . . . . . . . . . . . . . . . . . .337
7.1.6. Изоморфизм графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .338
7.2. Элементы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .339
7.2.1. Подграфы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .339
7.2.2. Валентность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .340
7.2.3. Маршруты, цепи, циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .341
7.2.4. Связные и несвязные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .342
7.2.5. Расстояние между вершинами, ярусы и диаметр графа . . . . . . . . . . . . . . . . . . . . .342
7.2.6. Эксцентриситет и центр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .343
7.2.7. Степенные последовательности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .343
7.3. Виды графов и операции над графами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .346
7.3.1. Полные и пустые графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .347
7.3.2. Двудольные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .347
7.3.3. Направленные орграфы и сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .348
7.3.4. Операции над графами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .349
7.3.5. Простые циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .351
7.3.6. Рёберные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .352
7.4. Представление графов в программах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .354
7.4.1. Требования к представлению графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .354
7.4.2. Матрица смежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .354
7.4.3. Матрица инциденций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .355
7.4.4. Списки смежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .355
7.4.5. Массив дуг . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .356
7.4.6. Обходы графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .356
7.5. Графы и отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .360
7.5.1. Орграфы и бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .360
7.5.2. Граф инциденций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .362
7.5.3. Гиперграфы и многоместные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .363
7.5.4. Достижимость и частичное упорядочение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .364
7.5.5. Достижимость и транзитивное замыкание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .365
Глава 8. Связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .366
8.1. Компоненты связности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .366
8.1.1. Объединение графов и компоненты связности . . . . . . . . . . . . . . . . . . . . . . . . . . . .366
8.1.2. Точки сочленения, мосты и блоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .367
8.1.3. Вершинная и рёберная связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .371
8.1.4. Оценка числа рёбер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372
8.2. Теорема Менгера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .373
8.2.1. Непересекающиеся цепи и разделяющие множества . . . . . . . . . . . . . . . . . . . . . . .373
8.2.2. Теорема Менгера в «вершинной форме» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .374
8.2.3. Варианты теоремы Менгера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .375
8.3. Паросочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .375
8.3.1. Задачи о свадьбах, трансверсалях и паросочетаниях . . . . . . . . . . . . . . . . . . . . . . .376
8.3.2. Теорема Холла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .376
8.3.3. Устойчивые паросочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .377
8.4. Потоки в сетях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .380
8.4.1. Определение потока . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .380
8.4.2. Разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .381
8.4.3. Теорема Форда–Фалкерсона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .381
8.4.4. Алгоритм нахождения максимального потока . . . . . . . . . . . . . . . . . . . . . . . . . . . . .383
8.4.5. Связь между теоремой Менгера и теоремой Форда–Фалкерсона . . . . . . . . . . . . . .384
8.5. Связность в орграфах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385
8.5.1. Сильная, односторонняя и слабая связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385
8.5.2. Компоненты сильной связности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .386
8.5.3. Выделение компонент сильной связности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .386
8.6. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .388
8.6.1. Взвешенные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .388
8.6.2. Кратчайшие пути в бесконтурном орграфе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .390
8.6.3. Алгоритм Беллмана–Форда . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .391
8.6.4. Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .392
8.6.5. Алгоритм Флойда–Уоршалла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .396
8.6.6. Алгоритмы с предобработкой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .397
Глава 9. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .399
9.1. Свободные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .399
9.1.1. Свободные деревья и их элементы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .399
9.1.2. Основные свойства деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .400
9.1.3. Центр дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .403
9.2. Ориентированные, упорядоченные и бинарные деревья . . . . . . . . . . . . . . . . . . . . . . . . . .403
9.2.1. Ориентированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .403
9.2.2. Эквивалентное определение ордерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .405
9.2.3. Упорядоченные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .405
9.2.4. Бинарные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .408
9.3. Представление деревьев в программах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .408
9.3.1. Представление свободных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .408
9.3.2. Представление упорядоченных корневых деревьев . . . . . . . . . . . . . . . . . . . . . . . . .411
9.3.3. Число упорядоченных ориентированных деревьев . . . . . . . . . . . . . . . . . . . . . . . . .412
9.3.4. Проверка правильности скобочной структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . .414
9.3.5. Представление бинарных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .414
9.3.6. Обходы бинарных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .416
9.3.7. Алгоритмы симметричного обхода бинарного дерева . . . . . . . . . . . . . . . . . . . . . . .417
9.4. Деревья сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .418
9.4.1. Ассоциативная память . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .418
9.4.2. Способы реализации ассоциативной памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . .419
9.4.3. Алгоритм бинарного (двоичного) поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .420
9.4.4. Алгоритм поиска в дереве сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .421
9.4.5. Алгоритм вставки в дерево сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .422
9.4.6. Алгоритм удаления из дерева сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .423
9.4.7. Вспомогательные алгоритмы для дерева сортировки . . . . . . . . . . . . . . . . . . . . . . .425
9.4.8. Сравнение представлений ассоциативной памяти . . . . . . . . . . . . . . . . . . . . . . . . .426
9.5. Специальные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .426
9.5.1. Выровненные и полные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .426
9.5.2. Сбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .428
9.5.3. Балансировка деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .429
9.5.4. Двоичные кучи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .430
9.5.5. Восстановление свойства двоичной кучи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .432
9.5.6. Реализация операций двоичной кучи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .433
9.5.7. Построение графа по степенному ряду . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .434
9.5.8. Дерево отрезков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .435
9.5.9. Оценки эффективности дерева отрезков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .438
9.6. Кратчайший остов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .440
9.6.1. Стягивающие деревья и остовы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .440
9.6.2. Схема алгоритма построения кратчайшего остова . . . . . . . . . . . . . . . . . . . . . . . . .441
9.6.3. Алгоритм Краскала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .442
9.6.4. Алгоритм Прима . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .443
Глава 10. Циклы, независимость и раскраска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .445
10.1. Фундаментальные циклы и разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .445
10.1.1. Циклы и разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .445
10.1.2. Фундаментальная система циклов и циклический ранг . . . . . . . . . . . . . . . . . . . . .447
10.1.3. Фундаментальная система разрезов и коциклический ранг . . . . . . . . . . . . . . . . . .448
10.1.4. Подпространства циклов и коциклов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .450
10.2. Эйлеровы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .451
10.2.1. Эйлеровы графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .451
10.2.2. Алгоритм построения эйлерова цикла в эйлеровом графе . . . . . . . . . . . . . . . . . .452
10.2.3. Оценка числа эйлеровых графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .453
10.3. Гамильтоновы циклы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .453
10.3.1. Гамильтоновы графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .454
10.3.2. Задача коммивояжёра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .455
10.3.3. Теорема Поша . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .456
10.4. Независимые и покрывающие множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .457
10.4.1. Независимые и покрывающие множества вершин и рёбер . . . . . . . . . . . . . . . . . .457
10.4.2. Связь чисел независимости и покрытий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .459
10.4.3. Оценка числа вершинной независимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .460
10.5. Построение независимых множеств вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .461
10.5.1. Постановка задачи отыскания наибольшего независимого множества вершин . . .461
10.5.2. Поиск с возвратами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .462
10.5.3. Улучшенный перебор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .464
10.5.4. Алгоритм построения независимых множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . .465
10.6. Доминирующие множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .466
10.6.1. Минимальное и наименьшее доминирующее множество . . . . . . . . . . . . . . . . . . . .466
10.6.2. Доминирование и независимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .466
10.6.3. Задача о наименьшем покрытии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .467
10.6.4. Связь задачи о наименьшем покрытии с другими задачами . . . . . . . . . . . . . . . . .467
10.7. Раскраска графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .468
10.7.1. Оценки хроматического числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .468
10.7.2. Хроматические числа графа и его дополнения . . . . . . . . . . . . . . . . . . . . . . . . . . .469
10.7.3. Точный алгоритм раскрашивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .470
10.7.4. Приближённые алгоритмы раскрашивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .471
10.8. Планарность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .472
10.8.1. Укладка графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473
10.8.2. Эйлерова характеристика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .473
10.8.3. Теорема о пяти красках . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .475
Указатель основных обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .476
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .479
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .480
