Дискретная математика. Теория и практика решения задач по информатике

ПЕДАГОГИЧЕСКОЕ  ОБРАЗОВАНИЕ
С. М. Окулов
ДИСКРЕТНАЯ МАТЕМАТИКА
ТЕОРИЯ И ПРАКТИКА
РЕШЕНИЯ ЗАДАЧ ПО ИНФОРМАТИКЕ
Учебное пособие
5+е издание, электронное
Москва
Лаборатория знаний
2024

УДК 519.85(075)
ББК 22.174я7
О-52
С е р и я
о с н о в а н а
в
2007 г.
Рецензенты:
академик РАО, доктор педагогических наук, профессор А. А. Кузнецов
доктор технических наук, профессор В. Н. Комаров
Окулов С. М.
О-52
Дискретная математика. Теория и практика решения задач
по информатике : учебное пособие / С. М. Окулов. — 5-е изд.,
электрон. — М. : Лаборатория знаний, 2024. — 425 с. — (Педагогическое образование). — Систем. требования: Adobe Reader XI ;
экран 10". — Загл. с титул. экрана. — Текст : электронный.
ISBN 978-5-93208-703-9
В учебном пособии даны ключевые разделы дискретной математики
с практической реализацией алгоритмических решений. Книга написана
на основе лекционного курса и практических занятий для студентов факультета информатики Вятского государственного гуманитарного университета,
а также спецкурса, читаемого автором для школьников, занимающихся
информатикой по углубленной программе.
Для студентов высших учебных заведений, а также старшеклассников,
углубленно изучающих информатику.
УДК 519.85(075)
ББК 22.174я7
Деривативное издание на основе печатного аналога: Дискретная математика. Теория и практика решения задач по информатике : учебное пособие /
С. М. Окулов. — М. : БИНОМ. Лаборатория знаний, 2008. — 422 с. : ил. —
(Педагогическое образование). — ISBN 978-5-94774-498-9.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных
техническими
средствами
защиты
авторских
прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации
ISBN 978-5-93208-703-9
© Лаборатория знаний, 2015

ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . .
7
Глава 1. Основные методы дискретной математики (счет и перебор)
10
1.1.
Счет и перебор
. . . . . . . . . . . . . . . . . .
10
1.2.
Асимптотические обозначения и основная теорема
. .
17
1.3.
Эффект ≪комбинаторного взрыва≫
. . . . . . . . . .
20
Упражнения и задачи
. . . . . . . . . . . . . . . .
22
Комментарии
. . . . . . . . . . . . . . . . . . .
24
Глава 2. Основные комбинаторные принципы и понятия в примерах
25
2.1.
Принципы сложения и умножения
. . . . . . . . .
25
2.2.
Подмножества
. . . . . . . . . . . . . . . . . . .
25
2.3.
Принцип включения и исключения
. . . . . . . . .
26
2.4.
Выборки
. . . . . . . . . . . . . . . . . . . . .
28
2.5.
Размещения с повторениями
. . . . . . . . . . . .
28
2.6.
Размещения без повторений
. . . . . . . . . . . .
29
2.7.
Сочетания без повторений
. . . . . . . . . . . . .
30
2.8.
Бином Ньютона и полиномиальная формула (комбинаторный смысл) . . . . . . . . . . . . . . . . . . .
32
2.9.
Сочетания с повторениями
. . . . . . . . . . . . .
33
2.10.
Перестановки без повторений . . . . . . . . . . . .
33
2.11.
Перестановки с повторениями
. . . . . . . . . . .
38
2.12.
Задача о размещениях
. . . . . . . . . . . . . . .
39
2.13.
Разбиения
. . . . . . . . . . . . . . . . . . . . .
42
2.14.
Разбиения на циклы
. . . . . . . . . . . . . . . .
43
2.15.
Разбиение числа на слагаемые
. . . . . . . . . . .
45
Упражнения и задачи
. . . . . . . . . . . . . . . .
46
Комментарии
. . . . . . . . . . . . . . . . . . .
51

