М. Свами, К. Тхуласираман - Графы, сети и алгоритмы (1984) (1162196)
Текст из файла
М.Свами, К.ТхуласираманГРАФЫ, СЕТИ И АЛГОРИТМЫМ.: Мир, 1984, 454 стр.В книге специалистов из Канады и Индии излагаются основы теории графов иее применение к сетям с сосредоточенными параметрами в электро- ивычислительной технике. Рассматриваются вопросы цикломатики, связности,устойчивости, вложимости и раскраски графов, что позволяет определитьчувствительность сети, а также разработать эффективные алгоритмы анализа иоптимизации графов.Для специалистов по электротехническим сетям и вычислительной технике.СодержаниеПредисловие редактора перевода5Предисловие7Часть I. Теория графов111.
Основные понятия111.1. Основные определения111.2. Подграфы и дополнения131.3. Маршруты, цепи, пути и циклы161.4. Связность и компоненты графа181.5. Операции Над графами191.6. Специальные графы231.7. Точки сочленения и разделимые графы251.8. Изоморфизм и 2-изоморфизм271.9 Замечания, касающиеся литературы29Упражнения302. Деревья, разрезающие множества и циклы332.1. Деревья, остовы и кодеревья332.2. k-деревья, остовные k-деревья, леса372.3.
Ранг и цикломатическое число392.4. Базисные циклы392.5. Разрезающие множества402.6. Разрез412.7. Базисные разрезающие множества432.8. Остовы, циклы и разрезающие множества442.9. Замечания, касающиеся литературы47Упражнения483. Эйлеровы и гамильтоновы графы503.1. Эйлеровы графы513.2. Гамильтоновы графы553.3. Замечания, касающиеся литературы60Упражнения604. Графы и векторные пространства624.1. Группы и поля624.2. Векторные пространства644.3. Векторное пространство графа4.4.
Размерность подпространств циклов и разрезов4.5. Связь между подпространствами циклов и разрезов4.6. Ортогональность подпространств циклов и разрезов4.7. Замечания, касающиеся литературыУпражнения5. Ориентированные графы5.1. Основные определения и понятия5.2. Графы и отношения5.3. Ориентированные и корневые деревья5.4. Ориентированные эйлеровы графы5.5. Ориентированные остовы и ориентированные эйлеровы цепи5.6. Ориентированные гамильтоновы графы5.7. Ациклические ориентированные графы5.8. Турниры5.9.
Замечания, касающиеся литературыУпражнения6. Матрицы графов6.1. Матрица инциденций6.2. Матрица разрезов6.3. Цикломатическая матрица6.4. Соотношение ортогональности6.5. Подматрицы матриц разрезов, инциденций и циклов6.6. Унимодулярные матрицы6.7. Число остовов6.8. Число остовных 2-деревьев6.9. Число ориентированных остовов в ориентированном графе6.10 Матрица смежности6.11.
Графы Коутса и Мэзона6.12. Замечания, касающиеся литературыУпражнения7. Планарность и двойственность7.1. Планарные графы7.2. Формула Эйлера7.3. Теорема Куратовского и другие характеризации планарности7.4. Двойственные графы7.5. Планарность и двойственность7.6. Замечания, касающиеся литературыУпражнения8. Связность и паросочетания8.1. Связность или вершинная связность8.2.
Реберная связность8.3. Графы с заданными степенями8.4. Теорема Менгера67717374767678788485889193959698981001001021051081101131151181201231261341341371371391411431471491491511511551561608.5. Паросочетания8.6. Паросочетания в двудольных графах8.7. Паросочетания графов общего вида8.8. Замечания, касающиеся литературыУпражнения9. Покрытия и раскраски9.1. Независимые множества и вершинные покрытия9.2. Реберные покрытия9.3. Реберная раскраска и хроматический индекс9.4. Вершинная раскраска и хроматическое число9.5. Хроматические полиномы9.6.
Проблема четырех красок9.7. Замечания, касающиеся литературыУпражнения10. Матроиды10.1. Основные определения10.2. Фундаментальные свойства10.3. Эквивалентные системы аксиом10.4. Двойственность матроидов и графоиды10.5. Ограничение, сужение и миноры матроида10.6. Представимость матроидов10.7. Бинарные матроиды10.8. Ориентируемые матроиды10.9. Матроиды и «жадный» алгоритм10.10. Замечания, касающиеся литературыУпражненияЧасть II. Теория цепей11. Графы и электрические цепи11.1. Преобразование контуров и сечений11.2. Системы контурных уравнений и уравнений сечений11.3.
Метод смешанных переменных11.4. Главное разбиение графа11.5. Уравнения состояния11.6. Свойство неусиления в резистивных цепях11.7. Замечания, касающиеся литературыУпражнения12. Резистивные n-полюсные цепи12.1. Введение12.2. Y-матрицы резистивной n-полюсной цепи ранга га12.3. Реализация (n+1)-узловых резистивных n-полюсных цепей (подходСедербаума)12.4. Реализация цикломатической матрицы и матрицы сечений12.5. Реализация (n+1)-узловых резистивных n-полюсных цепей (подходГуиллемина)16116316717117117417417918018418618919019019319319619820020420620721021221421521821822022322823023524124224324524525326326828112.6.
Замечания, касающиеся литературыУпражнения13. Функция цепи и чувствительность цепи13.1. Топологические формулы для RLC-цепей без взаимныхиндуктивностей13.2. Топологические формулы для общих линейных цепей13.3. Сопряженная цепь и вычисление чувствительности цепи13.4. Замечания, касающиеся литературыУпражненияЧасть III. Теория цепей14. Алгоритмы анализа графов14.1.
Транзитивное замыкание14.2. Транзитивная ориентация14.3. Поиск в глубину14.4. Двусвязность и сильная связность14.5. Сводимость графа программы14.6. Доминаторы в графе программы14.7. Замечания, касающиеся литературыУпражнения15. Оптимизационные алгоритмы15.1. Кратчайшие пути15.2. Деревья с минимальной длиной взвешенных путей15.3. Оптимальные деревья бинарного поиска15.4.
Максимальные паросочетания в графе15.5. Максимальные паросочетачия в двудольном графе15.6. Совершенное паросочетание, оптимальное назначение и составлениерасписаний15.7. Потоки в транспортной сети15.8. Оптимальное ветвление15.9. Замечания, касающиеся литературыУпражненияЛитератураПредметный указатель287288292292298305312313315315316322331338343351359359361361368376380389396404418422423425444Предметный указатель- декомпозиции Седербаума схемнойАксиома баз матроида 198матрицы 263- независимости матроида 193- доминаторов 354- ранга матроида 198- "жадный" 212- циклов матроида 199- Кана — Мункреса 402Алгоритм Габова 385- кратчайших путей из данной- Гильберта и Мура 166вершины ко всем остальным- Данцига 423вершинам 364- двусвязности 340- Ленгауэра и Тарьяна 354- Дейкстры 364- максимального паросочетания вграфе общего вида 385- - - - двудольном графе 394- - - - транспортной сети(помечивающий алгоритм) 410- между всеми парами вершин 367- нахождения минимального остова424- оптимального вектора длин путей374- - ветвления 421- - дерева бинарного поиска 381- - назначения 402- Пнуели, Лампла и Ивена 323- поиска в глубину внеориентированном графе 334- - - - - ориентированном графе 334- приближенный 423- реализации графов с заданнымистепенями 156—159- - матрицы сечений —цикломатической матрицы 268- - (n+ цепи, узловой, резистивной, n,полюсной, 1, 263- сводимости графа программы 348- сильной связности 343- совершенного паросочетания 399- столбце-ориентированный 319- строко-ориентированный 319- Тарьяна 348- транзитивного замыкания 3201- транзитивной ориентации 323- Уоррена 320- Уоршолла 318- Флойда 367- Форда — Фалкерсона 197- Хаффмана 374База матроида 194Базис векторного пространства 65Блок графа 26Валентность 12Вектор базисный 65- длин путей 370- инциденций 100- координаты 67- линейно независимый 65- ортогональный 67- разреза 76- циклический 76, 106n-вектор 67Вершина 11- висячая 12- внешняя 384- внутренняя 17- - n-полюсной цепи 17- звезды 255- изолированная 79- инцидентная 12- конечная 78- - маршрута 80- ориентированного маршрута 86- концевая 11, 16, 78, 80, 255- короткозамыкаемая 255- насыщенная (в паросочетании) 162- начальная 80- - в графе программы 131- - маршрута 97- - ориентированного маршрута 80- несоотносимая 334- полностью сканированная 332- помеченная 88- связанная 18- сильно связанная 81- смежная 12, 79- соответствующая усекаемой строке101- терминальная 16- центральная 49Вес ребра 59- цикла 59Ветвление оптимальное 418Ветвь дерева 33- неполюсная 247- полюсная 247Включение последовательности 141Вычисления параллельные 210Гаммоид 217Гиперплоскость матроида 216Гипотеза четырех красок 190Глубина 332Граф ассоциированныйориентированный 171- ациклический 33, 80- вершинно непересекающийся 28- - k-раскрашиваемый 184- взвешенный 135- гамильтонов 55- гамильтоново связный 61- гомеоморфный 142- двойственный 143- двудольный 23- деревьев 49- k-дольный 23- изоморфный 28- изоморфный, 1, 28- изоморфный, 2, 28- квазисильно связный 83- конденсированный 82- Koymca 127- кубический 31- лежащий в основенеориентированный 79- минимально связный 48, 82- - - ориентированный 82- Мэзона 126, 131- неориентированный 11, 100, 103- неразделимый 25- однородный 23- k-однородный 23- ориентированный 11, 78, 100, 103- - ациклический 80- - гамильтонов 93- - эйлеров 88- параллельно-последовательный 150- Петерсена 143- планарный 137- - с одной терминальной парой 150- полный 23- - двудольный 23- - k-дольный 23- - ориентированный 93- потоков Koymca 127- программы 130- произвольно гамильтонов 5&- - эйлеров 54, 55- простой 11- пустой 11- разделимый 25- реберно непересекающийся 28- - k-раскрашиваемый 180- - k-хроматический 180- к-реберно связный 155, 172- рефлексивный ориентированный 85- самодвойственный 150- самодополнительный 30- сводимый 344- связной 18, 80- - ориентированный 80- сигнальный Мэзона 131- сильно связный 81- симметрично ориентированный 85- с одной терминальной парой 150- стягиваемый 22- транзитивно ориентируемый 85, 322- тривиальный 25- укладываемый 137- k-факторизуемый 172- k-хроматический 185- эйлеров 51Графоид 203Группа абелева 62, 63Декодирование 369Дерево 33, 85- бинарного поиска 376- бинарное 87- в графе 33- венгерское 397- доминаторов 351- корневое 85- линейное 255- нормальное 236- оптимальное бинарного поиска 378- ориентированное 85- ПВГ 333- помеченное 117- расширенное бинарного поиска 376k-дерево остовное 37Дефицит 163Диакоптика 242Диаметр графа 30Длина взвешенных путей 87- ориентированного ребра 361- пути 17, 361- цикла 17Доминатор (вершины)непосредственный 351Дополнение ортогональное 67- подграфа 16- простого графа 15Дуга заходящая 79- инцидентная 79- исходящая 79- параллельная 78Задача о кёнигсбергских мостах 50- - коммивояжере 59- - свадьбах 161- составления расписаний 396Закон Кирхгофа для напряжений 218- - - токов 218Замыкание бинарного отношениятранзитивное 316- графа 61- - транзитивное 316- подмножества 216Звезда 255Изоморфность 66Индекс хроматический 180Источник напряжения 218- тока 218Клика 192Кобаза матроида 200Кодерево 33k-кодерево 37Код префиксный 88Ко-лес 38Колесо 38Коллапсирование вершины 350Комбинация линейная 65- параллельная параллельнопоследовательных графов 150- последовательная параллельнопоследовательных графов 160Компонента 18, 169- графа 80- двусвязная 341- нечетная 169- ориентированного графа 80- сильно связная 81- четная 169Конденсированный образ 82Контур 80- гамильтонов 93Конфигурация полюсная 245- - в виде звезды 245- - - - линейного дерева 245Координата вектора 67Копетля матроида 200Коранг матроида 200Корень в ориентированном графе 85- компоненты (в ПВГ) 336- ПВГ 332Коцикл 200- базисный матроида 201- матроида 200Лемма о раскраске дуг 98Лес 38Лист 15Мажорантность 56Маршрут 16, 80- замкнутый 17, 80- ориентированный 79- открытый 17Матрица базисная разрезающихмножеств 105- - цикломатическая 107, 208- бистохастическая 172- гипердоминантная 258- достижимости 121- инциденций графа 100- - ориентированного графа 100- коциклическая матроида 209- модифицированная сечений 289- - цикломатическая 290- однородно сужающаяся 260- подстановок 172- полных сопротивлений контура 225- - - холостого хода 33- полустепеней захода 121- - исхода 121- проводимостей короткогозамыкания 246- - сечений 248- разрезов графа 103- сечений 219- - базисная 220- смежности взвешенногоориентированного графа 126- - графа 123, 126- - ориентированного графа 123- с равными алгебраическимидополнениями 117степеней 117- схемная 44- узловых проводимостей 228- унимодулярная 113- усеченная инциденций 101- цикломатическая графа 106- - матроида 209- - ориентированного графа 106(О,1) матрица 166Матроид 193- бинарный 207- графический 196- двойственный 200- двудольный 217- изоморфный 196- кографический 195- неразделимый 216- несвязный 216- однородный 215- ориентируемый 216- паросочетаний 195- правильный 217- представимый 226- разделимый 216- разрезов 194- регулярный 215- связей 194, 216- связный 216- трансверсалей- Фано 216- циклический 194- эйлеров 217Место узкое 413Метка вершины 384- начальная 384- ребра 384Метод Коутса 126- Мэзона 131- Татта 121Минор матроида 206Множество базисное циклов 40, 43- внутреннее устойчивое 174- доминирующее 190- зависимое матроида 194- замкнутое матроида 216- - по отношению к бинарномуотношению 62- инциденций 76- лексикографически большее 213- - максимальное 213- независимое графа 174- - максимальное графа 174- матроида 194- оптимальное по Гейлу 213- разделяющее 152- разрешающее 40- - базисное 43, 76L-множество 271Модификация Эдмондса и Карпапомечивающего алгоритма 412Мост 31Назначение оптимальное 400Напряжение между узлом и базой222- узловое 222Нуль-граф 11Нуль-пространство 207Область планарного графа 139Образ конденсированный графа 82Обхват 30Объединение графов 21- матроидов 217Ограничение графа 204- матроида 205- по пропускной способности 03, 4Окрестность 219Операции над графами 62Определитель главный 115Оптимизация кода 374- сети 410Ориентация графа 78- ребра 78- транзитивная 109Ортогональность 67Остов графа 33- максимально удаленный 230- ориентированный 87Отец (вершины) 332Отношение бинарное 84- рефлексивное 84- симметричное 84- транзитивное 84- эквивалентности 84Отождествление (замыкание)вершиий 22Паросочетание максимальное 162- полное (в двудольном графе) 163- совершенное 169Переворачивание 28Переменная контура 222- сечения 222Пересечение графов 21Петля 11, 78- матроида 194- обратной связи 133Подграф 13, 79- венгерский 387- вершинно-порожденный 14- главный 233- критический 418- максимальный 14- минимальный 14- остовный 13- порожденный 14, 79- равенств 188- реберно-порожденный 14- собственный 13k-подграф 20Поддерево 33- левое 376- правое 376Подмножество зависимое 194- максимальное 14, 199- минимальное 14Подпространство ортогональное 67- разрезов 70- циклов 69Поиск в глубину в графе 332- - - - ориентированном графе 335- - ширину 360Покрытие вершинное 174- минимальное 175, 179- реберное 179Поле Галуа 63, 64Полином хроматический 186Полудоминатор 352Полустепень захода 79- исхода 79Полюс концевой 255- подобно ориентированный 255- противоположно ориентированный255Помечивание обратное 410- прямое 410Порядок редукции 350Последовательность выводимая 231- графическая 56- де Брёйна 88- остаточная 157- очков 97- Пруфера 147- степеней 56- чередующаяся (по отношению кнезависимому множеству) 176Поток максимальный 406Потомок (вершины) собственный 334Предок (вершины) собственный 334Преобразование контурное 221- полюсное 222- сечения 222- узловое 222Проблема оптимизации кода 372- NP-полная 359- расширения 383- NP-сложная 359- четырех красок 189Представление матроида стандартное206Проекция стереографическая 138Произведение полныхсопротивлений 293- проводимостей 293- скалярное векторов 67Пространство векторное 64- нуль матрицы 207Проход (через вершину в ПВГ) 332Псевдовершина 420Путь 17, 180- добавляющий 168- f-дополняющий 408- кратчайший 361- - по отношению к паросочетанию390- максимальный 282- f-ненасыщенный 195- ориентированный 80- - гамильтонов 55- M-чередующийся 167Разбиение главное 233- двудольное 23, 176Разделитель 42Размерность векторногопространства 65Разметка допустимая вершинная 399Разрез ориентированный 42, 98Ранг 82- графа 39- матроида 194- ориентированного графа 82Ранжирование 97Раскраска 202- k-вершинная 182- - правильная 184- ориентируемого матроида 211- k-реберная 180- - оптимальная 180- - правильная 180Расстояние между вершинами 30- - остовами 230Расщепление вершины 28- точки сочленения 28Реализация (n+ полюсной,резисторной, цепи, 1, 263Ребро 11- висячее 12- критическое 418- f-насыщенное 408- независимое 162- f-ненасыщенное 408- нециклическое 17- f-нулевое 408- обратное 332- - по отношению кориентированному пути 407- пересекающее 121- подходящее 418- f-положительное 408- полюсное 245- помеченное 329- последовательное 141- прямое 332- - по отношению кориентированному пути 407- - - - - ПВГ 332- рассмотренное (в ПВГ) 332- светлое 167- смежное 12, 79- темное 167- циклическое 17Редукция транзитивная 359Свойство ассоциативности 62- коммутативности 62- неусиления 241- схемности 257Связность вершинная 151- реберная 155Сеть транспортная 404Сечение ориентированное 241- - полюсной цепи 241Система различных представителей165- уравнений контурная 224- - сечений 226- - со смешанными переменными 230Скаляр 65Слияние последовательности 141Слово кодовое 372Соединение параллельное 290- псевдопоследовательное 290- факторное, ориентированного,графа, 1, 128Сортировка топологическая 95Составление расписания 403Список смежности 316Способность пропускная разреза 406- - ребра 405Степени свободы топологические 235Степень вершины 79- области 141Сток 404Стягивание ребра 22Сужение матроида 204Сумма кольцевая графов 21- прямая подпространств 65- характеристическая 372Теорема Бержа о чередующейся цепи168- Бине—Коши 116- Брукса 185- Визинга 183- добавления 196- Кёнига 165- Кёнига — Эгервари 166- Куратовского 141- Кэли 117- Менгера 160- Мендельсона и Далмеджа 169- о максимальном потоке иминимальном разрезе 409- - пяти красках 189- Татта о совершенныхпаросочетаниях 170- Теллежена 222- Холла 164- четырех красок 190- Эдмондса о k-реберной связности159Теория экстремальных графов 190Толщина 149Точка сочленения 25Трансверсаль частичная 165, 216Транспозиция цепи 312Треугольник 31Турнир 96Удаление вершины 22- ребра 22Узел 219Укладка планарная 137Улучшение реберной раскраски 183Уравнения состояния 235- узловые 228Уязвимость 181фактор, ориентированного, графа, 1,124k-фактор 172Формула коэффициента усиленияКаутса 130- - - Мэзона 133- Эйлера 139Функция Аккермана 136- коранга матронда 200- ранга матроида 194Хорда 33- неполюсная 249- полюсная 249«Цветок» 168Цепь 17, 80- вывода 327- замкнутая 17- - ориентированная 80- ориентированная 80- - эйлерова 51, 88- открытая 17, 80- - ориентированная 80- - - эйлерова 51, 88- n-полюсная 246- - нагруженная 246- чередующаяся (по отношению кпаросочетанию) 167Цикл 17, 80- базисный 40- - матроида 410- гамильтонов 55- матроида 410- ориентированный 80Число вершинного покрытия 175- внутренней устойчивости 174- независимости 174- паросочетаний 162- реберного покрытия 179- реберно-хроматическое 180- скрещиваний 149- хроматическое 185- цикломатическое графа 82, 89Эквивалентности классы 81Элементы матроида 63, 193Ячейка 140.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
