DFS について簡単な質問があります。問題全体を解決する方法ではなく、使用方法を理解しようとしています。私は宿題の解決策ではなく、説明を本当に探しています。
まず質問を書きます。
「無向グラフ G=(V,E) があり、その 3 つの頂点を v1、v2、v3 と呼ぶとします。これらの 3 つの頂点がクリーク (完全なグラフ) の一部であるかどうかを判断するアルゴリズムを見つけてください (k> =3)"
今、それを解決するために DFS を使用するとします。私が理解している限り、DFS は、v1、v2、および v3 が同じ強く接続されたコンポーネントにあるかどうかを知らせてくれます。私が正しければ、G もクリーク (完全なグラフ) であるかどうかも判断する必要があります。
インターネットで読んだところ、グラフがクリークであるかどうかを主張することはNPであり、簡単に解決できないことがわかりました。私は正しいですか？何か不足していますか？グラフが完全かどうかをすぐに判断するために使用できるプロパティはありますか?
NP 完全性に関する混乱を明確にするために、グラフがクリークであるかどうかのチェックは NP 完全ではありません。エッジを数えて、n(n-1)/2 があるかどうかを確認します。NP完全とは、最大クリーク（最大数の頂点を持ち、クリークであるサブグラフを意味する）またはn個の頂点のグラフでk個の頂点のクリークを見つけることです（kがaではなく入力の一部である場合）固定数); 後者のケースはクリーク決定問題と呼ばれます。
編集:強く接続されたコンポーネントについても質問したことに気付きました。その用語は有向グラフにのみ適用されます (つまり、辺には方向があります。つまり、2 つの頂点vとwの場合、辺v->wは辺と同じではありませんw->v)。クリークは一般に、連結成分しかない無向グラフで定義されます。
私の理解が正しければ、これら 3 つの頂点が接続されているかどうか、つまりエッジ v1-v2、v2-v3、v3-v1 が存在するかどうかを確認するだけで済みます。それらが存在する場合、それらは K=3 のクリークを形成します。それらの少なくとも 1 つが一致しない場合、これら 3 つの頂点を合わせてサイズ k>=3 のクリークにすることはできません。