- Артикул:00-01118866
- Автор: О. Оре
- Обложка: Твердая обложка
- Издательство: Наука (все книги издательства)
- Город: Москва
- Страниц: 336
- Формат: 84х108 1/32
- Год: 1980
- Вес: 553 г
Развернуть ▼
Первые пять глав посвящены наглядному материалу и содержат основные понятия и свойства графов. В шестой главе даются основы теории вполне упорядоченных множеств, которая используется в дальнейшем для строго абстрактного рассмотрения бесконечных графов. Особенно подробно, в главе 7, излагается вопрос о паросочетаниях; естественным ее продолжением является глава 12. В главах 8-11 рассматриваются ориентированные графы, и затем на языке ориентированных графов изучаются частично упорядоченные множества. Последние три, очень интересные, главы (13-15) снова имеют дело с более наглядным материалом.
Книга дает достаточно полное представление о направлениях исследований в теории графов; приводятся упражнения и нерешенные задачи; сделана попытка ввести систематическую терминологию. Написана книга ясным и достаточно доступным математическим языком. Она интересна и нужна специалистам-математикам, инженерам, занимающимся прикладными задачами, и студентам старших курсов университетов и технических вузов.
Содержание
От редактора русского перевода
Предисловие
Глава 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. Деревья
4.1. Свойства деревьев
4.2. Центры в деревьях
4.3. Циклический ранг (цикломатическое число)
4.4. Однозначные отображения
4.5. Произвольно вычерчиваемые графы
Глава 5. Листы и блоки
5.1. Соединяющие ребра и вершины
5.2. Листы
5.3. Гомоморфные образы графа
5.4. Блоки
5.5. Максимальные простые циклы
Глава 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.2. Теорема о гомоморфизме
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. Бинарные отношения и соответствия Галуа
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.Реберные отображения
Литература
Именной указатель
Предметный указатель