Монография крупного канадского математика, содержащая перспективные методы и конструкции современной теории графов (связность, факторизация, раскраска, планарность и др.). Многие результаты принадлежат автору, активно работающему в области комбинаторной теории. Книга вышла в известной серии "Энциклопедия математики и ее приложений", ряд томов которой издан на русском языке в издательствах "Мир" и "Наука".
Для математиков различных специальностей, инженеров-исследователей, аспирантов и студентов, специализирующихся в области дискретной математики.
Оглавление
От переводчика
От редактора Энциклопедии
Предисловие
Введение
Глава I. Графы и подграфы
I. 1. Определения
I. 2. Изоморфизм
I. 3. Подграфы
I. 4. Соединяющие вершины
I. 5. Компоненты и связность
I. 6. Удаление ребра
I. 7. Перечни неизоморфных связных графов
I. 8. Мосты
I. 9. Замечания
Упражнения
Литература
Глава II. Сжатия и теорема Менгера
II. 1. Сжатия
II. 2. Стягивание ребра
II. 3. Соединяющие вершины
II. 4. Числа разделения
II. 5. Теорема Менгера
II. 6. Теорема Холла
II. 7. Замечания
Упражнения
Литература
Глава III. Двусвязность
III. 1. Разделимые и двусвязные графы
III. 2. Построение двусвязных графов
III. 3. Блоки
III. 4. Ответвления
III. 5. Удаление и стягивание ребра
III. 6. Замечания
Упражнения
Литература
Глава IV. Трехсвязность
IV. 1. m-связность
IV. 2. Некоторые конструкции для трехсвязных графов
IV. 3. 3-блоки
IV. 4. Расслоения
IV. 5. Удаление и стягивание ребер
IV. 6. Теорема о колесе
IV. 7. Замечания
Упражнения
Литература
Глава V. Восстановление
V. 1. Проблема восстановления
V. 2. Теория и практика
V. 3. Лемма Келли
V. 4. Реберное восстановление
V. 5. Замечания
Упражнения
Литература
Глава VI. Орграфы и пути
VI. 1. Орграфы
VI. 2. Пути
VI. 3. Теорема BEST
VI. 4. Матричная теорема о деревьях
VI. 5. Законы Кирхгофа
VI. 6. Отождествление вершин
VI. 7. Теория транспортных сетей
VI. 8. Замечания
Упражнение
Литература
Глава VII. Чередующиеся пути
VII. 1. Курсальность дуг и ребер
VII. 2. Бикурсальные подграфы
VII. 3. Бикурсальные секции
VII. 4. Чередующиеся барьеры
VII. 5. f-факторы и f-барьеры
VII. 6. Теорема об f-факторе
VII. 7. Подграфы с наименьшим дефицитом
VII. 8. Двудольный случай
VII. 9. Теорема Эрдеша --- Галлаи
VII. 10. Замечания
Упражнения
Литература
Глава VIII. Алгебраическая двойственность
VIII. 1. Группы цепей
VIII. 2 Примитивные цепи
VIII. 3. Регулярные группы цепей
VIII. 4. Циклы
VIII. 5. Кограницы
VIII. 6. Ограничения и сжатия
VIII. 7. Алгебраическая двойственность
VIII. 8. Связность
VIII. 9. О теории транспортных сетей
VIII. 10. Матрицы инцидентности
VIII. 11. Матроиды
VIII. 12. Замечания
Упражнения
Литература
Глава IX. Графы и многочлены
IX. 1. V-функции
IX. 2. Хроматический многочлен
IX. 3. Раскраска графов
IX. 4. Потоковый многочлен
IX. 5. Реберная раскраска
IX. 6. Дихрома
