Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19. Орграфы и ориентированные ациклические графы. 157
|
|
Глоссарий и правила игры................................................................................................ 160
Анатомия поиска DFS в орграфах.................................................................................. 169
Достижимость и транзитивное замыкание................................................................. 178
Отношения эквивалентности и частичные порядки.............................................. 190
Графы DAG.............................................................................................................................. 193
Топологическая сортировка.............................................................................................. 199
Достижимость в графе DAG............................................................................................... 209
Сильные компоненты в орграфах.................................................................................. 212
Еще раз о транзитивном замыкании............................................................................. 223
Перспективы........................................................................................................................ 227
Часть 5. Алгоритмы на графах
Глава 20. Минимальные остовные деревья............................... 231
Представления......................................................................................................................... 234
Принципы, положенные в основу алгоритмов построения дерева MST.......... 243
Алгоритм Прима и поиск по приоритету...................................................................... 250
Алгоритм Крускала................................................................................................................ 260
Алгоритм Борувки................................................................................................................. 266
Сравнения и усовершенствования.................................................................................. 270
Эвклидово дерево MST......................................................................................................... 276
Глава 21. Кратчайшие пути........................................................ 279
Основные принципы............................................................................................................. 287
Алгоритм Дейкстры............................................................................................................... 294
Кратчайшие пути между всеми парами......................................................................... 304
Кратчайшие пути в ациклических сетях....................................................................... 311
Эвклидовы сети............................................................................................................................ 319
Сведение..................................................................................................................................... 325
Отрицательные веса.................................................................................................................... 340
Перспективы............................................................................................................................. 357
Глава 22. Потоки в сетях........................................................... 359
Транспортные сети................................................................................................................. 366
Алгоритм поиска максимального потока методом аугментального пути...... 376
22.3. Алгоритмы определения максимальных потоков методом выталкивания
превосходящего потока........................................................................................................ 402
Сведение к максимальному потоку................................................................................ 417
Потоки минимальной стоимости..................................................................................... 435
Сетевой симплексный алгоритм....................................................................................... 444
Сведение к задаче о потоке минимальной стоимости.............................................. 463
Перспективы............................................................................................................................. 473
Ссылки, использованные в пятой части.................................... 477
Предметный указатель............................................................. 479
Предисловие
Графы и алгоритмы на графах активно проникают во все современные компьютерные приложения. В этой книге описываются широко известные методы решения задач обработки графов, которые возникают на практике. Ее основная цель заключается в том, чтобы сделать эти методы и базовые принципы, составляющие их основу, доступными для все большего числа людей, которые в них нуждаются. Предлагаемый материал книги представлен таких образом, что сначала излагаются начальные сведения, начиная с базовой информации и основных понятий, с постепенным переходом к анализу классических методов, и завершается изучением современных технологий, которые все еще находятся на стадии разработки. Тщательно подобранные примеры, подробные рисунки и завершенные программные реализации сопровождаются подробным описанием алгоритмов и приложений.