こんにちは、これを読んでくれてありがとう。同じ数の頂点とエッジNP-Completeを持つ、重み付けされた無向グラフの最大コストを持つ単純なパスを見つける問題がありますか？
頂点と辺の数が同じで重み付けされた無向グラフで最大コストの単純なパスを見つける問題がNP完全であるかどうかを今知る必要がありますか？
入力：V（頂点）= E（エッジ）とグラフG =（V、E）
出力：グラフの中で最も高価な経路のコストG.
私はこれを見直すことができる記事への参照を提供することができますか？
ありがとうございます。
よろしくお願い致します。
アレックス。
グラフが必ずしも接続されていない場合は、入力グラフに余分な孤立した頂点を追加してノードと辺の数を同じにすることで、最長パス問題のインスタンスをこの問題に減らすことができます。これが甲状腺症例でなく、グラフを接続しなければならない場合、n-1辺のグラフがツリーであるため、入力グラフはちょうど1サイクルでなければなりません。 DFSでこのサイクルを見つけ、それを単一のノードに収めたら、ツリーがあります。ここで最長のパス計算を行うのは簡単です。すべてのペアのエッジを考慮し、それらの間のユニークなパスのコストを取得します。この経路をとって元のグラフを展開していたのであれば、最初に契約したノードを通過したサイクルを歩いて、多項式時間で最長の経路を得たと思います。
この問題はLongest Path Problemと呼ばれ、NP完全です。
制限|V| = |E|は一切役に立ちません。関係を満たすまで、未接続の頂点を追加することで、任意のグラフを解くことができます。
これは奇妙な説明です。グラフが木であることを意味しますか？ –
@ニキータ木のようには見えません。 N個のノードを持つ3つのエッジはN - 1個です。 – Michael
それはまったく木ではありません。同じ数の頂点とエッジを持つグラフです。たとえば、頂点が1 2 3で、1〜2〜3の間にエッジがあるグラフ3-1。 3つの頂点と3つのエッジを持ちます。 –