Оглавление
Глава 3. Перечисление комбинаторных объектов
. . . . . . .
52
3.1.
Общая схема генерации комбинаторных объектов
. .
52
3.2.
Генерация перестановок без повторений
. . . . . . .
53
3.3.
Генерация сочетаний без повторений
. . . . . . . .
54
3.4.
Генерация размещений без повторений
. . . . . . .
55
3.5.
Генерация перестановок с повторениями
. . . . . .
57
3.6.
Генерация сочетаний с повторениями
. . . . . . . .
57
3.7.
Генерация размещений с повторениями
. . . . . . .
57
3.8.
Генерация подмножеств
. . . . . . . . . . . . . .
58
3.9.
Генерация разбиений . . . . . . . . . . . . . . . .
60
3.10.
Генерация разбиений на циклы
. . . . . . . . . . .
66
3.11.
Генерация разбиений числа на слагаемые
. . . . . .
73
Упражнения и задачи
. . . . . . . . . . . . . . . .
74
Комментарии
. . . . . . . . . . . . . . . . . . .
75
Глава 4. Рекуррентные и нерекуррентные формулы
. . . . . .
76
4.1.
Простые примеры
. . . . . . . . . . . . . . . . .
76
4.2.
Числа Фибоначчи
. . . . . . . . . . . . . . . . .
77
4.3.
Числа Каталана
. . . . . . . . . . . . . . . . . .
82
4.4.
Схема нахождения общего решения линейных рекуррентных уравнений
. . . . . . . . . . . . . . . .
86
4.5.
Производящие функции
. . . . . . . . . . . . . .
90
4.6.
Ладейные полиномы
. . . . . . . . . . . . . . . .
97
4.7.
Аддитивность задач, или динамическое программирование
101
Упражнения и задачи
. . . . . . . . . . . . . . . . 106
Комментарии
. . . . . . . . . . . . . . . . . . . 110
Глава 5. Понятие графа, основные методы просмотра вершин графа 111
5.1.
Терминология
. . . . . . . . . . . . . . . . . . . 111
5.2.
Способы представления графа
. . . . . . . . . . . 112
5.3.
Поиск в глубину
. . . . . . . . . . . . . . . . . . 114
5.4.
Поиск в ширину
. . . . . . . . . . . . . . . . . . 116
5.5.
Основные понятия
. . . . . . . . . . . . . . . . . 117
Упражнения и задачи
. . . . . . . . . . . . . . . . 124
Комментарии
. . . . . . . . . . . . . . . . . . . 129
Глава 6. Деревья
. . . . . . . . . . . . . . . . . . . . . 130
6.1.
Определение дерева
. . . . . . . . . . . . . . . . 130
6.2.
Перечисление остовных деревьев связного помеченного
графа
. . . . . . . . . . . . . . . . . . . . . . . 131
6.3.
Матричная формула Кирхгофа
. . . . . . . . . . . 134

Оглавление
5
6.4.
Алгоритм представления дерева в виде последовательности чисел
. . . . . . . . . . . . . . . . . . . . . 135
6.5.
Остовные деревья минимального веса
. . . . . . . . 137
6.6.
Задача Штейнера
. . . . . . . . . . . . . . . . . 141
Упражнения и задачи
. . . . . . . . . . . . . . . . 143
Комментарии
. . . . . . . . . . . . . . . . . . . 144
Глава 7. Связность
. . . . . . . . . . . . . . . . . . . . 145
7.1.
Вершинная и реберная связность
. . . . . . . . . . 145
7.2.
Метод нахождения блоков графа
. . . . . . . . . . 147
7.3.
Теорема Менгера
. . . . . . . . . . . . . . . . . 149
7.4.
Связность в орграфе
. . . . . . . . . . . . . . . . 151
Упражнения и задачи
. . . . . . . . . . . . . . . . 154
Комментарии
. . . . . . . . . . . . . . . . . . . 155
Глава 8. Циклы
. . . . . . . . . . . . . . . . . . . . . 156
8.1.
Эйлеровы графы
. . . . . . . . . . . . . . . . . . 156
8.2.
Гамильтоновы графы
. . . . . . . . . . . . . . . . 158
8.3.
Фундаментальное множество циклов
. . . . . . . . 161
8.4.
Матроиды
. . . . . . . . . . . . . . . . . . . . . 166
Упражнения и задачи
. . . . . . . . . . . . . . . . 172
Комментарии
. . . . . . . . . . . . . . . . . . . 173
Глава 9. Покрытия и независимость
. . . . . . . . . . . . 174
9.1.
Основные понятия
. . . . . . . . . . . . . . . . . 174
9.2.
Метод генерации всех максимальных независимых множеств вершин графа
. . . . . . . . . . . . . . . . 175
9.3.
Клики
. . . . . . . . . . . . . . . . . . . . . . 179
9.4.
Доминирующие множества
. . . . . . . . . . . . . 180
9.5.
Паросочетания . . . . . . . . . . . . . . . . . . . 185
9.6.
Матроиды трансверсалей
. . . . . . . . . . . . . . 196
9.7.
Диаграмма взаимосвязей между задачами
. . . . . . 198
Упражнения и задачи
. . . . . . . . . . . . . . . . 201
Комментарии
. . . . . . . . . . . . . . . . . . . 203
Глава 10. Планарные графы
. . . . . . . . . . . . . . . . 204
10.1.
Основные понятия
. . . . . . . . . . . . . . . . . 204
10.2.
Формула Эйлера
. . . . . . . . . . . . . . . . . . 204
10.3.
Алгоритм укладки графа на плоскости
. . . . . . . . 206
Упражнения и задачи
. . . . . . . . . . . . . . . . 214
Комментарии
. . . . . . . . . . . . . . . . . . . 215

