ループと複数の重複エッジ (つまり、ノード 1 からノード 2 への 2 つのエッジ) を含むことができる有向で、重み付けされていない、場合によっては巡回グラフがあります。
このグラフで最長のトレイルの長さ、つまり次のような最長パスを見つけたいと思います。ノードを数回訪問する可能性があります (つまり、単純なパスである必要はありません)。
特に、この問題は NP 困難ですか? 最長の単純なパスは NP 困難 (ハミルトニアン パスをそれに減らす) であり、エッジの再利用を伴う最長のトレイルは P (すべてのエッジで重みが -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 つのエッジが存在します (A1 から B、A2 から B、B から A3、B から C、C から A1、C から A2、C から A3)。複数のエッジを持たないグラフで、ハミルトニアンとベルマン フォードの助けを借りて評価できます。
少なくとも問題が少し解決したことを願っています。