6

誰かがこの問題で私を助けてくれますか? ソリューションは明らかにネットワーク フローを使用していますが、私はネットワーク フローにあまり詳しくありません。ネットワークフローはこれをどのように解決するのに役立ちますか?

カニは 2 種類の頂点を持つ無向グラフです: 1 つの頭と K 個の足、および頭を各脚に接続する厳密に K 個の辺 (1 <= K <= T、ここで T は与えられます)。

無向グラフが与えられた場合、それぞれがクラブであるいくつかの頂点が素なサブグラフを見つける必要があります。目標は、カニがカバーする頂点の総数が最大になるような方法でカニを選択することです。

注: 2 つのグラフは、共通の頂点を持たない場合、頂点分離です。

元 。入力

8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6
4

3 に答える 3

1

上記の問題を頂点カバー アプローチで解くと指数関数的な tim アルゴリズムになりますが、これは Ford Fulkerson アルゴリズムを使用してフローを最大化することで解決できます。上記の問題は Ford Fulkerson を使用して解決できます。

  1. source(0) から容量 = t のグラフのすべてのノードへのパスを作成します。
  2. すべてのノードから target(1) へのパスを容量 = 1 で作成します。
  3. Ford Fulkerson を使用して、上記の修正されたグラフの最大フローを見つけます。

指定されたグラフで最大フローを見つけるための Ford Fulkerson アルゴリズム

  1. グラフでソースからターゲットへのパスを見つけます。
  2. パスに沿った最小フローを見つけます。
  3. 上記で計算された最小フローによって、パスに沿ったすべてのエッジのフローを増やします
  4. パスの最小フローを保存します。

オーグメンテーション パスが使用できなくなるまで、上記の 4 つの手順を繰り返します。

Ford Fulkerson アルゴリズムの説明

可能なパスを 1 つ選択し、容量が最小のエッジを特定します。この番号を記録します。そのパスの各番号からこの番号を引きます。これは、パスの長さの各アークの新しい容量です。別のルートを選択し、手順 1 をもう一度繰り返して最小容量を記録します。すべての可能なパスが使い果たされるまで繰り返します。すべてのルートの最小容量を追加します。これは、ネットワークの最小容量です。

参照

http://anandtechblog.blogspot.in/search/label/Ford%20Fulkerson%20アルゴリズム

于 2013-07-03T05:30:23.163 に答える