7

Given a undirected graph G=(V,E), each edge is associated with a non-negative value.

How to find the maximum number of vertex-disjoint paths from s to t on the graph G, with a constraint that the sum of paths length is not greater than a predefined value T.

4

2 に答える 2

5

頂点に素なパスの問題をエッジに素なパスの問題に変換することから始めることができます。詳細については、他の質問に対するこの回答を参照してください。

これで、このグラフで最小コスト フロー問題を解いて、最​​小のパス長の合計を持つ互いに素なパスをいくつでも見つけることができます。これを行い、各エッジに 1 に等しいフロー キャパシティを割り当て、必要なパス数に等しいフローで s と t の間の最小コスト フローを検索します。

パスの最大数を見つけるには、次の手順のいずれかによって決定されるパスの初期数から始めて、バイナリ検索の各ステップに最小コスト フロー手順を適用します。

  1. パスの最大数が大きくなると予想される場合は、このグラフの最大フローの問題を解きます。
  2. パスの最大数が少ないと予想される場合は、片側二分探索を使用します (各ステップで最小コスト フロー手順も使用します)。
于 2012-08-12T09:59:59.013 に答える
2

頂点分離パスの数にのみ関心があるため、メンガーの定理を使用できます(証明については、こちらを参照してください)。次のように述べています。

G を有限無向グラフとし、x と y を 2 つの非隣接頂点とする。次に、定理は、x と y の最小頂点カットのサイズ (削除によって x と y が切断される頂点の最小数) は、x から y への対の頂点に依存しないパスの最大数に等しいと述べています。

しかし、これは、パスの長さの合計が事前定義された値 T を超えないという制約を満たしません。

そのためには、ここに示されている制限された長さのパスにメンガーの定理のバージョンを使用する必要があります: http://www.math.elte.hu/~lovasz/scans/mengerian.pdf

于 2012-07-12T09:52:32.607 に答える