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