問題タブ [bipartite]

重み付けされていない二部グラフで最大一致サイズを見つけるために、拡張パスまたはクーンのアルゴリズムを読んでいました。

アルゴリズムは、一致しない頂点で開始および終了する交互パス (一致しないエッジと一致するエッジを交互に含む) を見つけようとします。代替パスが見つかった場合、パスが拡張され、一致するカウントが 1 増加します。

アルゴリズムは理解できますが、一般的な実装方法を理解するのに問題があります。これがリファレンス実装です - https://sites.google.com/site/indy256/algo/kuhn_matching2。

各段階で、左側の一致しない頂点から始まる代替パスを見つけようとする必要があります。ただし、指定された実装では、次のコードに示すように、反復ごとに、すべての一致しない頂点を可能な開始位置として試す代わりに、1 つの一致しない頂点のみから検索を開始します。

このようにして、反復中に一致しない左側の頂点が再試行されることはありません。なぜこれが最適なのか理解できませんか？

私は最近この問題に遭遇しました。それが NP-Complete であるか、多項式時間で解けるかどうかを知りたいです。

加重二部グラフ G=(V,E) が与えられた場合、V は 2 つのセット A と B に分割でき、E は A と B を接続するエッジのセットです。エッジ (v,u) の重みは w( v、u)。

以下を順番に実行します。

1. ノード v∈A を選び、
2. (v,u)∈E ごとにすべてのノード u∈B を削除し、
3. 削除されたすべてのエッジの合計スコアに重み w(v,u) を追加します。

目標は、合計スコアを最大化する一連のノード v1,…,vn∈A を見つけることです。

NP-Complete問題のバンクを検索して、この問題に還元できる可能性のあるものを見つけましたが、まだ有用なものは見つかりませんでした。どんな提案も非常に役に立ちます！

Rの有向二部グラフの形で2つのリスト間の要素の位置の変化をプロットする簡単な方法があるかどうか疑問に思っています。たとえば、リスト1と2は文字列のベクトルであり、必ずしも同じものを含むとは限りません要素:

次のようなものを生成したいと思います。

私は igraph パ​​ッケージの使用に少し苦労しましたが、私が望むものを簡単に構築することはできませんでした。

乾杯。

標準的な 2 部分割の問題を解決しようとしています。つまり、出力グラフが 2 部グラフになるようなエッジのサブセットを見つけようとしています。私の追加の制約は次のとおりです。

1. 両側の頂点の数は等しくなければなりません。
2. 各頂点にはちょうど 1 つのエッジがあります。

実際、そのようなサブセットが存在するかどうかを知るだけで十分です。構築自体は本当に必要ありません。O(400) ノードに対して繰り返し実行する必要があるため、最適なアルゴリズムは高速である必要があります。

次の図を取得しています。適切な二部グラフのように見せるにはどうすればよいですか?

私はRの初心者で、助けになるものは何も見つかりませんでした。サイズが異なるランダム行列を生成したい。for ループと関数を使用したかったのですgenwebが、多くの行列の代わりにベクトルが返されます。