問題タブ [independent-set]

ガウス消去法のバージョンをプログラムして、一連のバイナリ ベクトルの線形独立性を検証しました。評価して返す行列 (mxn) を入力します。

• True (線形独立): ゼロ行は見つかりませんでした。
• False (線形依存): 最後の行がゼロの場合。

常に、または少なくともほとんどうまく機能しているようです。行列の最後の行に2 つの重複したベクトルがある場合、機能しないことがわかりました。

この関数は、行列が「線形独立」であることを示しています。これは、ゼロ行が見つからず、結果に実際に存在するためです。しかし、デバッグすると、ある時点で行がゼロになることがわかりましたが、その後、いくつかの行操作の後、「通常」に戻ります。

私はコードを再確認しましたが、それを機能させる唯一の方法は、プロセスの終了前、より正確には行操作中に「ゼロ行」が見つかった場合にも「false」を返すことでした:

これが正しいのか、それとも悪いコードに「パッチを当てている」だけなのか知りたいです。

ありがとうございました！

以下の完全なコード:

私の仕事は、グラフの彩色に使用される色の最小数を確認することです。これは単にグラフの色数です。私の無向グラフは 2-regular (各頂点は 2 度) です。私はその解決策を見つけました

(最大独立集合数)/頂点数=色数(彩色数)

https://imgur.com/a/ZtyP4v9 - どのように見えるか

ご覧のとおり、結果が 2 の場合は 2 色になり、結果が 2 より大きい場合は 3 色になります。

しかし、そのようなグラフで最大の独立セットを見つける方法がわかりません。

始めるのが難しいと感じている宿題の問題があります。扱いにくいことを示すために、Karp (シングル コール) 削減に取り組んでいます。この課題では、問題は意図的にあいまいです。ここの誰かがそれを知っているか、私が始めるのに役立つ解決策の例を提供できることを望んでいました.

問題は、提供されたコードでのみ説明されています。次のコンポーネントがあります。

B = (G, T, k) ここで、B は「Blah」問題のインスタンス、G = (V,E) はグラフ (重みなし、無向)、T は V の頂点のサブセット、k は整数。B の証明書は、G のサブグラフ S = (V', E') を返します。yes インスタンスの検証子も提供されます。

はいのインスタンス

この問題と Independent-Set または Vertex-Cover の問題との間にいくつかの類似点があります。これらは扱いにくいことを示すために還元するのに適した候補だと思いますが、まだ問題を十分に理解していません。この問題に関する議論がどこかにある場合、または誰かがいくつかの例を提供できる場合は、大いに感謝します。ありがとうございました！