Задача

Для начала зададим себе два естественных вопроса:

♦ Как определить, содержит ли граф отрицательный цикл?

♦ Как найти отрицательный цикл в графе, в котором он присутствует? Алгоритм, разработанный для поиска отрицательных циклов, также приводит

к улучшению практической реализации алгоритма Беллмана-Форда из предыду- щих разделов.

Оказывается, идеи, описанные ранее, позволяют найти отрицательные циклы, которые имеют путь, достигающий конечной точки t. Но прежде чем углубляться в подробности, сравним задачу нахождения отрицательного цикла, способного до- стичь заданного t, с более естественной (казалось бы) задачей нахождения отрица- тельного цикла в любом месте графа независимо от его расположения относительно конечной точки. Как выясняется, разработка решения первой задачи позволяет также получить решение второй задачи следующим образом. Предположим, мы начинаем с графа G, добавляем в него новый узел t и соединяем каждый из осталь- ных узлов v в графе с узлом t через ребро стоимости 0, как показано на рис. 6.25. Назовем новый «дополненный граф» G'.

(6.29) Дополненный граф G' содержит такой отрицательный цикл C, что суще- ствует путь из C в конечную точку t в том и только в том случае, если исходный граф содержит отрицательный цикл.

Доказательство. Предположим, G содержит отрицательный цикл. Тогда цикл C очевидно содержит ребро к t в G', поскольку все узлы содержат ребро к t.

Теперь предположим, что G' содержит отрицательный цикл с путем к t. Так как никакое ребро не выходит из t в G', этот цикл не может содержать t. А поскольку G' совпадает с G во всем, кроме узла t, этот цикл также является отрицательным циклом в G. ■

Рис. 6.25. Дополненный граф


Итак, для решения задачи достаточно определить, содержит ли G отрицатель- ный цикл с путем к заданному конечному узлу t; этим мы сейчас и займемся.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения