Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задачи обработки графов
|
|
Вооружившись базовыми инструментальными средствами, которые были разработаны в настоящей главе, мы рассмотрим в главах 18—22 самые разнообразные алгоритмы решения задач обработки графов. Эти алгоритмы относятся к категории фундаментальных и могут оказаться полезными во многих приложениях, но, тем не менее, их можно рассматривать как введение в область алгоритмов на графах. Разработано множество интересных и полезных алгоритмов, которые выходят за рамки данной книги, исследовано множество интереснейших задач, для решения которых все еще не удалось найти хороших алгоритмов.
Как и в случае любой другой предметной области, первая серьезная проблема, с которой нам приходится сталкиваться при решении новой задачи обработки графов, касается определения, насколько трудной для решения является эта новая задача. Применительно к обработке графов, это решение может оказаться намного более трудным, чем мы можем это себе представить, даже для задач, решение которых, на первый взгляд, не представляет трудностей. Более того, наша интуиция часто оказывается бессильной и не может отличить легкой задачи от трудной или от нерешенной на данный момент. В этом разделе мы кратко опишем классические задачи и проверим, что мы о них знаем.
Имея перед собой новую задачу обработки графов, с какого вида трудностями нам придется столкнуться при разработке реализации ее решения? Неприглядная правда состоит в том, что не существует подходящего метода, чтобы ответить на этот вопрос применительно к любой задаче, с которыми нам приходится сталкиваться, в то же время мы способны дать общее описание сложности решения различных классических задач обработки графов. В этом смысле мы разобьем эти задачи примерно по следующим категориям сложности их решения:
■ Легкие
■ Поддаются решению
■ Трудно решаемые
■ Неизвестно, существует ли решение.
Такая классификация предназначена для того, чтобы получать информацию о каждой такой категории и чтобы иметь представление о текущем уровне знаний в области алгоритмов на графах.
Как показывает эта терминология, основная причина, побудившая ввести подобную классификацию задач, заключается в том, что существует множество задач на графах, подобных задаче поиска гамильтонова цикла, при этом никто не знает, можно ли найти их эффективное решение. В конечном итоге мы узнаем (в части 8), как наполнить это заявление содержанием в точном техническом смысле; однако на данном этапе мы, по меньшей мере, получаем предостережение о том, с какими серьезными препятствиями нам придется столкнуться во время написания программ, решающих эти задачи.
Часть 5. Алгоритмы на графах
Мы отложим подробное описание многих задач обработки графов до дальнейших разделов данной книги. Здесь мы ограничимся краткими и понятными формулировками с тем, чтобы ознакомить читателя с проблемой классификации задач обработки графов по трудности их решения.
Легкая задача обработки графа — это задача, которая может быть решена путем применения некоторых видов компактных, элегантных и эффективных программ, к которым мы уже успели привыкнуть на протяжении глав 1—4. Достаточно часто для выполнения этих программ требуется в худшем случае линейные затраты времени, либо зависимость этих затрат ограничивается полиномами низких степеней по числу вершин или числу ребер. В общем случае, как это имело место во многих других предметных областях, мы можем установить, что проблема относится к числу легких, путем разработки решения " в лоб", которое, будучи слишком медленным для графов крупных размеров, допустимо для графов небольших, а иногда и средних размеров. Затем, зная, что задача имеет легкое решение, мы предпринимаем попытки найти эффективные решения, которыми мы смогли воспользоваться на практике, и стремимся выбрать из них наилучшее. Задачу поиска эйлерова цикла, которую мы рассматривали в разделе 17.7, может служить наиболее ярким примером легких задач, в главах 18—22 мы рассмотрим множество других таких задач, и в первую очередь следующие.
Простая связность. Обладает ли заданный граф свойством связности? Иначе говоря, существуют ли пути, соединяющие каждую пару его вершин? Существует ли цикл в графе или он представляет собой лес? Содержатся ли в цикле две заданные вершины? Впервые мы столкнулись с необходимостью найти ответ на эти основные вопросы, касающиеся обработки графов, в главе 1. Мы будем искать решения указанных задач в главе 18. Некоторые из них легко решаются при линейных затратах времени; чтобы решить другие задачи за линейное время, требуется разработка изощренных алгоритмов, которые, в свою очередь, требуют серьезных исследований.
Сильная связность в орграфах. Существует ли ориентированная цепь, соединяющая каждую пару вершин орграфа? Соединены ли две заданные вершины графа ориентированной цепью в обоих направлениях (входит ли они в какой-либо направленный цикл)? Реализация эффективного решения этих задач намного сложнее, чем соответствующая задача простой связности в неориентированных графах, на их изучение отводится большая часть главы 19. Несмофя на все хитроумные приемы, применяемые при их решения, мы относим эти проблемы к категории легких, поскольку мы можем написать компактную эффективную и полезную реализацию.
Транзитивное замыкание. Какое множество вершин может быть получено, если следовать по направлению ориентированных графов из каждой вершины орграфа? Эта задача имеет прямое отношение к задаче сильной связности и другим фундаментальным вычислительным задачам. В главе 19 мы будем изучать классические решения, которые сводятся всего лишь к нескольким строкам программного кода.
Минимальное остовное дерево. Во взвешенном графе необходимо найти множество ребер с минимальным весом, которые соединяет все вершины. Это одна из старейших и хорошо изученных задач обработки графов; глава 20 целиком отводится для изучения различных классических алгоритмов ее решения. Исследователи продолжают поиски более быстродействующих алгоритмов решения этой задачи.
Глава 17. Свойства и типы графов
|
| Поиск кратчайших путей из одного истока.Каким будет кратчайший путь, соединяющий заданную вершину v с каждой другой вершиной во взвешенном орграфе (сети)? Вся глава 21 посвящена изучению этой задачи, которая исключительно важна для многочисленных применений. Эту задачу никоим образом нельзя отнести к категории легко решаемых, если веса могут принимать отрицательные значения. Задача обработки графов, принадлежащая к категории поддающейся решению, — это задача, алгоритм решения которой известен, а требования к которой в смысле затрат времени и пространства памяти на ее реализацию ограничиваются полиномиальной функцией от размеров графа (V + Е). Все легкие задачи поддаются решению, однако мы проводим различия между ними, поскольку для многих задач, поддающихся решению, характерно то, что разработка эффективных программ их решения, применение которых в оправдано в практических целях, представляет собой исключительно трудную, если не невозможную, проблему. Решения могут оказаться слишком сложным, чтобы приводить их в данной книге, поскольку их реализации могут содержать сотни и даже тысячи строк программного кода. Далее следуют два примера наиболее актуальных задач этого класса. Планарность.Можно ли начертить заданный граф таким образом, чтобы никакие линии, представляющие ребра, не пересекались? Мы свободны поместить вершины в любое место, так что мы можем решить эту проблему для множества одних графов, но ее нельзя решить для множества других графов. Замечательный классический результат, известный как теорема Куратовского (Kuratovski's theorem), позволяет легко проверить, является ли граф планарным (плоским). Эта теорема утверждает: графы, которые не могут |
быть представлены на чертеже без пересечения ребер, суть графы, содержащие некоторый подграф, который после удаления из него вершин степени 2, становится изоморфным одному из графов, изображенных на рис. 17.24. Бесхитростная реализация этого теста, даже если не принимать во внимание вершин степени 2, работает недопустимо медленно на крупных графах (см. упражнение 17.110), но в 1974 г. Роберту Тарьяну (R.Tarjan) удалось получить оригинальный (но в то же время довольно замысловатый) алгоритм, способный решать эту задачу за линейное время с использованием схемы поиска в глубину, которая является расширением схем, рассматриваемых в главе 18. Алгоритм Тарьяна не обязательно позволяет получить чертеж, пригодный для применения в практических целях, он просто констатирует тот факт, что такой чертеж существует. Как уже было отмечено в разделе 17.1, построение наглядного чертежа графа для приложений, в котором вершины графа не обязательно соответствуют реалиям внешнего мира, превращается в довольно сложную исследовательскую задачу.
Сочетания. Каким является наибольшее подмножество ребер графа, обладающего тем свойством, что никакие два ребра из подмножества не связаны с одной и той же
РИСУНОК 17.24. ЗАПРЕЩЕННЫЕ ПОДГРАФЫ ПЛАНАРНЫХ ГРАФОВ
Ни один из изображенных здесь графов нельзя начертить на плоскости без того, чтобы его ребра не пересекались, это утверждение справедливо для всех графов, которые содержат любой из этих графов в качестве подграфа (после того, как мы удалим вершины степени 2); однако все остальные графы допускают подобное отображение на плоскости.