Харари Ф. Теория графов (Харари Ф. - Теория графов. 1973)

Ф.ХарариТЕОРИЯ ГРАФОВМ.: Мир, 1973, 300 стр.В последнее время теория графов привлекает все более пристальное вниманиеспециалистов различных областей знания. Наряду с традиционнымиприменениями ее в таких пауках, как физика, электротехника, химия, онапроникла и в науки, считавшиеся раньше далекими от нее, — экономику,социологию, лингвистику и др. Давно известии тесные контакты теории графов стопологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязьсуществует между теорией графов и теоретической кибернетикой (особеннотеорией автоматов, исследованием операций, теорией кодирования, теорией игр).Широко используется теория графов при решении различных задач навычислительных машинах.За последние годы тематика теории графов стала значительно разнообразней;резко увеличилось количество публикаций.Предлагаемая книга написана одним из видных специалистов по дискретнойматематике.

Несмотря на небольшой объем и конспективный характер изложения,книга достаточно полно освещает современное состояние теории графов. Она,безусловно, будет полезна студентам университетов и технических вузов и,несомненно, заинтересует широкие круги научных работников, занимающихсяприложениями дискретной математики.Предисловие редактора переводаВведениеГлава 1.

Открытие!Задача о кёнигсбергских мостахЭлектрические цепиХимические изомеры«Вокруг света»Гипотеза четырех красокТеория графов в двадцатом векеГлава 2. ГрафыТипы графовМаршруты и связностьСтепениЗадача РамсеяЭкстремальные графыГрафы пересеченийОперации над графамиУпражненияГлава 3. БлокиТочки сочленения, мосты и блокиГрафы блоков и графы точек сочлененияУпражнения691313141516171821212627283033353841414546Глава 4. ДеревьяОписание деревьевЦентры и центроидыДеревья блоков и точек сочлененияНезависимые циклы и коциклыМатроидыУпражненияГлава 5. СвязностьСвязность и реберная связностьГрафические варианты теоремы МенгераДругие варианты теоремы МенгераУпражненияГлава 6. РазбиенияУпражненияГлава 7.

Обходы графовЭйлеровы графыГамильтоновы графыУпражненияГлава 8. Реберные графыНекоторые свойства реберных графовХарактеризация реберных графовСпециальные реберные графыРеберные графы и обходыТотальные графыУпражненияГлава 9. Факторизация1-факторизация2-факторизацияДревесностьУпражненияГлава 10. ПокрытияПокрытия и независимостьКритические вершины и ребраРеберное ядроУпражненияГлава 11. ПланарностьПлоские и планарные графыВнешнепланарные графыТеорема Понтрягина — КуратовскогоДругие характеризации пленарных графовРод, толщина, крупность, число скрещиванийУпражненияГлава 12. РаскраскиХроматическое число48485153545759606064707476818383858891919499101103104106106111113116117117120122124126126131133138141148151152Теорема о пяти краскахГипотеза четырех красокТеорема Хивуда о раскраске картОднозначно раскрашиваемые графыКритические графыГомоморфизмыХроматический многочленУпражненияГлава 13. МатрицыМатрица смежностейМатрица инциденцийМатрица цикловОбзор дополнительных свойств матроидовУпражненияГлава 14.

ГруппыГруппа автоморфизмов графаОперации на группах подстановокГруппа графа-композицииГрафы с данной группойСимметрические графыГрафы с более сильной симметриейУпражненияГлава 15. ПеречисленияПомеченные графыТеорема перечисления ПойаПеречисление графовПеречисление деревьевТеорема перечисления степенной группыРешенные и нерешенные задачи перечисления графовУпражненияГлава 16. ОрграфыОрграфы и соединимостьОриентированная двойственность и бесконтурные орграфыОрграфы и матрицыОбзор по проблеме восстановления турнировУпражненияПриложение I. Диаграммы графовПриложение II.

