グラフ内の最大重量のサイクル

Question

加重グラフ（指向または無向）が与えられた場合、最大重量のグラフのサイクルを見つける必要があります。

サイクルの重みは、グラフのエッジの重みの合計です。

それは私たちができるベースサイクルだけでなく、あらゆるサイクルになることができます

• すべてのベースサイクルを見つけます（参照してください 無向グラフのすべてのサイクルベースを識別するアルゴリズム )
• 各ベースサイクルの重量を計算し、最大を見つけます

グラフのすべてのサイクルを列挙してから最大値を計算しようとすることができますが、サイクルの総数は非常に大きくなる可能性があります（グラフが完了すると、最初と最後のものが同一である頂点のシーケンスがサイクルです）。

すべてのサイクルを列挙することなく、その最大重量サイクルを見つけることを考えていますか？

グラフで仮説が必要な場合（たとえば、ポジティブな重み）、それらを示してください。

Answer 1

これはNPハードです。

ハミルトニアンサイクルの問題はこれに減らすことができます。

ハミルトニアンサイクルが存在するかどうかを確認する必要があるグラフが与えられた場合、各エッジに重み1を割り当てます。

アルゴリズムを実行して、最大重量サイクルを取得します。重みが<nの場合、元のグラフにはハミルトニアンサイクルがありません。そうでなければそうします。

Answer 2

特定のケースで最小加重パスを見つけることができる場合は、すべての重みの兆候を逆にして、アルゴリズムを適用してください。もちろん、モロンの議論は正しいので、いくつかの未記述の仮定をしています（しゃれは意図されていません）。あなたが行っている仮定は、正の重量または負の重量サイクルではない可能性があります。可能な仮定の無限の空間で人々に検索させるのではなく、彼らを述べる努力をするべきだと思います。硬度の結果については、これも多くの方法で近似するのが難しいです、チェックしてください この紙. 。同じペーパーには、重要なタイプのグラフのいくつかの肯定的な結果が含まれていますが、最も長い重みのないパスに関係しているため、私の推測では、紙のほとんどのアルゴリズムはあなたの場合には直接役立ちません。 「重いサイクル」を検索すると、多くの興味深い論文が見つかりますが、性格はより数学的です。重量が小さい整数（グラフのサイズが多項式まで）の場合、すべてのエッジを非加重パスに置き換えて、問題を非加重ケースに減らすことができます。これがある程度役立つことを願っていますが、あなたはあなたの手にオープンな研究の問題があるかもしれません。