エッジ値の合計が0より大きいグラフに特定のエッジを含むサイクルが存在するかどうかを確認します。

Question

各エッジが実数値を持つ無向グラフがあるとします。そのサイクルの各エッジの値の合計としてサイクルの「合計」を定義します。

あるエッジEを含むグラフ内に、合計が0より大きく/より小さいサイクルが存在するかどうかをチェックする合理的な方法はありますか？今、私の（非常に粗悪でひどく非効率的な）ソリューションは、エッジが入っているすべてのサイクルをチェックすることです。

アルゴリズムは正確なサイクルを見つける必要はなく、そのようなサイクルの存在を確認する必要があります。

Answer 1

を単純にサイクルだけ許可すると仮定すると、いいえ、Hamiltonian Path Problemを効率的に解決できるため、効率的なアルゴリズムはありません。 （つまり、この問題はNP-Hardです）。

削減：

（我々がゼロに等しい/大きい重みを持つようにシンプルサイクルがある場合、我々は見つけるあなたの問題のバリアントを使用します）。直感的に

G' = (V',E') 
V' = V U {s,t} 
E' = E U { (s,v), (v,t), (s,t) } 
And add weights to the graph: 
w(s,t) = -|V'| + 1 
w(u,v) = 1 for u!=s and v!= t 

、私たちは、「ソース」と「ターゲット」ノードを追加する他のすべてのノードに接続し、負に接続された2つのノードを作成：グラフG=(V,E)、新しいグラフを構築考える

すべてのパスの重み。

新しいアルゴリズムには、(G', (s,t))が減少しています。

元のグラフのハミルトニアンパスがv1->v2->...->vnの場合、新しいグラフの周期はs->v1->v2->...->vn->t->sであり、その合計は0になり、単純なサイクルになります。

簡単(s,t)を使用G'におけるサイクル、および合計0より大きい任意の数のがあれば、それが使用(s,t)除く他のすべてのエッジの重みの合計が少なくとも|V'|-1であることを意味します。 これは、このサイクルに正確に|V'|個のノードがあることを意味します。これはグラフ全体であり、サイクルはs->t->v1->v2->...->vn->sであることがわかります。これは単純なのでv1,v2,...,vnは元のVのすべてのノードです。ハミルトン経路であるv1->v2->...->vnです。

結論：私たちはHamiltionian Pathからあなたの問題への多項式時間の短縮を示しました.HPはNP-Hardなので、この問題もあります。