Сведение

Вернемся к задаче о кратчайших путях, в частности, к общему случаю, когда допус­каются отрицательные веса (тема раздела 21.7), — представим общую математическую модель, которую можно использовать для решения широкого круга различных задач, ка­жущихся не имеющими отношения к обработке графов. Эта модель является первой сре­ди ряда таких общих моделей, с которыми предстоит встретиться чуть ниже. Поскольку мы подходим к более трудным задачам и все более общим моделям, одна из сложностей, с которой доведется столкнуться, связана с точной характеристикой взаимосвязей меж­ду различными задачами. Для каждой новой задачи мы задаемся вопросом, можем ли мы решить ее просто путем сведения к задаче с известным методом решения. Если у нас имеются ограничения на задачу, способны ли мы решить ее более простым путем? Что­бы ответить на вопросы подобного рода, в этом разделе мы ненадолго отклонимся от темы, дабы обсудить термины, используемые для описания таких видов взаимосвязи между задачами.

Определение 21.3. Мы говорим, что некоторая задача А сводится к (reduces to) дру­гой задаче В, если есть возможность использовать алгоритм решения задачи В для раз­работки алгоритма, дающего решение задачи А, за суммарное время, которое в худ­шем случае не более чем в константное число раз превышает худшее время выполнения алгоритма решения задачи В. Мы говорим, что две задачи эквивалентны, если они сводятся одна к другой.

Отложим до части 8 строгое определение того, что означают слова " использовать" один алгоритм для " разработки" другого. Для большинства приложений мы довольствуемся сле­дующим простым приемом. Мы показываем, что А сводится к В, демонстрируя возмож­ность решения любого экземпляра задачи А за три шага:

■ Преобразование ее к задаче В.
■ Решение полученной задачи В.

■ Преобразование решения задачи В в решение задачи А.

Поскольку мы можем выполнить преобразования (и решить задачу В) максимально эффективно, не менее эффективно можно решить также и задачу А. Дабы продемонст­рировать такую методику доказательства, рассмотрим два примера.

Свойство 21.12. Задача транзитивного замыкания сводится к задаче поиска кратчайших путей для всех пар с неотрицательными весами.

Доказательство: Мы уже отмечали прямую связь между алгоритмами Уоршалла и Флой­да. Другой способ исследования их взаимоотношений в настоящем контексте заклю-

Часть 5. Алгоритмы на графах

чается в представлении, что требуется вычислить транзитивное замыкание орграфов с использованием библиотечной функции поиска всех кратчайших путей в сетях. Для этого мы добавляем петли, если их нет в орграфе, а затем строим сеть непосредственно из матрицы смежности орграфа с произвольным весом (скажем, 0.1), соответствую­щим каждой 1 и сигнальным весом, соответствующим каждому 0. Затем мы обраща­емся к функции поиска кратчайших путей для всех пар. Далее, из вычисленной фун­кцией матрицы кратчайших путей для всех пар можно легко определить транзитивное замыкание: для любых двух заданных вершин и и v путь в орграфе из и в v существу­ет тогда и только тогда, когда длина пути в сети из и в v будет ненулевой (см. рис. 21.21). ■

Это свойство является формальным утверждением о том, что задача транзитивного за­мыкания не является более трудной, чем задача кратчайших путей для всех пар. Ввиду су­ществования алгоритмов транзитивного замыкания, которые являются даже более быст­рыми, чем известные нам алгоритмы для задач поиска кратчайших путей для всех пар, это утверждение не должно вызывать удивления. Сведение представляет интерес тогда, ког­да оно используется для установки взаимосвязей между задачами, решение которых нам не известно, или между такими задачами и задачами, которые мы можем решить.

Свойство 21.13. В сетях без ограничений на веса ребер задачи поиска наиболее длинного пути и кратчайшего пути (для единственного источника или для всех пар) эквивалентны.

Доказательство: Для заданной задачи поиска кратчайшего пути проинвертируем все веса. Наиболее длинный путь (путь с наибольшим весом) в модифицированной сети есть кратчайший путь в исходной сети. Тот же самый аргумент показывает, что зада­ча кратчайшего пути сводится к задаче наиболее длинного пути. ■

Это доказательство тривиально, но данное свойство также показывает, что осторож­ность при объявлении и доказательстве сведений оправдана, поскольку легко посчитать сведение само собой разумеющимся и таким образом ввести себя в заблуждение. Напри­мер, утверждение о том, что задачи о наиболее длинном и кратчайшем путях эквивален­тны в сетях с неотрицательными весами, категорически не соответствует действительно; ста.

РИСУНОК 21.21. СВЕДШИЕ ТРАНЗИТИВНОГО ЗАМЫКАНИЯ

Для заданного орграфа (слева) мы можем преобразовать матрицу смежности (содержащую петли) в матрицу смежности, представляющую сеть, путем присваивания произвольного веса каждому ребру (матрица слева). Как обычно, пустые элементы матрицы представляют сигнальные значения, указывающие на отсутствие ребра. Для заданной матрицы длин кратчайших путей для всех пар этой сети (матрица в центре) транзитивное замыкание орграфа (матрица справа) суть просто матрица, образованная подстановкой 0 для каждого сигнального значения и 1 для всех других элемен­тов.