Оглавление
Глава 11. Раскраска вершин графа
. . . . . . . . . . . . . 216
11.1.
Хроматическое число
. . . . . . . . . . . . . . . . 216
11.2.
Метод правильной раскраски
. . . . . . . . . . . . 217
11.3.
Методы поиска минимальной раскраски
. . . . . . . 219
Упражнения и задачи
. . . . . . . . . . . . . . . . 222
Комментарии
. . . . . . . . . . . . . . . . . . . 223
Глава 12. Кратчайшие пути в графе
. . . . . . . . . . . . 224
12.1.
Постановка задачи. Вывод пути
. . . . . . . . . . . 224
12.2.
Алгоритмы поиска кратчайших путей
. . . . . . . . 226
Упражнения и задачи
. . . . . . . . . . . . . . . . 234
Комментарии
. . . . . . . . . . . . . . . . . . . 235
Глава 13. Потоки в сетях
. . . . . . . . . . . . . . . . . 236
13.1.
Основные понятия и постановка задачи
. . . . . . . 236
13.2.
Алгоритм К. Эдмондса—Р. Карпа
. . . . . . . . . . 237
13.3.
Введение в метод блокирующих потоков или алгоритм
Е. А. Диница
. . . . . . . . . . . . . . . . . . . 244
13.4.
Модификация алгоритма Е. А. Диница
. . . . . . . 252
Упражнения и задачи
. . . . . . . . . . . . . . . . 260
Комментарии
. . . . . . . . . . . . . . . . . . . 262
Ответы и решения
. . . . . . . . . . . . . . . . . . . . 263
Задачи для самостоятельного решения
. . . . . . . . . . . 353
П р и л о ж е н и е 1. Математические факты и доказательства
отдельных теорем
. . . . . . . . . . . . . . . . . 375
П р и л о ж е н и е 2. Описание основных элементов языков
программирования Паскаль, визуального Бейсика и С++
396
Литература
. . . . . . . . . . . . . . . . . . . . . . . 414
Предметный указатель
. . . . . . . . . . . . . . . . . . 416

Надежде Григорьевне Окуловой
посвящаю
ПРЕДИСЛОВИЕ
С момента появления компьютера и начала использования его
для решения самых разнообразных задач получила развитие системная область знаний математики, связанная с программированием.
Компьютер, при всех его огромных возможностях, может работать
только с конечным множеством объектов (задача проецируется на
конечномерный случай), причем на этом множестве объектов должно быть определено отношение порядка [21]. Только в этом случае
проблема (задача) подвластна компьютеру при условии, что найден
эффективный способ ее решения. Эффект «комбинаторного взрыва» показывает, что компьютер бывает бессилен при решении даже
очень простых задач. Обобщая, можно сказать, что практически
компьютер решает только две задачи: подсчет количества объектов определенной природы (счет) или поиск объекта (из известного множества объектов), удовлетворяющего определенным условиям
(перебор).
Потребности практики, а именно программирования, определяют развитие «стыка» информатики и математики. Эта область знаний не исчерпывается одним предметом — «дискретной математикой», но он является характерным, основополагающим.
Структура книги
Главы 1, 2, 3, 4 — это материал по комбинаторике. Первой вводной темой являются проблемы счета и перебора (или выбора).
К этим двум проблемам сводится большинство задач, решаемых
на компьютере. Раскрывается суть «комбинаторного взрыва» —
показывается ограниченность возможностей компьютера. И весь
дальнейший курс строится под лозунгом преодоления этой огра

