От переводчика От редактора Энциклопедии Предисловие Введение Глава 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. Дихромат графа
IX. 7. Несколько замечаний о восстановлении
IX. 8. Замечания
Упражнения
Литература
Глава X. Комбинаторные карты
X. 1. Определения и предварительные теоремы
X. 2. Ориентируемость
X. 3. Двойственность
X. 4. Изоморфизм
X. 5. Изображение карт
X. 6. Углы
X. 7. Операции над картами
X. 8. Комбинаторные поверхности
X. 9. Циклы и кограницы
X. 10. Замечания
Упражнения
Литература
Глава XI. Планарность
XI. 1. Пленарные графы
XI. 2. Остовные подграфы
XI. 3. Теорема Жордана
XI. 4. Связность в пленарных картах
XI. 5. Теорема о рассечении
XI. 6. Мосты
XI. 7. Один алгоритм выявления планарности
XI. 8. Периферические циклы в трехсвязных графах
XI. 9. Теорема Куратовского
XI. 10. Замечания
Упражнения
Литература
Предметный указатель
|