問題タブ [bipartite]

私はグラフ理論に関連することに取り組んでいます。実際、2部グラフのデータがいくつかあるので、グラフ形式で視覚化してその妥当性をテストしたいと思います。

私のデータは（三角形の場合）のような形式です：

Vは頂点を示し、Uはエッジを示します（A、B、C、およびEはラベルです）。誰かが私の目的に最も適したツール/ライブラリ（Java / C）を提案できますか？

グラフは初めてです。2部グラフに2つのセットがあります。考えられるすべての組み合わせの一意の一致を見つける必要があります。だから私はホップクロフト・カープを使って最大の一致を見つけると思った。初心者なので、結果の一致するグラフが得られると思いましたが、それが示すのは42だけです。ああ、それは本当に役に立ちます。マッチングがいくつあるかを知る必要はありません。独自のマッチング自体を知る必要があります。

私は何かが足りないのですか？結果のマッチングを取得するにはどうすればよいですか？

無向グラフが二部かどうかを判断するアルゴリズムを実装しています。この疑似コードに基づいて、接続されたグラフで機能する実装を作成しましたが、接続されていない場合、プログラムは単に間違った答えを示します。接続されていない場合は、バラバラのサブグラフごとにもう1つのループが必要だと思います。しかし、私はこれにこだわっています。正しい答えを印刷するためにコードを解決するにはどうすればよいですか?

たとえば、この入力の場合

出力は次のようになります。

代わりに私に出力をスローします：

これは、グラフが連結グラフではない、つまり 2 つの連結要素があるために発生します。数日間この問題に悩まされていたので、助けていただければ幸いです。

アルゴリズム設計の第1章を読みましたが、2部マッチングを独立集合問題に変換する方法について非常に短い説明がありましたが、わかりません。

このプロセスを説明する詳細なマトリエルを知っている人はいますか？ありがとう！

固定料金輸送問題 (FCTP) の優れた解決策を見つけるために、メタヒューリスティックを使用してコードを作成する作業を行っています。

私が抱えている問題は、基礎となる二部グラフのスパニング ツリーを見つけることに基づいて、開始ソリューションを生成することです。

同じ問題に対して手順を複数回実行し、異なる解決策を得ることができるように、ランダム スパニング ツリーにしたいと考えています。

私はこれを行うのにいくつかの困難を抱えています。私がこれまで行ってきたアプローチは、弧をランダムに並べ替えてから、このリストを繰り返し処理し、サイクルが作成されない場合はそれらを順番に基礎に置くことです。

アークを含めるとサイクルが作成されるかどうかを確認するための高速な方法を見つける必要があります。大きな問題が発生した場合、このアプローチにはかなりの時間がかかる可能性があるため、「ブルートフォース」はしたくありません。

アークAがランダムに置換された配列であるとすると、どのように選択手順を実行しますか?

私はこれに数時間取り組んできましたが、私が試したことは何もうまくいきませんでした。アプリケーションに関しては、ほとんどが無意味です...

ポイントがプロットされ、一部またはすべてにラベルが付いているグラフィカルな xy プロットからセマンティクスを抽出しようとしています。ラベルは「ポイントの近く」にプロットされるため、人間は通常、どのラベルがどのポイントに対応しているかを理解できます。たとえば、このプロットでは、どのラベル (番号) がどのポイント (*) に属しているかが明確であり、ユークリッド距離に基づくアルゴリズムが機能します。(ラベルとポイントには意味的な順序付けはありません - 散布図など)

混雑したプロットでは、オーサリング ソフトウェア/人間は、重複を避けるためにラベルを異なる方向に配置する場合があります。たとえば、

人間のリーダーは通常、どのラベルがどのラベルに関連付けられているかを判断できます。

私が受け入れる1つの解決策は、ユークリッド距離行列を作成し、行をシャッフルして関数の最小値を取得することです(たとえば、対角線または他のヒューリスティック上の距離の合計二乗)。2 番目の例 (北西の角から時計回りに a、b、c、d のラベルが付いた点) では、(1 dp までの) 距離行列があります。

