Графы, сети и алгоритмы

  

Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984, - 454 с.

В книге специалистов из Канады и Индии излагаются основы теории графов и ее применение к сетям с сосредоточенными параметрами в электро- и вычислительной технике. Рассматриваются вопросы цикломатики, связности, устойчивости, вложимости и раскраски графов, что позволяет определить чувствительность сети, а также разработать эффективные алгоритмы анализа и оптимизации графов.

Для специалистов по электротехническим сетям и вычислительной технике.



Оглавление

Предисловие редактора перевода
Предисловие
Часть I. Теория графов
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.4. Базисные циклы
2.5. Разрезающие множества
2.6. Разрез
2.7. Базисные разрезающие множества
2.8. Остовы, циклы и разрезающие множества
2.9. Замечения, касающиеся литературы
Упражнения
3. Эйлеровы и гамильтоновы графы
3.1. Эйлеровы графы
3.2. Гамильтоновы графы
3.3. Замечания, касающиеся литературы
Упражнения
4. Графы и векторные пространства
4.2. Векторные пространства
4.3. Векторное пространство графа
4.4. Размерность подпространств циклов и разрезов
4.5. Связь между подпространствами циклов и разрезов
4.6. Ортогональность подпространств циклов и разрезов
4.7. Замечания, касающиеся литературы
Упражнения
5. Ориентированные графы
5.2. Графы и отношения
5.3. Ориентированные или корневые деревья
5.4. Ориентированные эйлеровы графы
5.5. Ориентированные остовы и ориентированные эйлеровы цепи
5.6. Ориентированные гамильтоновы графы
5.7. Ациклические ориентированные графы
5.8. Турниры
5.9. Замечания, касающиеся литературы
Упражнения
6. Матрицы графов
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.2. Формула Эйлера
7.3. Теорема Куратовского и другие характеризации планарности
7.4. Двойственные графы
7.5. Планарность и двойственность
7.6. Замечания, касающиеся литературы
Упражнения
8. Связность и паросочетания
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.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.2. K-матрицы резистивной (n-полюсной цепи ранга n)
12.3. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Седербаума)
12.4. Реализация цикломатической матрицы и матрицы сечений
12.5. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Гуиллемина)
12.6. Замечания, касающиеся литературы
Упражнения
13. Функции цепи и чувствительность цепи
13.1. Топологические формулы для RLC-цепей без взаимных индуктивностей
13.2. Топологические формулы для общих линейных цепей
13.3. Сопряженная цепь и вычисление чувствительности цепи
13.4. Замечания, касающиеся литературы
Упражнения
Часть III. Теория электрических цепей
14. Алгоритмы анализа графов
14.1. Транзитивное замыкание
14.2. Транзитивная ориентация
14.3. Поиск в глубину
14.4. Двусвязность и сильная связность
14.6. Доминаторы в графе программы
14.7. Замечания, касающиеся литературы
Упражнения
15. Оптимизационные алгоритмы
15.2. Деревья с минимальной длиной взвешенных путей.
15.3. Оптимальные деревья бинарного поиска
15.4. Максимальные паросочетания в графе
15.5. Максимальные паросочетания в двудольном графе
15.6. Совершенное паросочетание, оптимальное назначение и составление расписаний
15.7. Потоки в транспортной сети
15.8. Оптимальное ветвление
15.9. Замечания, касающиеся литературы
Упражнения
ЛИТЕРАТУРА