Оре О., Теория графов (Оре О. - Теория графов. 1980)

О.ОреТЕОРИЯ ГРАФОВМ.: Наука. Гл. ред. физ.-мат. лит., 1980, 336 стр.СодержаниеОт редактора русского переводаПредисловиеГлава 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. Соотношения между максимальными графами8911111622253034343639414543515353586470777782878896101101105107109114117117120123126128130Глава 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. Теорема Рамсея13413413814114515015516016717617818418418919119419820220620620821121621621722322723223223724224524824825225425626026026226627027313.6.

Одна задача из теории информации278Глава 14. ХРОМАТИЧЕСКИЕ ГРАФЫ28214.1. Хроматическое число28214.2. Суммы хроматических графов28514.3. Критические графы28914.4. Полиномы раскрашиваний294Глава 15. ГРУППЫ И ГРАФЫ30015.1. Группы автоморфизмов30015.2. Цветные графы Кэли для групп30315.3. Графы с заданными группами30515.4. Реберные отображения307Литература313Именной указатель327Предметный указатель329Предметный указатель- непосредственно предшествующаяАвтоморфизм двойственный 236b 206- обратный 236- следующая за а 206, 216Автоморфизмов группа 300- обратно дефицитная 218Аксиома выбора 118- относящаяся с высотой 91, 92Аксиомы метрики 41- промежуточная 34, 206- структуры 224- разделяющая 112Базис транспозиции 80- разрезающая 112Бернштейна теорема 146Вершина соединяющая (части) 102Биркгофа формула 295- средняя 44Блок 111, 191Вершинная связность 103Блоковое множество 111, 191Вершины бисвязанные 185Брэттона проблема 189- взаимно связанные 185Верхний отрезок 218- несравнимые 193Вершина 11- ориентированно-циклически- внешняя (части) 102реберно связанные 185- внутренняя (маршрута) 34- связанные 36- - (части) 102- сильно связанные 185- дефицитная 170, 204, 218- - циклически связанные 110- достижимая из а 184, 199- смежные 30- - множества А 253, 256- сравнимые 192- изолированная 14- циклически-реберно связанные 105,- инцидентная ребру 12106- конечная (маршрута) 34- эквивалентные по достижимости- - (ребра) 12184- концевая (графа) 77- по а-достижимости 200- кратность 127Вес дерева 85- начальная (маршрута) 34- - в вершине v 85- (ребра) 12Ветвь 78, 85- с весом 85Выбирающая функция 118Галуа замыкания 233- операции замыкания 233- связь 232- - инволютивная 238- - совершенная 234- - в Р 234- соответствие 232- двойственное себе 236Гамильтонов центр 75- цикл 70Гамильтонова цепь 71Гейла — Райзера теорема 183Гомоморфизм 107—111, 189- кратный 108- независимый 109Гомоморфизм простой 108- разделенный 109- связный 109- элементарный независимый 109- - связный 109Гомоморфный образ графа 107Гранди функция 282Граничные точки ребра 11Граф 11- ациклический 189- базисный 194, 206- без циклов 77- бесконечный 16- бисвязный 186- —вершинно) критический 289- взаимно связный 186- воспроизведения 211- всесмежный 261- двудольный 27, 134- двусторонний 134- Дезарга 302- (зависимости) сигналов 279- звездный 23, 263- исключения 127- - максимальный 127- конечный 16- критический 289- локально конечный 16- максимальный сильно сингулярный131- - сингулярный 131- накрывающий 262- неориентированный 12- обратный 15- однородный степени в 18, 21- определяемый взаимнооднозначным отображениемили подстановкой 39- ориентированно-циклическизамкнутый 189- ориентированный 12, 184- Паппа 302- передаточный 279- Петерсена 302- плоский 16- покрывающий 262- полный 14- - ориентированный 14- - с петлями 15- потомства 211- почти однородный 152Граф, произвольно вычерчиваемыйиз вершины а 96- связный 36- сильно ориентированно-циклическизамкнутый 191- - ориентированно-циклическиреберно связный 190- - связный 186- - циклически замкнутый 112- связный 110, 113- смежности ребер 32- смежностный 32- смешанный 13- соединяющий 103- соотнесенный неориентированный15- строгого частичного упорядочения216- транзитивный 191- цветной Кэлли 303- циклически замкнутый 106- частичного упорядочения 216- чередующейся композиции 201- k-раскрашиваемый 282- k-ребро связный 102- k-хроматический 282- l-вершиняо связный 103Графа транзитивное замыкание 192Графы изоморфные 13- реберно изоморфные 307- сингулярно связанные 131- циклически изоморфные 310Группа полная мономиальная 301Двойственное разбиение (числа) 181Двойственность между вершинами иребрами графа G 32Декартова сумма графов 51Декартово произведение графов 50Дерево 77- максимальное 128- с корнем 78- Хусими 114Дефицит 138, 202- максимальный 139- множества А относительно В 257- - - - - максимальный 257Дефицит обратный 203- ребер 259Дефицитов ограниченность 139Деформация 208- простая 208- циклическая (паросочетания) 169Диаметр 43, 82- протяженности 45Дилворта теорема 220Дирака теорема 116Дисперсия 44Дихотомия по полу 212Дополнение (элемента) 237- - ортогональное 237- - полярное 237- части 23Дополнительная часть 23Дуга 12Душника — Миллера теорема 227Дюбрейля условие шестиугольника247Жордапа — Гельдера свойства 208,210, 216- - теорема для главных рядов вгруппах 211- - - - композиционных рядов 210Задача Киркмана см.

