2

これは試験準備の一部です。max-flowアルゴリズムと関係があることは知っていますが、ヒントをいただければ幸いです：

G=(V,E)無向連結グラフと、w:E->R重み関数、eエッジ、および を考えk > 0ます。新しいグラフの最小全域木に属するkように、グラフから多くてもエッジを削除できるかどうかを判断するアルゴリズムを説明してください。e

スパニング ツリーは一種の完璧なマッチングだと思います。しかし、e と適切な量の他のエッジを含む最小限にするにはどうすればよいでしょうか?

4

1 に答える 1

3

ヒント: すべてのエッジ e について、e より (厳密に) 軽いエッジで構成される e のエンドポイント間にパスが存在しない場合にのみ、e を含む最小重みのスパニング フォレストが存在します。

于 2013-07-07T18:27:13.823 に答える