問題タブ [bipartite]

料理人を雇いたいホテルが N 軒、仕事を探している料理人が N 人いるとします。したがって、インタビューを行った後、各ホテルは好みに応じて独自の順番に並べた料理人のリストを作成し、同様にすべての料理人も同様に準備しました。好みに応じて順序付けられたホテルのリスト。ここで、すべてのホテルと料理人の好みのリストが与えられ、何人のホテルと料理人が最初の好みを得るかを計算する必要があります。

例 : N=4 で、降順のホテルの好みのリストが次のようになっているとします。

1 2 3 4

2 3 4 1

4 2 3 1

1 3 2 4

同様に、料理人の好みのリストは次のとおりです。

1 2 3 4

4 3 2 1

4 2 3 1

4 1 2 3

ここで、1 人のホテルが彼の最初の好みの料理人を獲得し、2 人の料理人が好みのホテルを獲得します。

これらのホテルと料理人の両方が最初に優先するオプションを取得する数を見つける必要があります

Xにはn個のノードがあり、Yにはm個のノードがあり、nはm未満です。セット X をセット Y に一致させ、X のすべてのノードを最後に取得する際に 2 つのエッジが交差しないように、完全に交差のないマッチング グラフが必要です。結果のグラフの重みの合計は最小限に抑える必要があります。動的プログラミングアルゴリズムを考案する。これは私がそれを考えた方法です：

X と Y のノードは x0 に配置され、xi は Y0、Yi などへの水平エッジを持つことができますが、Y は X よりも多くのノードを持ちます。 Y、または対角近傍 (i, j-1)、(i,j+1) を設定し、コストを最小化するエッジを選択します。また、X と Y で既に取得されているノードを追跡します。時間の複雑さ O( nm)

これを実装できるより良い方法はありますか。どんな助けでも大歓迎です。これは私が中間試験で受けた質問ですが、選択に任せました。

次のようなゲームに関するプログラミング コンテスト ( Andrew Stankevich Contest 21 )の問題にしばらく苦労しました。

Nick と Peter は次のゲームをするのが好きです [...]。彼らは無向二部グラフ G を一枚の紙に描き、その頂点の 1 つにトークンを置きます。その後、彼らは順番に動きます。ニックが先に動く。

移動は、グラフ エッジに沿ってトークンを移動することで構成されます。その後、移動前にトークンがあった頂点とそれに付随するすべてのエッジがグラフから削除されます。有効な動きがないプレイヤーはゲームに負けます。

グラフが与えられ、与えられた開始ノードについて、両方のプレイヤーが最適にプレイした場合に開始プレイヤーが勝つか負けるかを見つけることがタスクになります。要約する

• 二部グラフ
• 開始ノードが与えられます (左側にあるとします)。
• 順番に移動します。移動はエッジをたどることで構成されますが、既にアクセスしたノードにアクセスすることはできません
• 動けなくなったプレイヤーが負け

グラフは 2 部構成であるため、Nick (最初のプレーヤー) は常に左側からノードを削除し、Peter は常に右側からノードを削除します。

グラフには最大 1000 個のノード (各辺で最大 500 個) と 50000 個のエッジを含めることができるため、優れた多項式時間アルゴリズムが必要です (ここでの制限時間は、すべての開始位置を解決するのに 2 秒ですが、多くのことを共有できると思います)。異なる開始位置間の情報)。

グラフは 2 部構成であるため、これはある種の頂点カバーまたはパッキングの問題に帰着できると確信していますが、これらのいずれかに関連する戦略を見つけることができません。

私は特別な場合の解決策を知っています: 辺にそれぞれn ₁とn ₂の頂点があるとしましょう。サイズmin(n ₁ , n ₂ )のマッチングがあり、小さい側のプレイヤーが開始した場合、勝利戦略が存在します。彼はマッチしたエッジをたどるだけで、自動的に勝利します。

何か案は？

jgrapht、jgraph、またはアプレットを取得してこのグラフを正しく視覚化するのに問題がありますか? このグラフ ライブラリを使用して、下の図のように視覚化できますか? たとえば、コードでは U が x で、V が Y になります。この例では、有向グラフを使用して同じことを行うデモ バージョンを使用しています。jgAdapter と jgxAdapter のどちらを使用する必要があるかわかりませんか? 現在、いずれかの空のアプレットを取得しています。

アルゴリズムの解析について勉強しています。私は現在、Network Flowアルゴリズムについて読んでいます。最小コストのNetwork Flow発見に関するアルゴリズムの適用を検討しています。bipartite matchings

• G対応するネットワーク フローを使用してみましょうG'
• になろMうperfect matchingG
• このマッチングG<sub>M</sub>にresidual graph関連付ける

Jon Kleinberg と Eva Tardos のAlgorithm Design 7.13 on page 406 から、

Theorem 7.62状態:

(7.62) M を完全一致とする。G _Mに負のコスト有向サイクル C がある場合、M は最小コストではありません

この定理は理にかなっていますが、 abipartite flow network's residual graphの aperfect matchingが実際にサイクルをどのように含むことができるかについては混乱しています。サイクルを確認できる唯一の方法は、sinkまたはsourceが関係している場合です。

ただし、 にはperfect matching、sourceそこから出るエッジは含まれず、 にsinkは入るエッジは含まれません。また、内部ノードで発生するサイクルは、 a の定義と矛盾するように見えBipartite graphます。

誰かが残差グラフでそのようなサイクルの例を提供できますか?

私は1つのマトリックスを持っていて、MATLABで以下のように二部グラフを描きました。

この場合、すべての行は2 列目の(0 と 1)別々に接続されます。しかし、2 列目の要素が1の場合にのみ接続したいです 。0 は必要ありません。MATLAB でどのように描画したり、コードを記述したりできますか?