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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Ф.ХарариТЕОРИЯ ГРАФОВМ.: Мир, 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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги