<<
>>

Расширения: задача о гамильтоновом пути

Иногда бывает полезно рассмотреть разновидность задачи о гамильтоновом цикле, в которой не обязательно возвращаться к начальной точке. Для заданного направ- ленного графа G = (V, E) путь Р в G называется гамильтоновым путем, если каждая вершине входит в него ровно один раз.
(Путь может начинаться с любого узла и заканчиваться на любом узле при условии соблюдения указанного ограничения.) Такой путь состоит из разных узлов if∙, v,............... в определенном порядке, образую-

щих все множество вершин V; в отличие от гамильтонова цикла, наличие ребра из обратно в V; не обязательно. Задача о гамильтоновом пути формулируется так:

Содержит ли заданный направленный граф G гамильтонов путь?

Используя сложность задача о гамильтоновом цикле, мы покажем следующее.

(8.19) Задача о гамильтоновом пути является ЖР-полной.

Доказательство. Прежде всего задача о гамильтоновом пути принадлежит ЖР: сертификатом может быть путь в G, а сертифицирующий алгоритм проверяет, что он действительно является путем и каждый узел входит в него ровно один раз.

Один из способов демонстрации ХР-полноты задачи о гамильтоновом пути за- ключается в сведении от 3-SAT, почти идентичного тому, которое мы использовали для задачи о гамильтоновом цикле: мы строим граф, изображенный на рис. 8.7, с тем отличием, что в него не включается ребро из t в 5. Если в измененном графе нет ни одного гамильтонова пути, он должен начинаться в 5 (так как 5 не имеет входящих ребер) и завершаться в t (так как t не имеет выходящих ребер). Одно изменение позволяет более или менее дословно применить аргумент, использо- ванный в сведении гамильтонова цикла, для обоснования того, что выполняющее присваивание для экземпляра 3-SAT существует в том, и только в том случае, если существует гамильтонов путь.

Альтернативный способ демонстрации ХР-полноты гамильтонова пути ос- нован на доказательстве Гамильтонов цикл

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

Еще по теме Расширения: задача о гамильтоновом пути:

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