Предисловие
ниченности. Тема прекрасно «ложится» на компьютерный вариант
практики и служит пропедевтикой всех тем, изучаемых в дальнейшем. При изучении комбинаторных объектов (комбинаторики)
следует, на наш взгляд, не ограничиваться задачами подсчета, рассматривая и вопросы перечисления комбинаторных объектов, а
также задачи вычисления номера комбинаторного объекта в соответствии с установленным отношением порядка так, как это
сделано, например, в работе [20]. Рассмотрение комбинаторных
чисел «плавно подводит» к рекуррентным соотношениям и методам
исчисления конечных сумм.
Завершается курс темой «Алгоритмы на графах» (главы с 5
по 13). Эта тема тесно связана с рассмотренными комбинаторными проблемами. Отметим возможность различного по сложности
уровня обобщения теоретического материала и построения компьютерно-ориентированных практических занятий.
Доказательства теорем приведены в приложении 1. Они даются
автором, как правило, в курсе дискретной математики по специальности «прикладная математика и информатика».
Особенности книги
Книга является учебным пособием по дискретной математике и
написана по результатам педагогической деятельности автора, осуществляемой в рамках:
— спецкурса для школьников старших классов физико-математического лицея;
— курса дискретной математики для студентов педагогической
специальности «учитель информатики»;
— курса дискретной математики для студентов, специализирующихся в прикладной математике и информатике.
Текст книги — это синтез лекционных и практических занятий,
проводимых по всем трем направлениям деятельности. Автор преследовал основную цель — написать просто даже о сложном так,
чтобы пособие было полезно и школьнику, и учителю информатики, и студенту, и преподавателю вуза.
Используемые обозначения
Для записи алгоритмов используется минимальное подмножество языка программирования Паскаль, синтаксис которого счита

Предисловие
9
ется очевидным. Перевод в другие системы программирования не
вызывает трудностей. Соответствие между используемой нотацией
Паскаля и языками C++ и визуальным Бейсиком приведено в приложении 2. Не используются различного рода псевдокоды, которые
есть как в отечественной, так и в переводной литературе, по той
простой причине, чтобы читатель, набрав текст и уточнив логику,
мог получить действующую программу. Заглавные буквы, используемые для выделения конструкций языка, кое-кого приводят в недоумение. Автор осознанно делает это, ибо фрагмент текста при этом
становится не монотонным, а образным и легче воспринимаемым.
Сочетание зрительного образа, вербального разъяснения и действий
с объектом, в данном случае с программой, по мнению психологов,
является наиболее действенным в системе восприятия и запоминания человека.
В фигурных скобках {} даются комментарии. В угловых скобках
<> — фрагменты логики, описанные словами. Если в формулировке задачи не оговариваются параметры входных данных, например
значение n, то право выбора предоставлено читателю.
Благодарности
Автор выражает благодарность Тамаре Николаевне Котельниковой, которая много лет приводит его рукописи в приличный с точки
зрения русского языка вид, а также многочисленным школьникам и
студентам, творчески изучавшим курс. Роман Александрович Веснин, Максим Анатольевич Корчемкин, Артем Николаевич Алалыкин оказали помощь автору в разработке материалов для отдельных
параграфов, за что им огромная признательность. Ульяна Александровна Токмакова помогла автору в оформлении рукописи, профессионально переоформив все рисунки. Особо хотелось бы поблагодарить Ирину Анатольевну Маховую, главного редактора издательства
«БИНОМ. Лаборатория знаний» — ее профессионализм, приложенный к книгам автора, внес в них то, чего им так не хватало много лет.

ГЛАВА 1
ОСНОВНЫЕ МЕТОДЫ ДИСКРЕТНОЙ
МАТЕМАТИКИ (СЧЕТ И ПЕРЕБОР)
1.1. Счет и перебор
Приведем несколько примеров, в которых требуется подсчитать
количество объектов определенной природы.
Пример 1.1. Подсчитать количество последовательностейиз натуральных чисел от 1 до n, в которые каждое из этих чисел входит по одному разу.
На первое место в последовательности можно записать любое из n
чисел; на второе любое из оставшихся n−1 чисел и т. д. Общее количество последовательностей равно произведению 1 · 2 · 3 · . . .· (n −1) · n.
Это произведение обозначают n! (читается как n факториал).
При n = 7 значение n! = 5040, а при n = 8 — уже 40 320. Для вычисления и хранения чисел такого порядка в компьютере использовать величину типа Integer нельзя. Аналогично и с величинами
типа LongInt, так как последнее значение n, для которого можно
сохранить значение факториала, равно 12 (13! = 6 227 020 800). Вычисление для больших значений n рассмотрено в книге [20].
Пример 1.2. Подсчитать количество единиц в двоичном представлении целого положительного числа.
Рассмотрим величины типа Word. Длина двоичного представления чисел равна 16 битам (n = 16). Например, в двоичной последовательности 0101101001001001 содержится 7 единиц.
Первый вариант решения
Const n=16;
Var a, cnt, i:Word;
Begin
ReadLn(a);
cnt:=0;