Оглавление

1. Элементы комбинаторики. 4

1.1. Введение 4

1.2. Два принципа комбинаторики 5

1.3. Функции и размещения 5

1.3.1. Числа Стирлинга первого рода 8

1.3.2. Циклическая структура перестановок 9

1.3.3. Упорядоченные размещения. 11

1.3.4. Сочетания и биномиальные коэффициенты. 14

1.3.5. Полиномиальные коэффициенты 25

1.4. Разбиения 27

1.4.1. Число разбиений 27

1.4.2. Числа Белла. 31

1.5. Принцип включений - исключений 32

1.5.1. Задача о числе беспорядков (Задача о встречах) 36

1.5.2. Количество сюръективных отображений 39

1.5.3. Перестановки с ограничениями на местоположение 40

1.6. Системы представителей множеств 45

1.6.1. Системы различных представителей 45

1.6.2. Системы общих представителей 49

2. Функции алгебры логики 51

2.1. Элементарные высказывания 53

2.2. Элементарные логические операции (функции) 55

2.3. Алгебраические свойства элементарных операций 60

2.4. Разложение функций алгебры логики по переменным 62

2.5. Функциональная полнота систем функций алгебры логики 67

2.5.1. Замкнутые классы. 69

2.5.2. Критерий полноты 77

2.5.3. Представление о результатах Поста 84

3. Элементы теории графов 85

3.1. Степени вершин 87

3.2. О машинном представлении графов. 88

3.3. Поиск в графе 90

3.3.1. Поиск в глубину в графе 91

3.3.2. Поиск в ширину в графе 93

3.4. Пути и циклы 95

3.5. Связность 97

3.6. Деревья 99

3.6.1. Остовное дерево (каркас) 103

3.7. Эйлеровы пути и циклы 107

3.7.1. Aлгоритм построения эйлерова цикла 109

3.8. Гамильтоновы пути и циклы 112

3.9. Нахождение кратчайших путей в графе 121

3.9.1. Алгоритм нахождения расстояния от источника до всех остальных вершин в ориентированном графе с неотрицательными весами ребер 122

3.10. Максимальный поток в сети 124