Является ли проблема нахождения простого пути с максимальной стоимостью во взвешенном неориентированном графе с тем же числом вершин и ребер NP-Complete?

Question

Привет и еще раз спасибо за чтение.

Теперь мне нужно знать, является ли проблема нахождения простого пути с максимальной стоимостью во взвешенном неориентированном графе с тем же числом вершин и ребер NP-Complete или нет?

Ввод: График G = (V, E) с V (вершина) = E (ребра)

Вывод: Стоимость самого дорогого пути в графе G.

Не могли бы вы дать какую-либо ссылку на статью, где я могу просмотреть это.

Большое спасибо за ваше время.

С уважением,

Alex.

Answer 1

Если граф не обязательно связан, то любой случай проблемы самого длинного пути можно свести к этой проблеме, добавив дополнительные изолированные вершины во входной граф, чтобы сделать число узлов и ребер одинаковыми.Если это не случай щитовидной железы, и граф должен быть соединен, то входной граф должен иметь ровно один цикл, так как граф с n-1 ребрами является деревом.Если вы нашли этот цикл с DFS и заключили его с одним узлом, то у вас есть дерево.Здесь легко выполнять вычисления с самыми длинными путями;просто рассмотрите все пары ребер и получите стоимость уникального пути между ними.Если вы выберете этот путь и затем развернете его в исходном графике, пройдя цикл, в котором вы изначально прошли контрактный узел, я думаю, вы получите самый длинный путь за полиномиальное время.

Answer 2

Эта проблема называется проблемой Longest Path и является NP-полной.

Ограничение |V| = |E| не помогает вообще.Вы можете решить произвольный граф, добавив несвязанные вершины до тех пор, пока не будете удовлетворять соотношению.