Алгоритм редукции из гамильтонова цикла - PullRequest
2 голосов
/ 04 декабря 2011

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

Учитывая неориентированный граф 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.

Спасибо!

Ответы [ 3 ]

5 голосов
/ 04 декабря 2011

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

3 голосов
/ 04 декабря 2011

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

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

2 голосов
/ 04 декабря 2011

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...