Я беру класс Алгоритмы: проектирование и анализ II , один из вопросов:
Предположим, что P ≠ NP. Рассмотрим неориентированные графы с неотрицательным ребром
длины. Какие из следующих проблем могут быть решены в полином
время
Подсказка: задача о гамильтоновом пути: дан неориентированный граф с
n вершин, решите, есть ли путь (без цикла) с n
- 1 ребро, которое посещает каждую вершину ровно один раз. Вы можете использовать тот факт, что задача о гамильтоновом пути является NP-полной. Есть относительно
простые сокращения от гамильтоновой задачи пути к 3 из 4
проблемы ниже.
- Для заданного источника s и пункта назначения t вычислите длину кратчайшего пути s-t, который имеет ровно n - 1 ребра (или + ∞, если такого пути нет
существует). Путь может содержать циклы.
- Среди всех охватывающих деревьев графа вычислите одно с наименьшим возможным числом листьев.
- Среди всех охватывающих деревьев графа вычислите одно с минимально возможной максимальной степенью. (Напомним, степень вершины является
количество инцидентных ребер.)
- Для заданного источника s и пункта назначения t вычислите длину кратчайшего пути s-t, который имеет ровно n - 1 ребра (или + ∞, если такого пути нет
существует). Путь не может содержать циклы.
Обратите внимание, что гамильтоновый путь является остовным деревом графа и имеет только два листовых узла, и что любое остовное дерево графа с ровно двумя листовыми узлами должно быть гамильтоновым путем. Это означает, что NP-полная задача определения того, существует ли в графе гамильтонова траектория, может быть решена путем нахождения минимального листового остовного дерева графа: путь существует тогда и только тогда, когда минимальное листовое остовное дерево имеет ровно два листа , Таким образом, задача 2 является NP-полной.
Задача 3 NP-Hard; здесь - это документ, подтверждающий это.
Это означает, что между 1 и 4, один NP-Complete, другой в P. Кажется, что проблема 4 тривиально сводится к проблеме гамильтонова пути, но я не могу понять, как цикл делает его разрешима? Или это другой путь?