問題タブ [bipartite]

二部グラフ G = (V, U, E) があるとしましょう

v1 は u1、u2、および u3 に接続されています

v2 は u2 と u3 に接続されています

v3 は u3 に接続されています。

グラフを見ると、頂点カバーの最小値が {v1, v2, u3} と {v1, u2, u3} であることがわかりますが、2 部マッチング/頂点カバー アルゴリズムを使用してこれを見つける方法がわかりません。 . ここ とここ

手動でアルゴリズムを実行すると、出力は V のすべての単純な最小頂点カバーだけになります。何か間違ったことをしていますか?

編集：

グラフの最大一致は、エッジ (v1、u1)、(v2、u2)、および (v3、u3) です。最大の一致が与えられた場合、次のステップは、不飽和頂点 (一致したエッジの終点の 1 つではない頂点) から開始することです。

しかし、この場合はすべての頂点が飽和しているため、どうすればよいかわかりません。

1000 個の頂点を持つ 2 部リスト (投稿、単語カテゴリ) があり、コミュニティ検出に高速で貪欲なアルゴリズムを使用したいのですが、2 部グラフまたは 2 部投影で実行する必要があるかどうかはわかりません。

私の二部リストは次のようになります。

プロジェクションなしで実行すると、2 番目のステップでクラスタリングに問題が発生します。

たぶん、プロジェクションでコミュニティ検出を実行する必要がありますか? しかし、射影はグラフ オブジェクトではないため、常に失敗します。

喜んでお手伝いします！

二部ネットワークを構成する 100 万行で構成される大規模なデータがあります。ネットワークの片側は APP を表し、反対側は IP を表します。

データ形式は次のとおりです。

私がやりたいのは、igraph（pythonインターフェース）で何かを書いて、データを片側に投影することです。例えば

重みは、1.1.1.1ノードが 1 つの共通 A​​PP (1) と共通 APP (2) を共有することを表します。1.2.1.1

そして、体重を次の形式のファイルに保存したいtxt

でこれを処理する方法が少し混乱していigraphます。

igraphこの問題を処理できますか?

ありがとう

頂点セット A と B の両方が m 個の重み付き頂点を持つ有向 2 部グラフを考えてみましょう。エッジは A から B にのみ移動し、A のすべての頂点は同じ次数 (n で表す) を持ちます。頂点の重みは、次数によって上限が決まります。

例として、m = 4 および n = 2 を考えます。したがって、それぞれ 4 つの頂点を持つ A と B があり、A の各頂点から B に向かう 2 つのエッジがあります。A の頂点のすべての重みの上限は 2 です。

A から B へのすべての可能なエッジ フロー、特に B で結果として得られる頂点の重みをループすることに関心があります。これを C でできるだけ効率的に実行したいと考えています。これは、深さ優先検索のサブルーチンです。

私は本当にあなたの賢い入力を願っています:)

編集：すべてのエッジの容量は1です

これは宿題ではありませんが、調査中に遭遇した質問です。この問題が NP 困難かどうかを知る必要があります。前者の場合は近似アルゴリズムが必要であり、後者の場合は最適解を提供する効率的なアルゴリズムが必要です。

非公式の説明:

p 人が t 個のツールを使用していると想像してください。すべての人がすべてではなく、2、3 のツールしか使用していません。誰がどのツールを使用したかを誰かが書き留めます。質問: 各人が少なくとも k 個のツールを使用し、他の人も使用する最大のグループを見つける方法は? 【事前問題解説：みんなと同じ道具？】 道具の数がt'に制限されている

この問題の正式な説明を作成しました。これは役立つ場合があります。

G=(P,T,E) を2 部グラフとします。ここで、P は人の集合を表し、T はツールの集合を表します。人がそのツールを使用した場合、P のノード p と T の t の間にエッジがあります。目標は、次の条件が適用されるセット P'、T' を見つけることです。1) P' 内の任意の p' から、T' 内の任意の t' に単一のエッジで到達できます。2) |P'|、つまり P' 内のノードの数は最大です。

非効率的なアプローチは、各サブセット P' を取得し、P' 内の p' に関連付けられた各 t' の交差を計算することです。残念ながら、そのようなサブセットの数は指数関数的に増加し、計算はすぐに扱いにくくなります。

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

片側に N 個のノードがあり、反対側にほぼ 100 個のノードがある二部グラフがあります。ここで、最初の部分の各ノードが他の部分のノードへのリンクを持ち、最初の部分の 2 つのノードが 2 番目の部分の同じノードに一致しないように、一致をカウントする必要があります (1 つのジョブを 1 つのノードに割り当てることができるように)。申込者のみ）

このカウントを見つけるのは簡単ではなく、#P 困難な問題であることがわかりました (リンクから: https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in -一般的なグラフ)

しかし、そうするための野蛮な解決策は何でしょうか?誰かがコードまたは疑似コードで説明してください。

入力が、u が v に接続されていることを示す X ペアを持っているようなものであると仮定します

N=2 および X=4 で、ペアが (1,1)、(1,2)、(2,3)、(2,4) の場合。