問題タブ [bipartite]

有向非巡回グラフで最小パス カバーを計算するための効率的なアルゴリズムが存在するかどうかを知りたいです。最小の「パス カバー」を「頂点ディスジョイント パス カバー」と混同しないでください。後者については、対応する二部グラフの最大マッチングを使用する効率的なアルゴリズムを知っています。ただし、これは頂点が素の場合にのみ適用されます。各頂点を複数回訪れることができる場合、同じアルゴリズムを緩和してパス カバーの答えを取得できますか?

似たような話題がたくさんあることに気づきました。しかし、それらのほとんどは、私の場合にいくつかの疑問を残しました. 私がやりたいのは、完全な一致を見つけることです（または、もちろん完全な一致がない場合はできるだけ完全に近いものを見つけます）。次に、これらすべての一致から、n個の頂点のうちk個を一致させることができます（kは可能な限り最高です） ）、可能な限り最大の総重量を選択したい. したがって、私が言っていることは、優先順位に従うことです。

1. できるだけ多くの頂点を一致させる
2. ほとんどの場合、（重み付けされていない）最大一致は明確であるため、エッジの重みの合計が最大のものを選択したいと思います。同じ重さのものが複数ある場合は、どれを選択しても問題ありません。

Ford-Fulkerson アルゴリズムについて聞いたことがあります。それは私が説明した方法で機能していますか、それとも他のアルゴリズムが必要ですか?

Skiena's Design on Algorithms.I の問題で立ち往生しています。私の解決策が正しいかどうかわかりません。

5-18。ムービーのセット M_1、M_2、..M_k を考えてみましょう。顧客のセットがあり、それぞれが今週末に見たい 2 つの映画を示しています。映画は土曜日の夜と日曜日の夜に上映されます。複数の映画が同時に上映される場合があります。どの映画を土曜日に放映し、どの映画を日曜日に放映するかを決定して、すべての顧客が希望する 2 つの映画を視聴できるようにする必要があります。各映画が最大 1 回上映されるスケジュールはありますか? そのようなスケジュールが存在する場合、そのようなスケジュールを見つけるための効率的なアルゴリズムを設計してください。

解決策: 映画用のセット {M1,M2..Mk} と、顧客用のセット {C1,C2,..Cp} があります。C1 が見たいエッジ 2 の映画に接続します。好きな映画2本を同じ夜に見せられなかった(好きな映画2本を色違いで色付け)など、二部グラフになっていないか検証したい.もしそうなら、私たちはすべての映画を土曜日に1番目の色で、日曜日に2番目の色で色付けして表示します.問題は解決しました.しかし、そうでない場合はどうすればよいですか?

以下は、最大二部マッチング問題です: http://www.spoj.com/problems/QUEST4/ フォーラムを通じて、この問題を最小頂点カバー問題に変換できることを知りました。二部マッチング。しかし、問題がどのようにして最小頂点カバーに変換されたのかわかりません。これを理解するのを手伝ってください。