グラフ内のすべての完全なサブグラフを見つけるための既知のアルゴリズムまたは方法はありますか? 無向で加重されていないグラフがあり、サブグラフ内の各ノードがサブグラフ内の他のノードに接続されているすべてのサブグラフを見つける必要があります。
このための既存のアルゴリズムはありますか?
21811 次
2 に答える
21
これはクリーク問題として知られています。それは難しく、一般的にNP完全であり、そうです、これを行うための多くのアルゴリズムがあります。
グラフに追加のプロパティがある場合 (2 部グラフなど)、問題はかなり簡単になり、多項式時間で解けますが、それ以外の場合は非常に難しく、小さなグラフでのみ完全に解けます。
ウィキペディアより
コンピュータ サイエンスでは、クリーク問題とは、グラフ内の特定の完全なサブグラフ (「クリーク」)、つまり要素の各ペアが接続されている要素のセットを見つけることに関連する問題を指します。
クリークの問題には次のものがあります。
- 最大クリーク (頂点の数が最大のクリーク) を見つける
- 重み付きグラフで最大重みクリークを見つけ、
- すべての最大クリーク (拡大できないクリーク) のリスト
- グラフに特定のサイズより大きいクリークが含まれているかどうかをテストする決定問題を解決します。
これらの問題はすべて困難です: クリーク決定問題は NP 完全 (Karp の 21 個の NP 完全問題の 1 つ) であり、最大クリークを見つける問題は固定パラメーターで扱いにくく、近似するのも困難です。指数関数的に多くの最大クリークを持つグラフが存在するため、指数時間。それにもかかわらず、指数時間で実行されるか、特定のより特殊な入力グラフを多項式時間で処理する、これらの問題に対するアルゴリズムがあります。
こちらもご覧ください
于 2010-05-10T08:02:12.620 に答える