問題タブ [bipartite]

二部グラフのエッジの中で最小の加重エッジを取得する単純なアルゴリズムを探しています。私が検索したところ、2部グラフがあり、各エッジに数の重みがあり、それらの中で最小の数を取得する方法がある場合、2部のカバーエッジを意味することをすべて知ることができました

私はgraphvizで2部グラフを描いています.2列のノードを直線で接続したいです(他の場所で使用されているスタイルに一致させるため)。ほとんどの場合、必要なものを取得できます (画像を参照) が、列が近すぎて端をたどるのが不必要に難しくなります。

2 つのサブグラフを引き離すことを期待して、上位 2 つのノード間に非常に低い重みの接続を追加しようとしましたが、うまくいきません (そして、レイアウトの残りの部分が台無しになることがよくあります)。ノードの右側の列をさらに右に移動する方法はありますか。

これは私が見ている問題を示す例です

これが、このグラフを生成するために使用したコードです

幅優先探索を使用して、単純な（指示されていない）2部グラフで最短のサイクルを見つけるにはどうすればよいですか？

最大の2部マッチングの問題を解決するために、作成したコードをテストする必要があります。テストに使用できる大きなデータセットの例を知っている人はいますか？理想的には、これらは2部グラフの数値表現で構成され、できれば大きなサイズで、さらに理想的には、結果を確認できるように事前に解が含まれています。

C# で 2 部グラフを視覚化するためのライブラリまたはコードを誰かが推奨できますか?

Graph# は、この種のグラフを直接サポートしていないようです (ただし、頂点のもつれを解くためのサポートはいくつかあります)。

この2 部グラフのように、ノードにテキストを含むグラフィックを作成したいと考えています。同じ幅と高さのノードが理想的です。

グラフ番号に存在する WPF コントロールは完璧です。おそらく、XAML 定義さえ存在するのでしょうか? 別の方法として、レポート ウィンドウも非常に有効です。

おそらく、Graph# の経験が豊富な人なら、Graph# を利用してこれを行う方法についてヒントを提供できます。

NodeXL で少し試してみましたが、ノードはそれほど変更可能ではないように見えるため、完全な解決策ではないようです。おそらく、誰かがより良い解決策を提供できるでしょう。Soroush が提供する NetworkView で遊んでみました。現時点では、これは私が望むものに最も近いものです。

-更新- Soroush Falahati によって共有された NetworkView を試しました。これは良いベースのようですが、私が必要とするほど柔軟ではありません。これらのことをすぐに実行できるライブラリがそこにないと信じるには問題があります。(NetworkView には、コントロールに接続/エッジを設定する優れた機能があり、NodeXL をさらに強化します)。おそらく、Graph# はさらに多くのことを行うことができますが、現時点ではそれらの 2 つを試しただけです。

多くのアルゴリズムが実装されているこのライブラリがあり、そのうちの1つは最大2部マッチングです。

ソースコードへのリンクは次のとおりです：http ：//shygypsy.com/tools/bpm.cpp

ここにも含めます（コメントなし）

実行時間のforループがありますm。数字mは労働者の数を表しています。次に、bpm別のforループを持つ関数に入ります。このループは、タスクの量であるn回数を実行します。n

今まではm*n時間計算量がありました。

bpmただし、3番目のifステートメントにはの再帰関数呼び出しがあります。この関数の目的はdfs、拡張パスを見つけるためにを実行することです。

私はそれdfsが時間の複雑さを持っていることを知っていますO(n+m)。したがって、関数bpmの複雑さは次のようになります。O(n+m)

したがって、合計時間計算量は次のようになります。O(m*(n+m))

しかし、作者はそれがだと言いますO(m*n^2)。誰かが私にこれが事実である理由を説明できますか？前もって感謝します！

与えられた は二部グラフであり、すべての極大完全二部サブグラフをリストしたいと考えています。

例えば、

頂点集合 L = {A, B, C, D}

頂点集合 R = {a, b, c, d, e}

