ОГЛАВЛЕНИЕ
Введение. Возникновение теории графов и ее место в математике. Цель книги и ее план. Обозначения из теории множеств и математической логики. Полукольца.
Глава 1. Азбука теории графов
§ 1. Определение графа. Понятие графа и его точное определение; вершины, ребра и инцидентор графа. Дуги, петли и звенья. Смежность и инцидентность. Часть графа, подграф и суграф. Изоморфизм. Пример, поясняющий введенные понятия и обозначения. Надграф, сверхграф и объемлющий граф. Конечные графы.
§ 2. Задание графов с помощью матриц. Полукольцо K и матрица инциденций. Матрица соседства вершин; степень и валентность вершины. Матрица смежности. Матрица соседства ребер.
§ 3. Вопросы идентификации графов. Проблемы изоморфизма и изоморфного вхождения, трудность их в общем виде, понятие об их частичных решениях. Общие вопросы, касающиеся информации о графе.
§ 4. Основные типы графов. Орграфы, неорграфы и частично ориентированные графы. Вырожденные и пустые графы. Полуинцидентор и дезориентация графа. Униграфы и мультиграфы, p-графы и p-орграфы. Полные, плотные и квазиполные графы.
§ 5. Обыкновенные графы. Определение обыкновенного графа, вид его матриц соседства и смежности. Обыкновенный граф как множество с антирефлексивным симметричным бинарным отношением. Полные и пустые обыкновенные графы. Скелет произвольного графа.
§ 6. Бихроматические графы. Граф Кёнига и различные его представления. Полные графы Кёнига. Паросочетания. Теорема Кёнига-Оре и ее следствие (теорема Кёнига-Холла). Бихроматические графы общего вида.
§ 7. Графы Бержа. Определение графа Бержа и вид его матрицы смежности. Граф Бержа как множество с произвольным бинарным отношением. Задание графа Бержа с помощью отображения G вершин в подмножества и с помощью аддитивного отображения X подмножеств в подмножества. Определения отображений G и X и обратных им в случае произвольного орграфа. Орскелет. Симметрические и антисимметрические орграфы. Обыкновенные орграфы. Полные графы Бержа. Связь между матрицами смежности орграфа и полученного из него дезориентацией неорграфа; пример на нахождение ориентации требуемого вида с помощью булевой алгебры.
§ 8. Локальная и квазилокальная информация о графах. Характеристика инцидентности графа, I-классы графов. Характеристика смежности, J-классы. Локальная характеристика общего вида. Понятие квазилокальной информации. Проблема Келли. Окрестности и окружения вершин; проблема Трахтенброта и связанная с ней проблема конечности графа.
§ 9. Полные и пустые подграфы. Количества полных и пустых подграфов с заданным числом вершин в обыкновенном графе; количества вилок и антивилок. Дополнительные графы. Количества плотных и квазиполных, вырожденных и пустых подграфов в графе общего вида. Выявление максимальных пустых и полных подграфов у обыкновенного графа по способу Магу-Уэйсмана; проблемы практически эффективного выявления и подсчета полных и пустых подграфов.
§ 10. Части с экстремальными свойствами в графах. Определение максимальных и наибольших, минимальных и наименьших подграфов или суграфов с заданным свойством. Плотность и неплотность. Опоры и опорное число. Накрытия и накрывающее число, квазипаросочетания. Веерные накрытия, теорема Зарецкого. Об оценках Уэйнстейна. Всесмежные подграфы и число всесмежности графа. Полуядро.
Глава 2. Связность графов
§ 11. Маршруты, цепи и циклы. Определение маршрута. Нахождение количеств маршрутов данной длины в графе по его матрице смежности; выявление всех маршрутов. Цепи и циклы, их выявление. Лемма о существовании простой цепи и простого цикла в маршруте. Алгорифмы выявления цепей с помощью разметки вершин.
§ 12. Компоненты связности. Отделенность и неотделенность вершин графа; компоненты, связные графы. Выявление компонент по матрице смежности графа. Теорема Кёнига о бихроматических графах и ее следствия. Решение проблемы Келли для несвязных графов. Одно характеристическое свойство связных графов.
§ 13. Отделимость и соединимость. Определения k-отделимости и k-соединимости вершин в графе. Теорема Менгера и ее простейшие следствия. Перешейки и цикловые ребра.
§ 14. k-связные графы. Определение k-связного графа, критерий k-связности. Три характеристических свойства 2-связных графов. Проблема Адама.
§ 15. k-компоненты, точки сочленения, блоки. k-компоненты, их взаимное расположение в графе. Точки сочленения и блоки, обзор всех типов блоков. Две теоремы о взаимном положении блоков и точек сочленения. Выявление точек сочленения и блоков данного графа. Теорема Дирака о системе циклов при данной вершине.
§ 16. Отрезаемость и сплетаемость. k-отрезаемость и k-сплетаемость вершин, теорема Коцига. k-сплетенные графы и основы k-го порядка.
§ 17. Метрика графа. Расстояние между вершинами графа, нахождение матрицы расстояний по матрице смежности. Вопросы реализации данной метрики с помощью графа, теорема Стоцкого. Центральные и периферийные вершины, радиус и диаметр графа; теорема Жордана о центральных вершинах.
§ 18. Обходы графа. Алгорифм слепого поиска цепи, соединяющей две данные вершины графа. Эйлеровы цепи и эйлеровы циклы, критерий их существования и алгорифм Хоанг Туи для нахождения. Различные обобщения задачи Эйлера. Гамильтоновы цепи и гамильтоновы циклы, некоторые достаточные условия их существования.
Глава 3. Цикломатика графов
§ 19. Цикломатическое число. Определение и простейшие свойства цикломатического числа графа. Критерий полноты обыкновенного графа в терминах цикломатического числа и количества ребер.
§ 20. Графы без циклов. Характеристические свойства графов без циклов. Определение и характеристические свойства дерева. Степени вершин дерева. Простейшие свойства графов без циклов.
§ 21. Метрические свойства деревьев. Центральные и бицентральные деревья. Система расстояний между висячими вершинами дерева, теорема Смоленского - Зарецкого и связанные с ней проблемы.
§ 22. Каркасы. Определение и теоремы существования каркаса графа. Выявление каркасов с помощью разметки вершин графа. Хорды каркаса и ранг графа. Теорема о простом цикле, определяемом каркасом и хордой; преобразования каркасов. О числе связных каркасов без общих ребер.
§ 23. Пространство суграфов и пространство циклов. Определение линейного пространства (группы) суграфов данного графа. Квазициклы и пространство циклов; цикломатические матрицы графа. Теорема Степанца о кратчайшем базисе циклов.
§ 24. Разрезы и пространство разрезов. Определения разреза и простого разреза графа. Теорема о простом разрезе, определяемом ребром каркаса и хордами. Теорема о пересечении цикла с простым разрезом. Квалиразрезы и их свойства, пространство разрезов графа. Матрицы разрезов, связь их с цикломатическими матрицами. Об одном результате Трента.
§ 25. Преобразования матриц графа. Роль матрицы инциденций над полем вычетов по модулю два; теорема и следствия, выясняющие смысл ранга и линейной зависимости столбцов. Преобразование матрицы инциденций с целью выявления каркаса графа и нахождения матрицы разрезов и цикломатической матрицы; перекройка матриц. Пример. Преобразование матрицы разрезов в цикломатическую и наоборот; некоторые свойства графа, непосредственно устанавливаемые по этим матрицам.
§ 26. Обзор и подсчет каркасов. Японский метод выявления всех каркасов графа. Выявление простых циклов. Подсчет каркасов, теорема Лантьер'и - Трента.
§ 27. Графы с заданными разрезами и заданными циклами. Пример восстановления графа по матрице разрезов или по цикломатической матрице, равносильность обеих задач. Операции деления графа по разрезу и деления матрицы по строке. Алгорифм Майеды для установления реализуемости матрицы в виде матрицы разрезов и для нахождения всех реализаций; составление матрицы, преобразующей матрицу разрезов в матрицу инциденций.
Глава 4. Ориентация графов
§ 28. Маршруты с учетом ориентации дуг. Частично ориентированные маршруты и ормаршруты в графе; орцепи, пути и орциклы. Нахождение количеств частично ориентированных маршрутов и ормаршрутов заданной длины по матрице смежности графа. Выявление кратчайших путей с помощью разметки вершин. Эйлеровы пути. Гамильтоновы пути и гамильтоновы орциклы. О различных уточнениях понятия неотделимости вершин в графе.
§ 29. Транзитивные и квазитранзитивные графы. Определения и простейшие свойства транзитивных и квазитранзитивных графов. Критерии транзитивности и квазитранзитивностп в терминах матрицы смежности графа. О свойствах графа, близких к транзитивности.
§ 30. Транзитивное замыкание. Определение транзитивного замыкания, в частности, экономного; теорема существования и единственности. Транзитивные замыкания графов Бержа и неориентированных униграфов. Нахождение транзитивного замыкания по матрице смежности графа. О понятии квазитранзитивного замыкания.
§ 31. Квазитранзитивная и транзитивная ориентируемость. Определения. Граф Гуйя-Ури для заданного обыкновенного графа. Сукомпоненты графа и их свойства. Критерии транзитивной ориентируемости обыкновенного графа, равносильность транзитивной и квазитранзитивной ориентируемости, алгорифм Гилмора-Гофмана для нахождения транзитивной ориентации. Сильная транзитивность, теорема Уулка. Транзитивная и квазитранзитивная ориентируемость графов общего вида; критерий в терминах матрицы смежности.
§ 32. Бикомпоненты орграфа. Достижимость вершин. Определение и критерий бисвязности орграфа. Выявление бикомпонент по матрице смежности. Выявление бикомпонент орграфа, заданного списком дуг, по способу Лейфмана. Граф Герца для заданного орграфа. Структура полных обыкновенных орграфов, теорема Камьона-Фаулкса о гамильтоновых орциклах. Проблема исчерпывающего обзора полных бисвязных орграфов, теорема Байнкее-Харари. Теоремы Редеи о гамильтоновом пути и Гуйя-Ури о гамильтоновом орцикле. Критерий бисвязной ориентируемости графа, минимизация количества бикомпонент.
§ 33. Базы вершин. Ядра. Определение базы вершин орграфа. Базовые бикомпоненты, их существование. Полный обзор всех баз вершин в заданном орграфе, нахождение баз по матрице смежности. Антибазы. Положительные и отрицательные ядра орграфа. Теоремы Рудяну и Ричардсона о существовании и единственности ядер и о сведении проблемы их нахождения.
§ 34. Базы дуг. Два определения базы дуг орграфа, их равносильность; теорема существования. Некоторые достаточные условия единственности базы дуг (теорема Кёнига и ее следствие). Проблема полного обзора баз дуг в заданном орграфе, сведение этой проблемы к случаю бисвязных орграфов. Теорема Барздыня. Верхняя оценка мощности базы дуг бисвязного орграфа (теорема Гольдберга). Практическое выявление баз. Понятие базы ребер у графа общего вида.
§ 35. Теоремы Менгера и Коцига для орграфов. Ориентированные аналоги понятий k-отделимости и т.д. вершин орграфа. Уточнение теорем Менгера и Коцига при учете ориентации ребер графа. Симметрично сплетенные орграфы, проблема Коцига.
§ 36. Растущие ордеревья. Определение растущего ордерева и его корня, характеристические свойства. Поддеревья и сокорневые поддеревья. Равномерно растущие ордеревья, теорема Гольдберга-Лившица. Подсчет растущих каркасов графа, теорема Ботта-Мейберри.
§ 37. Орметрика. Отклонение одной вершины от другой в орграфе; ориентированные аналоги метрики, радиуса и диаметра, Квазибисвязность орграфа как достаточное условие конечности его оррадиуса. Нижние оценки оррадиуса и ордиаметра бисвязного орграфа, теорема Гольдберга и решение проблемы Брэттона. Проблема общего изучения орграфов без орциклов. Задача Бекишева.
§ 38. Пространство обобщенных суграфов. Теорема о базисе пространства циклов, содержащем наибольшее количество орциклов. Проблема устранения орциклов, теорема Гринберга-Дамбита и ее следствие (теорема Фидрих - Адама). Гипотеза Адама. Пространство обобщенных суграфов, матрицы линейно независимых разрезов и циклов над кольцом целых чисел. Подпространства циклов и разрезов в пространстве обобщенных суграфов; соответствующие матрицы орграфа.
Глава 5. Отображения и раскраски графов
§ 39. Гомоморфизмы графов. Определение и простейшие свойства гомоморфных отображений графа в граф и на граф. Группа автоморфизмов графа, теорема Фракта и связанные с ней вопросы. Полугруппа эндоморфизмов графа. Эндоморфизмы графов Бержа. Эндоклассы, теоремы Попова и Глускина; другие исследования и дальнейшая проблематика, связанные с теоремой Глускина. О других результатах, касающихся гомоморфизмов графов.
§ 40. Частичные гомоморфизмы. Раскраски вершин и хроматическое число графа. Стягивание ребер и число Хадвигера. Гипотеза Хадвигера и функция Вагнера. Реберные гомоморфизмы, раскраски ребер и хроматический класс графа. Реберный изоморфизм обыкновенных графов, теорема Уитни-Юнга.
§ 41. Хроматическое число. Независимость хроматического числа от плотности графа. Оценка хроматического числа обыкновенного графа через его степень, теорема Брукса и некоторые ее следствия. О других оценках хроматического числа в терминах степеней вершин графа.
§ 42. Нахождение минимальной раскраски вершин. Об одной принципиально негодной попытке. Отождествление соцветных вершин. Способ Магу. Теорема Плесневича. Теорема Витавера. Теорема Минти. О практической процедуре раскраски.
§ 43. Неполные раскраски вершин. Задача Уэйсмана и ее сведение к перебору максимальных пустых подграфов графа.
§ 44. Раскраска ребер. Сведение общего случая к рассмотрению графов без петель. Двуцветные цепи и леммы Шеннона. Теорема Шеннона о верхней оценке хроматического класса через степень графа, точность этой оценки. Теорема Визинга о верхней оценке хроматического класса р-графа, точность этой оценки при p=1. Хроматический класс полных обыкновенных графов и бихроматических графов, оценка хроматического класса обыкновенного графа через число его вершин. Вывод теоремы Шеннона из теоремы Визинга. Об одновременной раскраске вершин и ребер.
Глава 6. Представления графов
§ 45. Теоретико-множественные и алгебраические представления. Граф пересечений произвольной системы множеств. Граф интервалов; о критериях Леккеркеркера и Боланда, теорема Филмора-Гофмана. Другие графы пересечений. О теоретико-множественном представлении циклически транзитивных графов. Графы сравнимости. О графах делимости и графах коммутации в группоидах. О функциональных графах.
§ 46. Самопредставления. Граф инцидентности. Граф смежности ребер, теоремы Крауса, Уитни, Харари-Нэш-Вильямса, Седлачека и Чартрэнда. Граф, изоморфный своему графу смежности ребер, теорема Гирлянды-Менона. Графы блоков и графы сочленений, теоремы Харари. О результате Гавела и о других самопредставлениях графов.
§ 47. Геометрические и топологические представления. Геометрическое изображение графа в плоскости и в пространстве. О реберных остовах многогранников и n-мерных кубов. Графы пересечений в геометрии. Топологическое представление графа. Подразделение и слияние ребер, комбинаторный и точечный гомеоморфизмы графов. Плоские графы; условие МакЛэйна; двойственные графы и их свойства, условие Уитни; условия Понтрягина-Куратовского и Харари - Татта; теорема о плоских графах. Об алгорифмах расположения графа в плоскости; t-плоские графы (обзор). Неразбивающее расположение графа на поверхности заданного топологического типа. Порядок связности и род графа; расположение полных обыкновенных графов, число полноты поверхности (обзор). Граф как многомерный клеточный комплекс; элементарное подразделение, проблема выявления комбинаторных топологических инвариантов. О других топологических представлениях графов.
§ 48. Проблема четырех красок. Оценки хроматического числа плоского графа, возникновение и формулировка гипотезы четырех красок. Сведение проблемы к случаю триангуляций сферы (плоскости). Теорема Тэйта-Волынского, движение индексов и псевдоалгорифмы раскраски. Теоремы Хивуда и Петерсена. Теорема Аартса-де Гроота. Краткий обзор Других результатов. О плоских 3-хроматических графах (теоремы Грёцша и Грюнбаума). О раскраске вершин графов на различных поверхностях. О хроматическом классе плоского графа.
Заключение первой части
§ 49. Приложения и обобщения графов. Краткий обзор важнейших областей приложения графов и отдельных приложений некоторых вопросов теории графов. Примеры обобщений понятия графа.
§ 50. Дальнейшие перспективы. Алгорифмические и метатеоретические проблемы теории графов; практическая и статистическая эффективность конечных алгорифмов. Важнейшие направления развития современной теории графов. Краткий обзор содержания второй части книги.
Литература
Примечания