私のアルゴリズム クラスの課題の 1 つは、クリーク問題を解決するための徹底的な検索アルゴリズムを設計することです。つまり、サイズnのグラフが与えられた場合、アルゴリズムは、サイズkの完全なサブグラフがあるかどうかを判断することになっています。答えは出たと思いますが、改善できると思わずにはいられません。ここに私が持っているものがあります:

バージョン 1

input : 配列 A[0,... n -1] で表されるグラフ、検索するサブグラフのサイズk 。

output : サブグラフが存在する場合は True、そうでない場合は False

アルゴリズム(Python のような疑似コード):

バージョン 2

input : サイズ n × n の隣接行列、k は検索する部分グラフのサイズ

output : サイズ k の A 内のすべての完全なサブグラフ。

アルゴリズム(今回は関数型/Python 疑似コード):

ご意見、ご感想、ご提案はありますか? これには、私が見逃した可能性のあるバグと、これをより読みやすくする方法が含まれます (私は多くの疑似コードを使用することに慣れていません)。

バージョン 3

幸いなことに、課題を提出する前に教授に相談しました。私が書いた疑似コードを彼に見せたとき、彼は微笑んで、私があまりにも多くの仕事をしたと言った. 1 つには、疑似コードを提出する必要がありませんでした。問題を理解していることを証明する必要がありました。2 つ目は、彼は力ずくで解決することを望んでいたことです。それで、私が提出したものは次のようになりました。

入力: グラフ G = (V,E)、kを見つけるためのクリークのサイズ

output : クリークが存在する場合は true、そうでない場合は false

アルゴリズム:

1. デカルト積 V ^kを求めます。
2. 結果のタプルごとに、各頂点が互いに接続されているかどうかをテストします。すべて接続されている場合は、true を返して終了します。
3. false を返して終了します。

更新: 2 番目のバージョンを追加しました。(私が知っている)派手な動的プログラミングを追加していませんが、これは良くなっていると思います。

更新 2 : バージョン 2 をより読みやすくするために、いくつかのコメントとドキュメントを追加しました。これはおそらく今日私が提出するバージョンです。みんなの助けに感謝します！複数の回答を受け入れることができればいいのですが、私を最も助けてくれた人の回答を受け入れました. 先生の考えをお伝えします。

グラフは、任意の頂点が残りの頂点と接続されているグラフのサブグラフです。

k-問題では、入力は無向グラフと数値 k であり、出力は、存在する場合はサイズ k の clof (または、サイズ k のすべての cl) です。

「G がサイズ k のクリークとサイズ k の独立集合の両方を持っているかどうか、与えられた入力 G と k を決定することが NP-Complete であることを証明してください。これは 2 ではなく 1 つの問題であることに注意してください。答えは、次の場合にのみ「はい」です。 G にはこれらのサブセットの両方があります。」

この問題は私のアルゴリズム コースで出されましたが、大勢の学生がそれを理解できませんでした。ここに私たちがこれまでに持っているものがあります...

クリーク問題と独立集合問題の両方が、それ自体で NP 完全であることはわかっています。いくつかの「証明書」がNPにある場合、この問題の検証が行われることもわかっています。

この問題は、上記の問題 (独立集合とクリークの両方を含む) を、完全にクリークまたは独立集合で構成される問題のいずれかに縮約することです (少なくとも、それは私たちが行う必要があると考えていることです)。リダクションを元の形式に戻すために必要な情報を失うことなく、このリダクションを実行する方法はわかりません。

クリークカバー問題を解決するライブラリまたはコード（できればJava）を知っている人はいますか？

OCamlバージョンを見つけましたが、もっと簡単に統合できるものを使いたいです。

グラフで最大クリークを見つけるためのJavaコードとCコードも見つけましたが、このコードを利用してクリークカバーを見つける方法がわかりません（たとえば、ノードがなくなるまで最大クリークを繰り返し削除します）。最適なソリューションは得られません）。

私は現在、最終年度のプロジェクトのグラフで最大クリークを見つけるためのアプリケーションの開発に取り組んでいます。私はほとんどのプロジェクトを完了し、アプリケーションのテストを開始したばかりです。

アプリケーションは現在、隣接リストを入力として使用していますが、誰かが隣接リストのランダムジェネレーターを知っているかどうか疑問に思っていたので、アプリケーションをテストできますか？

どうもありがとう

私は基本的なクリークの問題を解決しようとしていましたが、次のいくつかの点で立ち往生しています:

• what is is the minimum size of the largest clique in any graph with N nodes and M edges

• To Find the largest clique in a graph

上記の2つのステートメントの違いを教えてください。

大学のプロジェクトでは、 Bron-Kerboschアルゴリズムを実装しようとしています。つまり、特定のグラフにすべての最大クリークをリストします。

私は最初のアルゴリズムを（ピボットせずに）実装しようとしていますが、ウィキペディアの例でテストした後、私のコードはすべての答えを生成しません。これまでの私のコードは次のとおりです。

答えの一部しか得られない理由はありますか？

Bron-Kerbosch アルゴリズムの C バージョンの実装に問題があります。

1-アルゴリズムの仕組みがまったくわかりません。私はインターネットで参考文献を見つけようとしましたが、それらはすべてひどいアルゴリズムの実装例でくだらないものであり、疑似コードに表示される任意の名前の関数 ( P(N) など) の説明はまったくありません。

2- インターネットでいくつかの C++ 実装を見つけましたが、作成者がコードで使用されているクラスを配置できなかったため、変数の名前がまったくわからないひどい名前の変数が残っています (compsub、nod、minnod など)。 、fixp、newne、newce)。

私が翻訳できた 1 つのコードは SegFaulting です。アルゴリズムを理解するのを手伝ってもらえますか/コードで何が間違っていたか教えてください。

役立つ情報:

graph->matrix は接続性マトリックスです。

List_clear は、リストのサイズを返します。