2

私はこのような問題を抱えています：

2部グラフが表示されます。例えば

A1 B1
A2 B2
A3 B3
A4

そして、これが隣接リストの表現です（グラフが双方向であると仮定します）

B1 -> A2, A3
B2 -> A2, A3, A4
B3 -> A1

最終的な結果として、左側（As）のすべてのノードに正確に1つの入力エッジがあり、同時に、個々のBノードから出る必要のあるエッジの最大数を最小限に抑える必要があります。この場合、答えは次のようになります。

B3 can connect to A1
B2 can connect to A2, A4
B1 can connect to A3

したがって、ここでは、単一のBsノードから出る必要のあるエッジの最大数は2です。すべてのAsをカバーすることはできません。同時に、Asをカバーするために2つのエッジが出ていないBノードがあります。

もう一つの例：

A1 B1
A2 B2
A3 B3
A4 B4

B1 -> A1, A2, A3
B2 -> A1, A2, A3, A4
B3 -> A1, A2, A3
B4 -> A1, A2, A3

この場合、答えは次のようになります。

B1 can connect to A1
B2 can connect to A4
B3 can connect to A3
B2 can connect to A2

このようにして、すべてのAsを1回だけカバーすると同時に、個々のBから出る必要のあるエッジの最大数を最小限に抑えます。したがって、ここでは、単一のBsノードから出る必要のあるエッジの最大数は1です。

もう一つの例：

A1 B1
A2 B2
A3 B3
A4
A5
A6

B1 -> A6
B2 -> A1, A2, A3, A4, A5
B3 ->

この場合、答えは5になります。つまり、単一のBから出る必要のあるエッジの最大数は5です。それより少なくすることはできません。

私は基本的なフォードフルカーソンアルゴリズムを実装しました。これもネットワークフローであることは知っていますが、それにどのように関連付けるかはわかりません。

誰かがグラフについてのヒントを与えることができれば素晴らしいでしょう。

ありがとう

4

2 に答える 2

3

最適なソリューションを見つける-すべてのBが最大で1つのアウトエッジ（存在する場合）を持つ場合、簡単です：

  • グラフにソースとシンクを追加します。ソースは、Bのリストのすべての頂点に対して容量1のアウトエッジを持ちます。
  • すべての(B,A)エッジの容量は1になります。
  • すべてのAは、シンクに対して容量1のアウトエッジを持ちます。
  • ここで、フローアルゴリズムを実行すると、A内の頂点の最大数が生成されます。これは、1つの出力エッジのみを持つ各Bでカバーできます（最適なソリューションが存在する場合）。

編集：

さて、上記のアイデアに基づいて、単一のBからAまでのエッジの最大数を最小化しようとしているので（以前考えていたように、エッジの総数ではありません）、最適なソリューションは簡単です。

while there is no coverage:
   set capacity(source,b_k) = increase_size() (for each b_k in B)
   run max flow algorithm on the graph suggested above
return last flow found

複雑さはO(E*V*#iterations)（この問題f <= Vでは、したがって、フォード・ファルカーソンの場合の複雑さO(EV)）、#iterations求める最小最大数で線形に実行するか、指数関数的増加を使用して、範囲を二分探索することができます（Evkeny Kluevによって提案されています）。この番号のログに。 2部グラフであるため
、E=O(V)O(V^2*log(V))

于 2012-10-02T09:31:57.413 に答える
2

すべてのAを容量のエッジを持つ1つの共通シンクノードに接続します1.すべてのBを可変容量のエッジを持つ1つの共通ソースノードに接続しますC。

このグラフで最大のネットワークフローを見つけますC。すべてのAがカバーされていない場合は増加し、そうでない場合は減少します。Cこれは、二分探索を使用するための最適な値を見つけることを意味します。

于 2012-10-02T09:39:41.147 に答える