ГЛАВА 7. Графы ..................
7.1. Определения графов ............. 7.1.1. История теории графов......
7.1.2. Основное определение ......
7.1.3. Смежность................
7.1.4. Диаграммы ...............
7.1.5. Другие определения.........
7.1.6. Изоморфизм графов ........
7.2. Элементы графов................
7.2.1. Подграфы ................
7.2.2. Валентность...............
7.2.3. Маршруты, цепи, циклы......
7.2.4. Расстояние между вершинами .
7.2.5. Связность ................
7.3. Виды графов и операции над графами
7.3.1. Тривиальные и полные графы . .
7.3.2. Двудольные графы..........
7.3.3. Направленные орграфы и сети........
7.3.4. Операции над графами .............
7.4. Представление графов в ЭВМ .............
7.4.1. Требования к представлению графов . . .
7.4.2. Матрица смежности................
7.4.3. Матрица инциденций...............
7.4.4. Списки смежности.................
7.4.5. Массив дуг.
7.4.6. Обходы графов ...................
7.5. Орграфы и бинарные отношения ...........
7.5.1. Графы и отношения ................
7.5.2. Достижимость и частичное упорядочение
7.5.3. Транзитивное замыкание ............
Комментарии .......
Упражнения ........
ГЛАВА 8. Связность.
8.1. Компоненты связности....................
8.1.1. Объединение графов и компоненты связности...................
8.1.2. Точки сочленения...................
8.1.3. Оценка числа ребер через число вершин и число компонент связности.
8.2. Вершинная и реберная связность............
8.2.1. Мосты и блоки.....................
8.2.2. Меры связности....................
8.3. Теорема Менгера..
8.3.1. Непересекающиеся цепи и разделяющие множества.............
8.3.2. Теорема Менгера в «вершинной форме»
8.3.3. Варианты теоремы Менгера..........
8.4. Теорема Холла...
8.4.1. Задача о свадьбах .................
8.4.2. Трансверсаль.....................
8.4.3. Совершенное паросочетание.........
8.4.4. Теорема Холла - формулировка и доказательство...............
8.5. Потоки в сетях...
8.5.1. Определение потока................
8.5.2. Разрезы...
8.5.3. Теорема Форда и фалкерсона ........
8.5.4. Алгоритм нахождения максимального потока...................
8.5.5. Связь между теоремой Менгера и теоремой Форда и фалкерсона . . .
8.6. Связность в орграфах ...................
8.6.1. Сильная, односторонняя и слабая связность ...................
8.6.2. Компоненты сильной связности.......
8.6.3. Выделение компонент сильной связности .....................
8.7. Кратчайшие пути .
8.7.1. Длина дуг..
8.7.2. Алгоритм Флойда..................
8.7.3. Алгоритм Дейкстры ................
Комментарии .......
Упражнения ........
9.2. Ориентированные, упорядоченные и бинарные деревья........
9.1.2. Основные свойства деревьев.........
9.2.1. Ориентированные деревья...........
9.2.2. Эквивалентное определение ордерева.............
9.2.3. Упорядоченные деревья..............
9.2.4. Бинарные деревья ...................
9.3. Представление деревьев в ЭВМ...
9.3.1. Представление свободных, ориентированных и упорядоченных деревьев
9.3.2. Представление бинарных деревьев ....................
9.3.3. Обходы бинарных деревьев ..........
9.3.4. Алгоритм симметричного обхода бинарного дерева....
9.4. Деревья сортировки................
9.4.1. Ассоциативная память.......
9.4.2. Способы реализации ассоциативной памяти ............
9.4.3. Алгоритм бинарного (двоичного) поиска
9.4.4. Алгоритм поиска в дереве сортировки...
9.4.5. Алгоритм вставки в дерево сортировки ....................
9.4.6. Алгоритм удаления из дерева сортировки ................
9.4.7. Вспомогательные алгоритмы для дерева сортировки
9.4.8. Сравнение представлений ассоциативной памяти
9.4.9. Выровненные деревья ...............
9.4.10. Сбалансированные деревья ...............
9.5. Кратчайший остов .............
9.5.1. Определения ...................
9.5.2. Схема алгоритма построения кратчайшего остова
9.5.3. Алгоритм Краскала.......
Комментарии .
Упражнения .....