Найти длину самого длинного следа в ориентированном невзвешенном графике
У меня есть ориентированный, невзвешенный, возможно, циклический граф, который может содержать петли и несколько повторяющихся ребер (т.е. два ребра от узла 1 до узла 2).
Теперь я хотел бы найти длину самого длинного следа в этом графе, то есть самый длинный путь, который: - не использует ребро дважды (но если имеется множество ребер от узла 1 до узла 2, он может использовать каждый из них) - возможно, посещает узлы несколько раз (т.е. это не должен быть простой путь)
В частности, эта проблема NP-сложная? Я знаю, что самый длинный простой путь - NP-hard (сокращает путь Hamiltonian Path к нему), а самый длинный путь с повторным использованием ребра - в P (Беллман форд с весом -1 на каждом ребре). Однако, с этой проблемой я не совсем уверен, и я не мог найти хорошую информацию об этом.
1 ответ
Хотя я не совсем уверен, я думаю, что эта проблема NP-сложная. Как я понимаю, ваш вопрос возникает из-за нескольких ребер между узлами. Графы с несколькими ребрами между одинаковыми узлами могут быть расширены до больших графов без множественных ребер между ними. Таким образом, граф с несколькими ребрами между одинаковыми узлами не имеет разницы, чем граф без нескольких ребер.
Позвольте мне пройти простой пример, чтобы объяснить: пусть будет граф с 3 узлами (A,B,C) и 5 ребрами между ними (от A до B, от A до B, от B до A, от B до C, от C до A) Этот график может быть расширен и показан с 5 узлами и 7 ребрами. Давайте расширим узел A до 3 разных узлов (A1, A2, A3). Когда мы настраиваем ребра в соответствии с предыдущими ребрами, существует 7 ребер (от А1 до В, от А2 до В, от Б до А3, от Б до С, от С до А1, от С до А2, от С до А3). В результате теперь мы имеем граф без кратных ребер и может быть оценен с помощью гамильтониана и беллмана форда.
Надеюсь, я хотя бы немного решил проблему.