Киркманазадача 268- о браке или о танцах 147- о бродячем торговце (окоммивояжере) 71- о движении транспорта 187- о Кёнигсбергских мостах 9, 53- о лабиринте 57, 64- - - метод Винера 66- - - Терри 57, 66- о минимальном соединении 81- о назначениях 147- о перевозчике 51- о пяти ферзях 262- о разделении 52- о ревнивых мужьях 52Задача о Ханойской башне 52- о шахматном коне 70- Эстер Клейн 277Законы дистрибутивности 228- поглощения 224Замкнутые элементы 234Запрещенная составляющаямножества Е 130Инволюция 237Индекс компонент 47, 289- связности вершины 114Инцидентности отношение 12Исключение конечного типа 127Квазигруппа 166Квазиупорядочение 191Кенига теорема 177, 256Киркмана задача о пансионе длядевушек 268Класс эквивалентности неособый 28- - особый 28- - элемента а 27Клика 266, 276Компактное реберное разделение 196Компонента дефицитная 172- связная 36- совершенная 172Конечность цепей (из вершины) 258- - (между вершинами) 206Контур 35Концевые точки (маршрута) 35- - (ребра) 11Концы (маршрута) 85- (ребра) 11Корень дерева 78Кратность (ребра) 17, 21Куратовского — Хаусдорфа принципмаксимальности см.

