Богульская Н. А. Дискретная математика. Основы теории графов

Титульный......Page 1 Введение......Page 3 1.1. Понятие графа......Page 4 1.2. Способы представления графов......Page 5 1.3. Две теоремы о свойствах степеней вершин......Page 8 1.4. Маршруты, цепи, циклы. Связность графа......Page 9 1.5. Расстояния в графах......Page 11 1.6. Части графа и операции над графами......Page 12 1.7. Графы и бинарные отношения......Page 13 1.8. Изоморфизм графов......Page 14 Контрольные вопросы и задачи......Page 15 2.1. Эйлеровы циклы и цепи......Page 17 2.2. Задачи о лабиринтах и обходы графов......Page 21 2.3. Нахождение кратчайших путей......Page 26 2.4. Гамильтоновы циклы и цепи......Page 28 Контрольные вопросы и задачи......Page 30 3.1. Деревья и их свойства......Page 31 3.2. Бинарные деревья и способы нумерации их вершин......Page 35 3.3. Каркасные деревья......Page 38 4.1. Графы с помеченными вершинами и задачи о раскрасках......Page 41 4.2. Проблема четырёх красок......Page 45 5.1. Двудольные графы......Page 47 5.2. Паросочетания в двудольных графах......Page 49 6.1. Особенности ориентированных графов......Page 50 6.2. Задача о максимальном потоке......Page 51 6.3. Применение графов для анализа программ......Page 56 7.1. Базисные алгоритмы......Page 58 7.2. Сильно связные компоненты......Page 59 7.3. Алгоритм Прима......Page 68 7.4. Нахождение кратчайших путей......Page 71 Библиографический список......Page 81 Оглавление......Page 82