Алгоритм редукции из гамильтонова цикла

Question

Я полагаю, что проблема гамильтонова цикла может быть суммирована следующим образом:

Учитывая неориентированный граф G = (V, E), a Гамильтонова цепь - это тур в G, проходящий через каждая вершина G один раз и только один раз.

Теперь я хотел бы свести мою проблему к этому. Моя проблема:

Для взвешенного неориентированного графа G, целого числа k и вершин u, v как в G, есть ли простой путь в G от u до v с общим весом по крайней мере k?

Таким образом, зная, что задача о гамильтоновом цикле является NP-полной, сводя эту проблему к гамильтониану, эта задача также оказывается NP-полной. Моя проблема заключается в функции, сводящей ее к гамильтониану.

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

Для (1) я имею в виду прохождение графа со всеми простыми путями общего веса МЕНЬШЕ, чем k исключено. Для (2) я думаю, что это на самом деле не проблема, потому что если есть гамильтонов цикл, то из него можно вырезать простой путь от u к v.

Итак, мои настоящие вопросы:

1. Мое решение даст мне правильный ответ?
2. Если да, то как я могу вынуть ребра, которые дадут простые пути общей массой меньше k, БЕЗ влияния на вероятность того, что один из этих ребер может потребоваться для фактического решения? Поскольку, если ребро e выбрано из-за того, что оно дает простой путь веса = k.

Спасибо!

Answer 1

Ваше сокращение в неправильном направлении. Чтобы показать, что ваша задача является NP-полной, вам нужно уменьшить ее до Hamilton Circuit, и это очень просто. То есть покажите, что каждая проблема Гамильтоновой цепи может быть выражена через ваш вариант задачи.

Answer 2

Больше подсказки, чем ответа:

Невзвешенный граф можно интерпретировать как взвешенный граф, где каждое ребро имеет вес 1. Какова будет стоимость гамильтонова цикла на таком графике?

Answer 3

Часть о несоответствии между циклами и путями является правильной и является проблемой, которую вам нужно решить. По сути, вам нужно доказать, что задача о гамильтоновом пути также является NP-полной (относительно прямолинейное приведение к задаче о цикле)

Что касается другой части, вы делаете вещи в неправильном направлении. Вам нужно показать, что ваша более сложная задача может решить проблему гамильтонова пути (и, следовательно, NP-сложна). Для этого вам просто нужно использовать специальный случай ребер с удельной стоимостью.