Принципмаксимальности Хаусдорфа —Куратовского 120Кэли задача 80- таблица 166- формула 78, 80- цветной граф 303Латинский квадрат 166- - частичный 167- - - максимальный 167Лес 177Лист 106, 189Листовая композиция 108, 190Листовое множество 106, 189- - особое 106Маршрут 34- возвращающийся секущий 252, 255- двусторонне-бесконечный 35- длины n 35- неориентированный 35- нетривиальный 35- односторонне-бесконечный 35- ориентированный 35- циклический 35Матрица бистохастическая 164- инцидентности 31- мер 31, 50- перестановочная 306- смежности (вершин) 30- - ребер 31- стохастическая 164Мангера теорема 252, 256Мера (ребра) 32, 50, 68Метод чередующихся цепей 107Множества, сопоставленные припаросочетании 142- \sigma-вершинно разделенные 252- \tau-реберно разделенные 255Множество без дефицита 140, 257- вершин 11- вполне упорядоченное 117- всесмежное 261- дефицитное 171- доминирующее 260- - минимальное 260- - обратное 261- достижимое 200- зависимое 266- замкнутое 225- критическое 139, 258- - минимальное 140, 173- максимального дефицита 139- накрывающее 269- независимое 219, 266- - максимальное 266Множество, не имеющее d-дефицита179- несвязанное 266- покрывающее 262- полностью зависимое 266- порождающее 185, 218- - минимальное 185, 218- прообразов 107- разделяющее 176, 255- - согласованное 176- - - конечно минимальное 177- - с паросочетанием М 176- различных общих представителей148- ребер разделяющее 255- связанное 266- сильно зависимое 220- соседства 22- субдоминирующее 261- упорядоченное 29- - максимальное 121- частично упорядоченное 29Мост 105Моток 97Мощность (ребра) 31Мультипликативная размерность(частичного упорядочения) 228Наполнение графа G 129Неподвижная точка отображения 40,90Неравенство треугольника 41Нижний отрезок 218Нуль-граф 14Нуль-маршрут 35Ортогональность 237Остов 129Отклонение вершин 44- - среднее 44- ребер среднее 44Отношение антирефлексивное 27,240, 242- ациклическое 216, 242- бинарное 25- включения 28, 184- - множеств 29- двойственное себе 236, 240- дополнительное 25Отношение замкнутое 241- замыкания 225- непосредственного потомства 211- пулевое 25, 242- обратное 26- одинаковости 25- отличия 25- полного упорядочения 117- рефлексивное 27, 240, 242- самотранзитивное 244- симметрическое 26- слабо симметрическое 240- - транзитивное 244- собственного включения 29- строгого включения 29- - частичного упорядочения 29, 216- тождественное 242- транзитивное 26, 242- универсальное 25- упорядочения 29- частичного упорядочения 28, 216- эквивалентности 27, 242- R' следует из отношения R 26- R' содержит отношение R 26Отношений коммутативность 247- слабая коммутативность 247Отношения взаимно транзитивные243- дифункциональные 244- степень 242- транзитивное замыкание 243- Феррерса 246- чередующегося произведения 245Отображение взаимно однозначное39- много-однозначное 88Oтрицание 25Паросочетание 142, 258- вершинно-реберное инцидентное 93- максимальное 168- правильное 143- реберно-вершинное инцидентное 93- совершенное 147Паросочетание частичное 142Паросочетания взаимные 145- инцидентные 93- совместные 178Пересечение отношений 26- частей 23Перманент 162Петля 15- двойная 17- однократная 17Платоновы тела 18Подграф 23- пустой 266Покрывающий суграф графа G 23,262Полная подструктура относительноструктурного пересечения 236Полное кольцо пересечений 225Полуостров 101- ранга k 101Полярность 237Порождающая часть графа 194Порядковая размерность (частичногоупорядочения) 227Порядок вершины при отображении39, 90- графа 44Потомок 211Правильные многогранники 18Предок 211Представление графа G в видеформального произведения 24Принцип включения — исключения125- максимальности Хаусдорфа —Куратовского 120- - Цорна 122- суммы цепи 123- трансфинитной индукции 117Проблема четырех красок 9, 294Произведение графов 48- множеств 12- - декартово 12- - прямое 12- отношений 242- упорядочений 228Пропускная способность ребра 31Протяженность 45Процесс постепенного покрыванияграфа 67Процесс редукции индекса 68- трансфинитного построения 121Путь 35Радиус графа 43- протяженности 45Радо теорема 137Разбиение множества 28Разделяющее множество (в цепимножеств) 118, 252Разложение частичногоупорядочения 217, 220, 222- - - независимое 222Рамсея теорема 273Раскраски функция 282Раскрашиваний полипом 294, 297Расстояние 41- в смысле данной меры 68Ребер независимое семейство 269- покрывающее семейство 262Реберная связность 102Ребра кратность 17, 21Ребра секущие 248- - размеченные по простым цепям251- сильно ориентированноциклически-реберно связанные190- - циклически-связанные 110- смежные 31Ребра 11- ациклическое 185- внешнее 101- внутреннее 102- входящее в (подходящее к,заходящее в) вершину b 12- выходящее из (отходящее от,исходящее из) вершины а 12Ребро излишнее 194- инцидентное вершине 12- касающееся 101- концевое 77- неориентированное 12- ориентированное 12- ориентированно циклическое 185- разделяющее 105- разрезающее 105Ребро связывающее 101- соединяющее 101- существенное 198- циклическое 105Редеи теоремы 188Редукционное множество 131Редукция дерева 79Родитель 212Сабли Магомета 53, 54Свойство включения 124- или исключения), конечного типа124- исключения 124- - конечного типа 124Серпинского — Пикара теорема 268Сеть 12Сигналы зависимые 279- независимые 279Симметрическая группа 80Сингулярная реберная замена 131- циклическая замена 132Скелет 129Сопоставление при паросочетании142, 258Сочетания k-cвязанные 267Ствол дерева 78Степень (графа) в вершине а 17, 21- - - - - локальная 17, 21- однородного графа 18, 21Структура 224- дистрибутивная 228- полная 224- с дополнениями 237Структурная операция 223Структурное объединение 223- пересечение 223Суграф 22, 202- однородной первой степени 147- покрывающий 23, 263- - собственный 265Сумма отношений 26- частей 23- - прямая 24- - - по ребрам 24- элементов матрицы по столбцам164Сумма элементов матрицы построкам 164- - - полная 164Суммируемое по цепи свойство 123,124Теорема о вершинном разделении252- о гомоморфизме 109, 190- о паросочетании 138, 141- о реберном разделении 254- о секущих цепях 248- о системах различныхпредставителей 144Терм-граф 160Терм-ранг 161Транзитивное замыкание графа 191- - отношения 243Транспозиция 80- двух вершин 42Трансфинитное построение 121Турана теорема 270Удвоения процесс 16Узел 12Уитни выражение для полиномараскрашиваний 296- теорема 308Упорядочение слабое 192Фактор 24Феррерса диаграмма 246- отношения 246Функции дефицита 138Харари соотношение 114Хаусдорфа — Куратовского принципмаксимальности см.