エッジ: Aa、Ab、Ba、Bb、Cc、Cd、Dc、Dd、De

完全な二部構成の最大値は次のとおりです。

{A,B}-{a,b}

{C,D}-{c,d}

{D} - {c、d、e}

ブルート フォース アルゴリズム O(2^n) を見つけました。近似アルゴリズムかランダム化アルゴリズムかはわかりません。

私は二部グラフを検出するアルゴリズムを作成していますが、私のアルゴリズムはそう言っていますが、二部グラフとしてカウントされるかどうかわからないグラフを考えました。

グラフは次のようになります

したがって、これには 3 つのノードがありますが、 と の間にのみエッジが 1 つAありBます。これは実際に二部構成ですか？

二部グラフで「最小」「選択」を見つけることができるアルゴリズムを探していると思います。各頂点には、それを選択するための (整数の) コストが関連付けられています。コストではなく、選択したセットの頂点の数を最小限に抑えるアルゴリズムしか見つかりません。以前は「マッチング」が必要だと思っていましたが、実際には、すべてのエッジをカバーする頂点のサブセットが必要なだけです...

貪欲な解決策はうまくいかないと思います。セットが A、B であるとします。

頂点 1、2、3 は A にあり、コストは 1 です。頂点 4 は B にあり、コストは 2 です。

解決策は、最も高価な頂点 4 を削除することです。コストに基づいて選択した貪欲な解決策は失敗します。同様に、B のコストが 10 の場合、最も接続されている頂点を貪欲に選択することはできません。

別の言い回しを考えました:「各頂点にコストが関連付けられている 2 部グラフがある場合、選択したサブセット内の少なくとも 1 つの頂点にすべてのエッジが含まれるように、最小コストの頂点のサブセットを見つけます」。

The Algorithm Design Manualでは、著者はグラフを 2 色で着色するためのアルゴリズムを提供しています。これは、コンポーネントの数をカウントするアルゴリズムに似ています。使用可能なすべての頂点を反復処理し、検出されない場合にのみ、その頂点に色を付けて BFS を実行します。

BFS は、エッジが処理されていない場合、またはグラフが有向であるprocess_edge場合に関数を呼び出します。BFS は次のようになります。yx -> y

関数は次のprocess_edgeようになります。

ここで、次のようなグラフがあるとします。

次のように 2 色にできます。

ただし、頂点の順序でトラバースする場合は、最初に node から開始し、それを に1色付けしWHITEます。次に、ノードを見つけ13て に色付けしBLACKます。ループの次の反復では、ノードが検出されてい5ないため、色をWHITE付けて BFS を開始します。これを行っている間に、ノード5との間の競合が検出されます。次に、 と の間に別の矛盾があることを発見します。11BLACKWHITE11313WHITEBLACK

すべてのコンポーネント (接続されているかどうかに関係なく) を介してグラフの通常のトラバーサルを実行する場合、いずれにせよすべてのノードにアクセスすることになるため、順序は問題になりませんが、グラフに色を付ける場合は順序が問題になるようです。私は本でこれについての言及を見たことがなく、上記のようなランダムに生成されたグラフを 2 色にしようとしたときにのみ、この問題に出くわしました。既存のアルゴリズムに小さな変更を加えることができたので、この問題は解消されました。

この変更は理にかなっていますか、それとも基本的な概念を理解していないためのハックですか?

アップデート

G.バッハの回答に基づいて、次のグラフがあると仮定します。

どうすればこれが適切に 2 色になるのか、私はまだ混乱しています。元のアルゴリズムでは、最初の反復でノードを使用して BFS が開始され、次1のような色のグラフが得られます。

次の反復では、ノード5を使用して BFS を開始し、次のような色のグラフを表示します。

次の反復では、ノードを使用して BFS を開始し、次6のような色のグラフを表示します。

しかし、ここで5は既にアクセス済みであるため、色を変更しません。これにより、適切に色付けされていないグラフが残ります。