Н. Кристофидес - Теория графов. Алгоритмический подход (1978) (1162186)
Текст из файла
Н.КристофидесТЕОРИЯ ГРАФОВ. АЛГОРИТМИЧЕСКИЙ ПОДХОДМ.: Мир, 1978, 432 стр.Предисловие редактора переводаПредисловиеГлава 1. Введение1. Графы. Определение2. Пути и маршруты3. Петли, ориентированные циклы и циклы4. Степени вершины5. Подграфы6. Типы графов7. Сильно связные графы и компоненты графа8. Матричные представления9.
Задачи10. Список литературыГлава 2. Достижимость и связность1. Введение2. Матрица достижимостей и контрадостижимостей3. Нахождение сильных компонент4. Базы5. Задачи, связанные с ограниченной достижимостью6. Задачи7. Список литературыГлава 3. Независимые и доминирующие множества. Задача опокрывающих множествах1. Введение2. Независимые множества3.
Доминирующие множества4. Задача о наименьшем покрытии5. Приложения задачи о покрытии6. Задачи7. Список литературыГлава 4. Раскраски1. Введение2. Некоторые теоремы и оценки, относящиеся к хроматическим числам3. Точные алгоритмы раскраски4. Приближенные алгоритмы раскрашивания5. Обобщения и приложения6. Задачи7. Список литературыГлава 5.
Размещение центров1. Введение57111113161818192325272829292933374041424343445053636871757576799092949798982. Разделения3. Центр и радиус4. Абсолютный центр5. Алгоритмы нахождения абсолютных центров6. Кратные центры (р-центры)7. Абсолютные р-центры8. Алгоритм нахождения абсолютных р-центров9. Задачи10. Список литературыГлава 6. Размещение медиан в графе1. Введение2. Медиана графа3. Кратные медианы (р-медианы) графа4. Обобщенная р-медиана графа5. Методы решения задачи о р-медиане6. Задачи7. Список литературыГлава 7. Деревья1. Введение2.
Построение всех остовных деревьев графа3. Кратчайший остов (SST) графа4. Задача Штейнера5. Задачи6. Список литературыГлава 8. Кратчайшие пути1. Введение2. Кратчайший путь между двумя заданными вершинами s и t3. Кратчайшие пути между всеми парами вершин4. Обнаружение циклов отрицательного веса5. Нахождение кратчайших путей между двумя заданными вершинами6.
Кратчайший путь между двумя заданными вершинами вориентированном ациклическом графе7. Задачи, близкие к задаче о кратчайшем пути8. Задачи9. Список литературыГлава 9. Циклы, разрезы и задача Эйлера1. Введение2. Цикломатическое число и фундаментальные циклы3. Разрезы4. Матрицы циклов и разрезов5. Эйлеровы циклы и задача китайского почтальона6. Задачи7. Список литературыГлава 10. Гамильтоновы циклы, цепи и задача коммивояжера991011021041111121141231261271271271291321331411431451451481581661681721751751771891911931972012112142172172172212252272392412421. Введение242ЧАСТЬ I2452.
Гамильтоновы циклы в графе2453. Сравнение методов поиска гамильтоновых циклов2594. Простая задача планирования262ЧАСТЬ II2655. Задача коммивояжера2656. Задача коммивояжера и задача о кратчайшем остове2687. Задача коммивояжера и задача о назначениях2848. Задачи3049. Список литературы30710. Приложение308Глава 11. Потоки в сетях3101. Введение3102. Основная задача о максимальном потоке (от s к t)3113. Простые варианты задачи о максимальном потоке (от s к t)3254. Максимальный поток между каждой парой вершин3295. Поток минимальной стоимости от s к t3396.
Потоки в графах с выигрышами3537. Задачи3648. Список литературы367Глава 12. Паросочетания, транспортная задача и задача о назначениях 3681. Введение3682. Наибольшие паросочетания3713. Максимальные паросочетания3894. Задача о назначениях4045. Общая задача построения остовного подграфа с предписанными411степенями6. Задача о покрытии4167. Задачи4178. Список литературы420Приложение 1. Методы поиска, использующие дерево решений4221. Принцип поиска, использующий дерево решений4222. Некоторые примеры ветвления4243.
Типы поиска, использующего дерево решений4244. Применение границ4265. Функции ветвления426Предметный указатель427Предметный указатель- - для задачи о назначениях 405—Активный цикл см. Маршрут407замкнутый активный 358, 364- - - транспортной задачи 413Алгоритм "беспорядка" ["out-of-kilt"]339- венгерский 405- двойственный решения задачи опотоке минимальной стоимости351—353- Дейкстры решения задачи ократчайшем пути между двумязаданными вершинами s и t снеотрицательной матрицейвесов 174—183- Краскала построения кратчайшегоостова графа 160—162- направленного древовидногопоиска для задачи о р-медиане138- - поиска для задачи о р-медиане139—144- нахождения абсолютного в-центра114, 115- основной для задачи о потокеминимальной стоимости 339—342- поиска, использующего дереворешений для задачи окоммивояжере 285—295- приближенный для задачи о рмедиане 139—141- Прима построения кратчайшегоостова графа 162—163- расстановки пометок в задаче омаксимальном потоке 314—315- решения задачи китайскогопочтальона 331, 332- - - о кратчайших путях между двумязаданными вершинами 195, 196- - - - кратчайшем пути между двумязаданными вершинами s и t собщей матрицей весов 183—189- - - - назначения 405- - - - - матричная форма 406, 407- - - - наибольшем паросочетании(ЗНПС) 381—, 383- - - - наименьшем покрытии (ЗНП),использующий дерево поиска55- - - - покрытии наименьшеймощности (ЗНПМ) 416- - - - - разбиении (ЗНР) 55- - - - потоке между каждой паройвершин 331—334- - - - раскраске и использованиемдерева поиска 88—90- Робертса и Флореса порождениягамильтонова цикла 249—253- Флери построения эйлерова цикла230- Флойда решения задачи ократчайшем пути между всемипарами вершин 189—190- Хакими нахождения абсолютногоцентра 104, 105- - модифицированный 107—110- штрафования вершин для задачикоммивояжера 285—295Алгоритмы приближенные решениязадача о раскраске 90—91Антибаза [contrabasis] 38База [basis] 37—40- сильная [power] 39Булевское (логическое) выражение64Вершина [vertex] 11- внешняя [outer] 374—378- внутренняя [inner] 374—375- конечная [final] 11- концевая [terminal] 11- начальная [initial] 11Вершина несущественная,избыточная [inessential] 33- пропускная способность 326- существенная, неотъемлемая[essential] 33- экспонированная [exposed] 371Внешне устойчивое множество см.Доминирующее множествовершин 40Внутреннее произведение вершин245Выбор места для склада 129- проекта 45Гипотеза четырех красок 79Граф [graph] 11- антисимметрпческий 20- взвешенный 15- двудольный [bipartite] 21, 405, 412- - неориентированный 21- - ориентированный 21- дополнение 46- инкрементальный [incremental] 321,339, 350, 352, 360- Куратовского 23- Муна- Мозера 70- неориентированный [nondirected] 11- - двойник 11- непланарный [nonplanar] 23- несвязный [disconnected] 23- односторонне связный илиодносторонний [unilateral] 23- ориентированный [directed] 11- остовов [tree graph] 157- планарный [planar] 22, 79- полный [complete] 19- - антисимметрический 20- - симметрический 20- реберный [line] 237- редуцированный [reduced] 254- r-хроматический [r-chromatic] 75- сильно связный или сильный[strong] 23- симметрический [simmetric] 20- слабо связный или слабый [weak] 23- со взвешенными вершинами [vertexweighted] 15- - - дугами [arc-weighted] 15- транзитивный [transitive] 33- унитарный [unitary] 323Густота cм.
Кликовое число 43Дерево [tree] 145—172- альтернирующее 374- аугментальное [augmenting] 375- венгерское 380—382- ориентированное [directed] 145—147, 240- остовное [spanning tree] (см. Остов)145—224- - длиннейшее 163- - процедура порождения 149—157- - расщепление [division] 153- решения для поиска [search tree]422—427- - ветвление 422, 424- - границы 426- - для поиска по глубине 425- - - - - ширине 425- - висячая вершина 423- - разбиение 424- - функции ветвления 426—427- сращивание [merging] 153- цветущее [blossomed] 376- Штейнера наикратчайшее 167—169- элементарное преобразование 149Диаметр графа 11, 125Доминирующее множество вершин40- - - минимальное [minimal] 50- - - наименьшее [minimum] 50Достижимое множество 29Достижимость [reachability] 23Дуга [arc] 11- вес [weight] (Длина [length],стоимость или цена [cost] 15,201- надежность [reliability] 201- нижняя граница потока через 310- обратная 313, 356- поток, входящий в 354- - выходящий из 354- пропускная способность 202, 282,313- прямая 313, 356Задача государственногорайонирования [politicaldistricting] 65- об остовном графе спредписанными степенями[degree-constrained partial graphproblem] 368, 411—414- китайского почтальона 231—237- нахождения ДОПУСТИМОГОпотока минимальной стоимости310- о доставке молока или почты[delivery of post] 231- - Кёнигсбергских мостах 228- - коммивояжере 242—309- - - минимаксная 244- - - минисуммная 244- - - нижняя граница из задачи ократчайшем остове 266, 279- - - - - - - - назначениях 265, 297—303- - кратчайших путях между двумязаданными вершинами 195- - кратчайшем пути междузаданными вершинами s и t175—189- - - - - - - - - - с неотрицательнойматрицей весов 177—183- - ферзях на шахматной доске 70- - максимальном паросочетании(ЗМП) 368—371- - - потоке (от s к t) 310—325- - минимальном покрытии (ЗНПО)369- - многопродуктовом потоке[multicommodity] 311, 325- - назначениях (ЗН) [assignmentproblem] 284, 404—411- - наибольшем паросочетании(ЗНПС) 370, 375- - наименьшем покрытии 43, 53—68- - - - вычисление нижней границы 60- - - - приложения 63—68- - - - упрощение 54- - покрытии наименьшей мощности(ЗПНМ) [minimum cardinalitycovering problem] 370, 416- - потоке минимальной стоимости отs к t 310, 339- - потоках с выигрышами 311, 353—364- - раскраске 375- - - решение методом динамическогопрограммирования 80—84- - - - - программирования, 1, 84—46- - - сведение к ЗНП 86—88- - распределении ресурсов 94- размещения минимаксная 98, 127- - минисуммная 98, 127- сетевого планирования [networkplanning] 65- синхронизации линии сборки[assembly line balancing] 65- теории расписаний 94- транспортная (ТЗ) 371, 412—416Задача Штейнера 166—169- - евклидова 167- - линейная 169- - на графах 166, 167Информационный поиск [retrievalinformation] 63Исследование структурыорганизации 39Источник [source] 310Клика графа [clique] 46Кликовое число [clique number] 43Компонента графа односторонняя 24- - сильная 24, 33—36- - слабая 24Компрессия [compression] матрицы297Константа «проникновения»[penetration] 114Контрадостижимое множество[reaching set] 30Контур см.
Орцепь замкнутаяпростая 17- гамильтонов 17, 157, 237, 242—309- - алгебраический метод нахождения245—249- независимый [independent] 218Корень [root] дерева 374- ориентированного дерева 146- - - замена 193Коцикломатпческое число 218Кратные центры [multiple centres] 111Кратчайшее дерево Штейнера 166—167Кратчайший остов графа [shortestspanning tree] 158—161Критический путь [critical path] 197—200\lambda-оптимальность 140—141Максимальный полный подграф см.Клика 46Маршрут [chain] 4- аугментальный [augmenting] 356- - инкрементальная пропускнаяспособность [incrementalcapacity] 356- выигрыш 356- замкнутый [cycle] 17- - активный [active cycle] 358—364Маршруты полетов самолетов 64Матрица достижимостей [reachabilitymatrix] 29, 30, 31- инциденций [incidence matrix] 26,148, 155, 170, 226, 239, 379- контрядостижимостей [reaching] 30,31- ограниченных достижимостей 33- редуцированная 406- смежности [adjacency matrix] 25- - модифицированная 245Медиана [median] 98, 127—143- абсолютная 130- внешняя 128- внешне-внутренняя 129- внутренняя 128- кратная см.
р-медиана 129Метод критического пути (МКП)[critical path method] 197Наименьшее доминирующеемножество ребер см.Наименьшее покрытие 66, 67Независимое множество вершин[independent vertex set] 44- - - максимальное [maximal] 44—48,80, 86, 87- - - наибольшее [maximum] 45, 65- - ребер [independent link set] 66- - - наибольшее 66Область 114Обход лабиринта 240Орцепь см.
Цепь ориентированная 14- замкнутая 17- - простая [elementary circuit] 17Остов [spanning tree] 145, 224- число 148Отображение [mapping] 11Паросочетание [matching] 66, 368—420- максимальное [maximal] 389- наибольшее [maximum] 66, 368- совершенное [perfect] 389Передаточное число [transmissionnumber] 127—128- - внешнее [out] 128- - внутреннее [in] 128ПЕРТ 197Петля [loop] ? 6Плотность см. Кликовое число 43Подграф [partial subgraph] 19- максимальный [maximal subgraph]23, 24- остовный [partial graph] 18- порожденный [subgraph] 18Покрытие [covering] 66, 67, 369- минимальное [minimal] 369- наименьшее [minimum] 66, 67Полустепень захода [indegree] 18- исхода [outdegree] 18Пометка предшествования 153- - изменение 153Поток [flow] 310- аугментальная цепь [flowaugmenting chain] 313- в графах с выигрышами 356- - - - - в вершинах 364- - - - многими источниками истоками 325- - - - пропускными способностямидуг и вершин 326- допустимый [feasible flow] 310,353—358- - максимальный 354- - оптимально-максимальный 354- - оптимальный 354- конформальный [conformal] 325Потоковая эквивалентность 330Проверка электрических,телефонных илижелезнодорожных линий 231Псевдовершина [pseudovertex] 375Пустое множество 11Путь [path] 13- вес, длина или стоимость [length] 15- длина или мощность [cardinality] 16- замкнутый [path] 16- - элементарный 17- кратчайший 173, 189—193- надежность 201, 202- ответвление [deviation] 195- пропускная способность 202- самый длинный 198- с наибольшей приведеннойпропускной способностью206—211р-кратный внешний центр [poutcentre] 112- внутренний центр [p-incentre] 112р-медиана 129- абсолютная 130- внешняя 130- внутренняя 130- обобщенная 132, 139р-центр (кратный центр) 41, 111, 112- абсолютный 112, 113- - нахождение 113—123Радиус 101- абсолютный внешний 103- - внутренний 101- внешне-внутренний 102- внешний 101Радиус внутренний 101Разделение [separation] 99—101- внешнее [out] 100- внутреннее [in] 100Размещение [location] 98- аварийных служб и пунктовобслуживания 101—102, 106,107- нескольким центров обслуживания112- центров 51, 52, 98—125Разрез [cut-set] 221—225, 312, 313- величина 312- для ориентированного графа 223,224- правильный [proper] 222, 223- фундаментальный 224, 225- - матрица 225, 226, 239Раскраска [colouring] 75—96- оптимальная независимая 80, 84Ребро [link] 11- искусственное 232r-подграф 80- максимальный 80—84Смежные дуги 14- вершины 14Соответствие 11- обратное 13Специальный остовный подграф[equally partial] 391Степень вершины [degree] 18- - k-шаговая 91Строгое пересечение (SI) [strictintersection] 117—118Сток [sink] 310(s-t)-разрез 202, 206Теорема Кенига 418- - и Холла 417- о максимальном потоке иминимальном разрезе 312, 313- - пяти красках 79Точка Штейнерa 168, 169Транзитивное замыкание графа 33Турнир [tournament] 21Хроматическое число [chromaticnumber] 75- - верхняя оценка 78- - нижняя оценка 77, 78Цветок [blossom] 375—379- крайний [outermost] 375- срезание [shrinking] 375—379Центр графа 98, 103Цепь альтернирующая [alternatingpath] 371- аугментальная [augmenting path]372, 372- ориентированная (орцепь) [simplepath] 14- простая [elementary path] 14- эйлерова см.
Эйлеров цикл 227, 240Цикл гамильтонов 17, 242—309- ориентированный (орцикл) 17- - матрица 225, 239- - мультицепной метод нахождения253, 259- - сравнение методов поиска 259—262- фундаментальный 220, 221- эйлеров 227—240Цикломатическое число [cyclomaticnumber] 217, 218Число Бетти см. Цикломатическоечисло 217, 218- внешнего разделения 100- внутреннего разделения 100- доминирования 43- независимости [independencenumber] 43, 44.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
