0

無向加重(正の加重)グラフを切断するための最小コストはいくらですか.

つまり、削除によってグラフが切断され、そのコストが最小化されるエッジを見つける必要があります。

私は次のアイデアを持っています...

1. グラフのすべてのブリッジを見つけます。その場合、最小重量のブリッジ エッジが ans になります。

2.ブリッジがない場合は、すべてのノードがサイクルになっていることを意味します(よくわかりません)。次に、重みに従ってエッジを並べ替え、2 つの最小エッジ重みの合計が ans になります。

グラフには自己ループはありません。

このアルゴリズムは正しいですか?

4

1 に答える 1

0

この質問は、グラフの「最小カット」の研究によって回答されたのと同じ質問のようです。グラフ理論の観点からなぜそれが機能するのかについて詳しく知るには、ここここを読んでください。リンクには疑似コードも含まれています。

提案されたアルゴリズムに関して、グラフ内のブリッジを見つけるのは難しいかもしれません..ブリッジの存在を確認するには、両方のエンドポイントとそれらのローカル構造を検査する必要があります..おそらくエッジ縮小を使用すると、実装が簡単になります.

于 2012-10-02T19:06:13.513 に答える