2 つのノード (0 と 6) があるグラフがあり、それらが接続されないように、可能な限り最小のエッジをカットする必要があります。たとえば、このグラフでは
ノード 0 と 6 であるため、カットする必要がある最小のエッジは 2-7 と 3-7 です。私の考えは、bfs を使用して両方の間の最短パスを見つけることでした。1 つ (0-2-7-6) を見つけましたが、もう 1 つ (0-3-7-6) を見つける方法がわかりません。それでも、カットするエッジをどのように選択するかわかりません。
誰かがこの問題について私にいくつかの指針を与えることができればうれしいです.
あなたが欲しいのは分セントカットです。一般的なグラフで 1 つを見つける通常の方法は、ソース 0 とシンク 6 でpush relabelのようなアルゴリズムを実行することです。これは、最大フローの計算の副産物として最小 st カットを計算します。
Karger のアルゴリズムは最小カットを見つけます。つまり、s と t およびカットを最小化します。s と t は固定されているため、Karger のものは適切ではありません。関節頂点は、削除するとグラフが切断される頂点です。頂点ではなくエッジを削除することに関心があります。
この問題は、グラフ内のアーティキュレーション ノードを見つける問題と非常に似ているようです。アーティキュレーション ポイントまたは二重接続コンポーネントの技術的な定義は、ノードを削除するとグラフが 2 つに分割されるノードです。
グラフからの連結ノードの発見は、大部分が解決された問題であり、詳細については、http: //en.wikipedia.org/wiki/Biconnected_componentを参照してください。
一般的に、このような問題にアプローチする方法は、次のようなものになるようです。
1. Find all articulation points
2. Do a bfs from each node and determine articulation points along the path
3. Split graph at the articulation point, choosing the side with minimal edges
4. Continue until the two nodes are not connected
上記の例では、7 が唯一の関節点であり、7 と 0-4 グラフの間には 2 つのエッジしかなく、7 と 5,6,8 の間には 3 つのエッジしかないため、7、2、および 3 の間のエッジを切り取ります。グラフ。
これを行うためのより確立されたアルゴリズムがあります（読んでください：私が思いつきませんでした）、n ^ 2時間で問題を解決できるKargerのアルゴリズムと呼ばれます。
このアルゴリズムは、ノードが 2 つになるまで隣接するノードを効果的に結合し、2 つのノード間に残っているエッジの数をカウントすることによって機能します。エッジの数は、グラフを分割するために必要なカットの最小数です。
問題に Karger のアルゴリズムを実装する方法には、分割する 2 つのノードに常にノードを結合する必要があるという警告が必要です。さらに、カットする必要がある元のエッジに戻ることができるようにするには、エッジが最初に属していたノードへの参照を保持する必要があります。
Karger のアルゴリズムの優れた視覚化がここにあります: http://en.wikipedia.org/wiki/Karger%27s_algorithm