Содержание

ГЛАВА Ι. ТЕОРИЯ МНОЖЕСТВ

§ 1. Основные понятия теории множеств………………………. 5

§ 2. Соответствия. Функции. Отображения……………………. 12

§ 3. Понятие алгебры. Алгебра множеств Кантора.………….. 23

§ 4. Бинарные отношения.………………………………………. 28

§ 5. Бинарное отношение эквивалентности..…………………… 33

§ 6. Бинарное отношение порядка. Упорядоченные

множества…………………………………………………… 35

§ 7. Решетки (структуры ). Изоморфизм……………………….. 39

§ 8. Отношения (обобщение). Алгебраические

системы………………………………………………………. 43

ГЛАВА ΙΙ. КОМБИНАТОРНЫЙ АНАЛИЗ

§ 1. Основные определения……………..……………………… 49

§ 2. Формулы расчета перестановок и сочетаний.………….. 52

§ 3. Бином и полином.…………………………………………… 56

§ 4. Подстановки………………………………………………… 59

§ 5. Метод включений и исключений………………………… 62

§ 6. Метод производящих функций…………………………… 78

§ 7. Комбинаторная мера информации. Вероятность

искажения информации…………………………………… 94

ГЛАВА ΙІІ. ТЕОРИЯ ГРАФОВ

§ 1. Первоначальные понятия теории графов……………….. . 96

§ 2. Операции над графами. Способы задания графов……….. 101

§ 3. Маршруты, цепи, циклы и другие характеристики

графа…………………………………………………………. 107

§ 4. Алгебраическая форма представления графа...……………112

ГЛАВА ІV. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ ГРАФОВ

§ 1. Эйлеровы графы. Алгоритм Флери. Гамильтоновы

графы. Метод Робертса – Флореса ………………………... 118

§ 2. Пространство циклов графа………………………………... 126

§ 3. Независимое множество вершин графа…………………. 129

§ 4. Вершинное число внешней устойчивости графа…………. 135

§ 5. Плотность графа…………………………………………….. 139

§ 6. Раскраска графа……………………………………………… 142

§ 7. Планарность графа………………………………………….. 145

ГЛАВА V. ОПТИМИЗАЦИОННЫЕ АЛГОРИТМЫ ТЕОРИИ

ГРАФОВ

§ 1. Определение кратчайших путей. Алгоритм

Дейкстры…………………………………………………….. 151

§ 2. Максимальный поток через сеть. Алгоритм

Форда - Фалкерсона…………………………………………. 157

§ 3. Построение остова экстремального веса. Алгоритм

Краскала……………………………………………………… 161

§ 4. Метод ветвей и границ: задача коммивояжера.

Общая модель задачи поиска………………………...…….. 163

§ 5. Применение ориентированных деревьев в задачах

теории кодирования и диагностирования…………………. 174

§ 6. Построения оптимального дерева бинарного поиска.

Алгоритм Гильберта – Мура………………………………. 179

§ 7. Сложность задач теории графов. Задача синтеза

управляющих систем………………………………………. 186

ЛИТЕРАТУРА…………………………………………………………….194

ГЛАВА 1. ТЕОРИЯ МНОЖЕСТВ