От редактора русского перевода Предисловие Глава 1. ОСНОВНЫЕ ПОНЯТИЯ 1.1. Определения 1.2. Локальные степени 1.3. Части и подграфы 1.4. Бинарные отношения 1.5. Матрицы смежности и инцидентности Глава 2. СВЯЗНОСТЬ 2.1. Маршруты, цепи и простые цепи 2.2. Связные компоненты 2.3. Взаимно однозначные отображения 2.4. Расстояния 2.5. Протяженность 2.6. Матрицы и цепи. Произведение графов 2.7. Головоломки Глава 3. ЗАДАЧИ О ЦЕПЯХ 3.1. Эйлеровы цепи 3.2. Эйлеровы цепи в бесконечных графах 3.3. О лабиринтах 3.4. Гамилмоновы циклы Глава 4. ДЕРЕВЬЯ 41. Свойства деревьев 4.2. Центры в деревьях 4.3. Циклический ранг (дипломатическое число) 4.4. Однозначные отображения 4.5. Произвольно вычерчиваемые графы. Глава 5. ЛИСТЫ И БЛОКИ 5.1. Соединяющие ребра и вершины 5.2. Листы 5.3. Гомоморфные образы графа 5.4. Блоки Глава 6. АКСИОМА ВЫБОРА
6.1. Полная упорядоченность
6.2. Принципы максимальности
6.3. Суммируемые по цепи свойства
6.4. Максимальные графы исключения
6.5. Максимальные деревья
6.6. Соотношения между максимальными графами
Глава 7. ТЕОРЕМЫ О ПАРОСОЧЕТАНИЯХ
7.1. Двудольные графы
7.2. Дефициты
7.3. Теоремы о паросочетаниях
7.4. Взаимные паросочетанпя
7.5. Паросочетания в графах частного впда
7.6. Двудольные графы с положительными дефицитами
7.7. Применения к матрицам
7.8. Чередующиеся цепи и максимальные паросочетания
7.9. Разделяющие множества
7.10. Совместные паросочетания
Глава 8. ОРИЕНТИРОВАННЫЕ ГРАФЫ
8.1. Отношение включения и достижимые множества ь:г. Теорема о гомоморфизме
8.3. Транзитивные графы и погружения в отношения упорядочения
8.4. Базисные графы
8.5. Чередующиеся цепи
8.6. Суграфы первой степени в графе
Глава 9. АЦИКЛИЧЕСКИЕ ГРАФЫ
9.1. Базисные графы
9.2. Деформации цепей
9.3. Графы воспроизведения
Глава 10. ЧАСТИЧНАЯ УПОРЯДОЧЕННОСТЬ
10.1. Графы частичных упорядочений
10.2. Представления в виде сумм упорядоченных множеств
10.3. Структуры и структурные операции. Отношения замыкания
10.4. Размерность в частичном упорядочении
Глава 11. БИНАРНЫЕ ОТНОШЕНИЯ II СООТВЕТСТВИЯ ГАЛУА
11.1. Соответствия Галуа
11.2. Связи Галуа для бинарных отношений
11.3. Отношения чередующегося произведения
11.4. Отношения Феррерса
Глава 12. СВЯЗЫВАЮЩИЕ ЦЕПИ
12.1. Теорема о секущих цепях
12.2. Вершинное разделение
12.3. Реберное разделение
12.4. Дефицит
Глава 13. ДОМИНИРУЮЩИЕ МНОЖЕСТВА, ПОКРЫВАЮЩИЕ МНОЖЕСТВА И НЕЗАВИСИМЫЕ МНОЖЕСТВА
13.1. Доминирующие множества
13.2. Покрывающие множества и покрывающие суграфы
13.3. Независимые множества
13.4. Теорема Турапа
13.5. Теорема Рамсея
13.6. Одна задача из теории информации
Глава 14. ХРОМАТИЧЕСКИЕ ГРАФЫ
14.1. Хроматическое число
14.2. Суммы хроматических графов
14.3. Критические графы
14.4. Полиномы раскрашиваний
Глава 15. ГРУППЫ И ГРАФЫ
15.1. Группы автоморфизмов
15.2. Цветные графы Кэли для труп
15.3. Графы с заданными группами
15.4. Реберные отображения
Литература
Именной указатель
Предметный указатель
Ойстин Оре — автор более сотни статей и около десятка книг в различных областях математики. Его исследования по алгебре и математическому анализу способствовали развитию многих отраслей знания, в том числе теории информации и кибернетики. Широкую известность получили написанные им биографии выдающихся математиков Абеля и Кардано, научно-популярная книга «Приглашение в теорию чисел», а также работы в области теории графов, к которым относится и книга «Графы и их применение», многократно переиздававшаяся на многих языках мира, в том числе и на русском. |