Диаграммы орграфовПриложение III. Диаграммы деревьевСписок литературы и именной указательУказатель обозначенийПредметный указательПредметный указательавтоморфизм графа 190базис коциклов 55155156162164167169172175178178180183186187189193194195198201204206209209211216219224225230232232234237244244248260266268291293- циклов 55блок 41валентность вершины 27вершина графа 22, 126- изолированная 28- инцидентная ребру 22- концевая 28- критическая 121- неподвижная 201- орграфа 232- периферическая 51- центральная 51- центроидная 52вершинная база 237вершины подобные 201- смежные 22, 213вес вершины 52вес функции 213ветвь 56- к вершине 52вихрь 187внешность цикла 134выпуклый полиэдр 130гипотеза Улама 25, 26, 48, 58, 202,244- Хадвигера 161, 162- четырех красок 151, 156—162, 164,167, 172гомоморфизм графа 169- полный порядка л 169- элементарный 169гомоморфный образ графа 196граничный оператор 54грань 127- внешняя 127- внутренняя 127граф асимметрический 190- ациклический 48- базисный 132- бесконечный 36- блоков 45- - и точек сочленения 53- вершинно-критический 121- вершинно-симметрический 201- внешнепланарный 131- - максимальный 131- вполне несвязный 28- гамильтонов 85- геометрически двойственный 138- Давида 29- двудольный 31- дополнительный 29- интервалов 35- клик 34- комбинаторно двойственный 139- критический 167- кубический 28- Леви 205, 206- Мак-Джи 205- направленный 23- неразделимый 41- несводимый 123- однозначно раскрашиваемый 164- одноциклический 58- пересечений 33- Петерсена 113- планарный 127- - максимальный 128- плоский 127- подразбиений 101- полный 29граф полный двудольный 32- - n-дольный 37- полунесводимый 123- помеченный 23- произвольно гамильтонов 89- - проходимый 89- простой 197- реберно-критический 121- реберно-регулярный 202- реберно-симметрический 201- реберный 91, 94- - итерированный 91- регулярный 28- самодополнительный 29- сводимый 123- симметрический 201- составной 197- тороидальный 142- тотальный 103- точек сочленения 45- тривиальный 22- Хивуда 204- эйлеров 83- n-раскрашиваемый 152- n-транзитивный 204- n-унитранзитивный 204- n-хроматический 152- \alpha-перестановочный 206граф-композиция 196графоид 58графы гомеоморфные 132- изоморфные 24, 190- коспектральные 188группа 189- графа 190- вершинная 190- диэдральная 195- знакопеременная 195- конфигураций 213- парная 217- - редуцированная 218- подстановок 190- реберная 191- симметрическая 195- степенная 194- тождественная 195- циклическая 195группы идентичные 190- изоморфные 190дерево 48- блоков и точек сочленения 54- корневое 219- с висячим корнем 220- входящее 235- выходящее 235диагональ блока 47«диаграмма Хассе» 73диаметр 27длина маршрута 27добавление вершины 25- ребра 25дополнение графа 29достижимость 133древесность графа 113дуга 23, 232животное 227замощение решетки, 2, 227звезда (лапа, гроздь) 32изоморфизм 24инвариант 24инцидентность ребра и вершины 22искаженность графа 149источник 235карта плоская 127- - с корневым ребром 227квадрат графа 27квадратный корень графа 38клетка 204количество очков 243клика графа 34кограница 55кограничный оператор 54кодерево 56колесо 63комплекс 20композиция графов 37, 196- групп 194компонента 27- нечетная 108- односторонняя 233- сильная 233- слабая 233конденсация 234контур 233- эйлеров 240конфигурация 213конъюнкция 40, 243корона графов 198коцикл 55крупность (зернистость,шероховатость) 146лемма Бернсайда 212, 214лес 48линия матрицы 71линейный подграф графа 180- - орграфа 179Маршрут 26- замкнутый 26- несовершенный 119- открытый 26- совершенный 119- Y-сводимый 120матрица достижимостей 238- инциденций ISO- коциклов 184- обходов 238- полустепеней захода 239- - исхода 239- разреженная 241- смежностей графа 179- - орграфа 237- циклов 183матричная теорема о деревьях 178,181, 239матроид 57- бинарный 188- графический 180- кографический 180- коциклов графа 57- циклов графа 57- эйлеров 188многочлен деревьев графа 187множество вершин 22- внешне устойчивое 118- внутренне устойчивое 118- независимое 57, 108, 118- разделяющее 64- ребер 22мост 41мультиграф 23наследственное свойство 119надграф 24независимые единицы матрицы 71обхват 27объединение графов 36одноцветный класс 152ожерелье 212—215, 224, 225окрестность вершины 197- замкнутая 197окружение 27орбита 211орграф 232- бесконтурный 235- контрафункциональный 236орграф несвязный 233- обратный 234- односторонний 233- примитивный 246- реберный 245- сильный 233- слабый 233- строго односторонний 244- - слабый 244- функциональный 236- эйлеров 240ориентация графа 246остов 55пара связностей 62паросочетание 119- наибольшее 119перечисляющий ряд дляконфигураций 213- - - фигур 213петля 23подграф 24- линейный 180- остовный 24- порожденный 24- четный 227покрытие вершинное 117- реберное 117полиэдр 127полная раскраска 170полный набор инвариантов 24полугруппа графа 208полуконтур 233полумаршрут 233полупуть 233полустепень захода 232- исхода 232порядок группы 190последователь n-пути 204принцип ориентированнойдвойственности 234, 235произведение графов 36- групп 190- поэлементное 239пространство коциклов 55- циклов 55псевдограф 23путь 233разбиение графа 76- графическое 76- числа 76разрез 55ранг коциклический 56- циклический 55размерность симплекса 20расстояние в графе 27- - орграфе 233раскраска графа 152- плоской карты 156- полная 170- ребер 159- t цветами 172ребра кратные 23- независимые 108- подобные 01, 2- смежные 22ребро графа 22- инцидентное вершине 22- критическое 121- подразбитое 101- симметричное 221род графа 142- полиэдра 142сеть 70система различных представителей72стабилизатор 211степень вершины 27- графа 27- группы 190- ребра 202сток 235стягивание 137- элементарное 137сумма графов 37- групп 193теорема Вине—Коши 181- об интерполяции гомоморфизмов171- о пяти красках 151, 155, 156- перечисления Пойа 211—215, 217,218- - степенной группы 224- Хивуда о раскраске Карт 162—164- BEST 240толщина графа 145точка сочленения 41транзитивная тройка 241треугольник 26- нечетный 95- четный 95турнир 241турнир состязаний 245тэта-граф 85удаление вершины 25- ребра 25укладка графа 126уравнение характеристики неподобиядля деревьев 221- Эйлера—Пуанкаре 57фактор графа 106факторизация графа 106фигура 213формула Оттера 222- Эйлера для полиэдров 127функция связности 62связность 60- локальная 66- односторонняя 233- реберная 60- сильная 233- слабая 233хорда 55хроматический класс 159- многочлен 173цветной граф группы 199центр графа 51центроид дерева 52цепи непересекающиеся 64- реберно-непересекающиеся 64цепь 26- альтернирующая 109- геодезическая 27- простая 26цикл 26- гамильтонов 85- графой да 58- матроида 57- простой 26- эйлеров 83циклическая тройка 241циклический вектор графа 54цикловой индекс группы 212число ахроматическое 170- независимости вершинное 118- - реберное 118- пересечения 33- покрытия вершинного 117- - реберного 117- Рамсея 30- - реберное 104- скрещиваний 148- Хадвигера 177- хроматическое 152- n-хроматическое 177экспоненцирование 208эксцентриситет 51элемент графа 103элементы соседние 103эндоморфизм графа 208ядро вершинное 125- реберное 122цепь, 54база, 1, 237скелет, 1, 127цепь, 1, 54решетка, 2, 227решетка, 3, 227n-клетка 204n-компонента 63n-куб 37n-путь 204n-раскраска 152- реберная 159n-связность 63n-фактор 106n-факторизация 106Р-множество 119.