|
Оглавление
Предисловие редактора перевода Предисловие Часть I. Теория графов 1. Основные понятия 1.1. Основные определения 1.2. Подграфы и дополнения 1.3. Маршруты, цепи, пути и циклы 1.4. Связность и компоненты графа 1.5. Операций над графами 1.6. Специальные графы. 1.7. Точки сочленения и разделимые графы 1.8. Изоморфизм и 2-изоморфизм 1.9 Замечания, касающиеся литературы Упражнения 2. Деревья, разрезающие множества и циклы 2.1. Деревья, остовы и кодеревья 2.2. k-деревья, остовные k-деревья, леса 2.3. Ранг и цикломатическое число 2.4. Базисные циклы 2.5. Разрезающие множества 2.6. Разрез 2.7. Базисные разрезающие множества 2.8. Остовы, циклы и разрезающие множества 2.9. Замечания, касающиеся литературы Упражнения 3. Эйлеровы и гамильтоновы графы 3.1. Эйлеровы графы 3.2. Гамильтоновы графы 3.3. Замечания, касающиеся литературы Упражнения 4. Графы и векторные пространства 4.1. Группы и поля 4.2. Векторные пространства 4.3. Векторное пространство графа 4.4. Размерность подпространств циклов и разрезов 4.5. Связь между подпространствами циклов и разрезов
4.6. Ортогональность подпространств циклов и разрезов
4.7. Замечания, касающиеся литературы
Упражнения
5. Ориентированные графы
5.1. Основные определения и понятия
5.2. Графы и отношения
5.3. Ориентированные и корневые деревья
5.4. Ориентированные эйлеровы графы
5.5. Ориентированные остовы и ориентированные эйлеровы цепи
5.6. Ориентированные гамильтоновы графы
5.7. Ациклические ориентированные графы
5.8. Турниры
5.9. Замечания, касающиеся литературы
Упражнения
6. Матрицы графов
6.1. Матрица инциденций
6.2. Матрица разрезов
6.3. Цикломатическая матрица
6.4. Соотношение ортогональности
6.5. Подматрицы матриц разрезов, инциденций и циклов
6.6. Унимодулярные матрицы
6.7. Число остовов
6.8. Число остовных 2-деревьев
6.9. Число ориентированных остовов в ориентированном графе
6.10 Матрица смежности
6.11. Графы Коутса и Мэзона
6.12. Замечания, касающиеся литературы
Упражнения
7. Планарность и двойственность
7.1. Пленарные графы
7.2. Формула Эйлера
7.3. Теорема Куратовского и другие характеризации планарности
7.4. Двойственные графы
7.5. Планарность и двойственность
7.6. Замечания, касающиеся литературы
Упражнения
8. Связность и паросочетания
8.1. Связность или вершинная связность
8.2. Реберная связность
8.3. Графы с заданными степенями
8.4. Теорема Менгера
8.5. Паросочетания
8.6. Паросочетания в двудольных графах
8.7. Паросочетания графов общего вида
8.8. Замечания, касающиеся литературы
Упражнения
9. Покрытия и раскраски
9.1. Независимые множества и вершинные покрытия
9.2. Реберные покрытия
9.3. Реберная раскраска и хроматический индекс
9.4. Вершинная раскраска,и хроматическое число
9.5. Хроматические полиномы
9.6. Проблема четырех красок
9.7. Замечания, касающиеся литературы
Упражнения
10. Матроиды
10.1. Основные определения
10.2. Фундаментальные свойства
10.3. Эквивалентные системы аксиом
10.4. Двойственность матроидов и графоиды
10.5. Ограничение, сужение и миноры матроида
10.6. Представимость матроидов
10.7. Бинарные матроиды
10.8. Ориентируемые матроиды
10.9. Матроиды и «жадный» алгоритм
10.10. Замечания, касающиеся литературы
Упражнения
Часть II. Теория электрических цепей
11. Графы и электрические цепи
11.1. Преобразование контуров и сечений
11.2. Системы контурных уравнений и уравнений сечений
11.3. Метод смешанных переменных
11.4. Главное разбиение графа
11.5. Уравнения состояния
11.6. Свойство неусиления в резистивных цепях
11.7. Замечания, касающиеся литературы
Упражнения
12. Резистивные n-полюсные цепи
12.1. Введение
12.2. Y-матрицы резистивной n-полюсной цепи ранга п
12.3. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Седербаума)
12.4. Реализация цикломатической матрицы и матрицы сечений
12.5. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Гуиллемина)
12.6. Замечания, касающиеся литературы
Упражнения
13. Функция цепи и чувствительность цепи
13.1. Топологические формулы для.RLC-цепей без взаимных индуктивностеq
13.2. Топологические формулы для общих линейных цепей
13.3. Сопряженная цепь и вычисление чувствительности цепи
13.4. Замечания, касающиеся литературы
Упражнения
Часть III. Теория электрических цепей
14. Алгоритмы анализа графов
14.1. Транзитивное замыкание
14.2. Транзитивная ориентация
14.3. Поиск в глубину
14.4. Двусвязность и сильная связность
14.5. Сводимость графа программы
14.6. Доминаторы в графе программы
14.7. Замечания, касающиеся литературы
Упражнения
15. Оптимизационные алгоритмы
15.1. Кратчайшие пути
15.2. Деревья с минимальной длиной взвешенных путей
15.3. Оптимальные деревья бинарного поиска
15.4. Максимальные паросочетания в графе
15.5. Максимальные паросочетания в двудольном графе
15.6. Совершенное паросочетание, оптимальное назначение и составление расписаний
15.7. Потоки в транспортной сети
15.8. Оптимальное ветвление
15.9. Замечания, касающиеся литературы
Упражнения
Литература
Предметный указатель
|