ラベルを付ける必要がありa1 b2 c4 d3ます。行 3 と 4 を入れ替えると、対角線の最小和が得られます。最も近いものを選択するだけでは失敗する可能性がある、より複雑な例を次に示します。

これが解決された場合、ラベルの数がポイントの数よりも少ないか多い場合に行く必要があります。

アルゴリズムが標準である場合は、オープン ソース Java (JAMA や Apache maths など) へのポインタをいただければ幸いです。

注: この SO の回答ポイントを通るパスが指定されているため、近くのポイントをパスに関連付けることは回答としては機能しません。

状況: ユーザーが、プロジェクトの可能なパートナーとして他の複数のユーザーを選択します。ユーザーは、自分が選んだユーザーを別のユーザーより優先することはありません (つまり、リスト内のユーザーはパートナーとして十分です)。例：

実際のリストはもっと大きくなります。

私の質問: ユーザーとその優先パートナー (上記のリストなど) の配列が与えられた場合、最終的なパートナー ペアの配列を生成したいと考えています。最終的にパートナーになるペアの数を最大化する必要があります (できるだけ多くの人をペアにしたい)。

これは私が必要だと思うアルゴリズムです: Edmonds's matching algorithmですが、私は数学のバックグラウンドを持っていないため、解釈と実装に問題があります。

どんな助けでも大歓迎です。前もって感謝します。

つまり、一部の頂点が他の頂点に接続されていない可能性があるグラフの2部一致を見つけるにはどうすればよいですか？

編集：もう1つの条件として、エッジにも重みが付けられていると仮定します。エッジの重みの合計が最小化（または最大化）されるようにマッチングしたいと思います。

私の一般的な問題は、iGraph を使用してグラフを生成するときに、頂点の名前/ラベルが失われることです (ここで正しい単語がわからない)。

次のような二部ネットワークのエッジ リスト IC_edge_sub があります。

次に、グラフ要素を作成します。

次に、それを折りたたんで、companyID 間の接続のみを識別します

次に、隣接行列を取得します。

iGraph では、ノードの番号付けはゼロから始まるため、マトリックスの命名もゼロから始まります。ただし、代わりに、最終的な CC_matrix_IC_based マトリックスのエッジリストの 2 列目に指定されている「new_companyID」が必要になります。

元のエッジリストからの情報を使用して、最終的な隣接行列に行名と列名を入れる方法を教えてください。

私はそれをグーグルで検索し、スタックフローを検索しましたが、実際に機能する答えを見つけることができませんでした. 助けてくれてどうもありがとう

A=(a_1,a_2,...,a_m) と B=(b_1,b_2,...,a_n) の 2 つのセットがあるとします (同じサイズである必要はありません)。関数 F は、集合 A から集合 B までの各リンクに重みを割り当てます: F:A*B->R。したがって、たとえば、F(a_1,b_1)=2 は、a_1 と b_1 の間のリンクの重みが 2 であることを意味します。問題は、集合 A の要素を集合 B の要素に接続して、これらの制約を満たすリンクの重み:

• セット A の要素は、セット B の 1 つの要素と正確に一致する必要があります。
• セット B の要素は、0 個以上の一致 (0,1,2...) を持つことができますが、B の要素には重み C_i の合計に対する制約が存在します。つまり、a_1 を b_1 に接続することを選択した場合、および a_2 から b_1 の場合、重みの合計 F(a_1,b_1)+F(a_2,b_1) は C_1 以下でなければなりません。この制約は、B のすべての要素に対して存在します。

私はいくつかのアイデアを探し、代入問題とハンガリーのアルゴリズムを調べました。追加のことは、これらのどれもが私が持っている2番目の制約を考慮していないということです. これを解決する方法について何かアイデアはありますか？

ありがとう