私は2つのノード（0と6）を持っているグラフを持っており、可能な限り最小限のエッジをカットして接続していません。このグラフIを切断する必要があり、ノード0と6つの以上のエッジなのでJava - グラフのクリティカルリンク
、例えば2-7及び3-7です。 私の考えは、bfsを使って両方の最短経路を見つけることでした。私は1つ（0-2-7-6）を見つけましたが、他のもの（0-3-7-6）を見つける方法はわかりません。それでも私はカットするエッジをどのように選ぶか分かりません。
誰かがこの問題について私にいくつかの指摘を与えることができたらうれしいです。
この問題は、グラフ内のアーティキュレーションノードを見つけることと非常によく似ています。アーティキュレーションポイント、またはバイコネクテッドコンポーネントの技術的定義は、その除去によってグラフが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との間の唯一の二つのエッジが存在するので、あなたは7,2及び3の間にエッジをスニップなりますグラフと7と5,6,8グラフの間の3つのエッジ。
n^2の時間ではあるが問題を解決できるKargerのアルゴリズムと呼ばれるこれを実行するためのより確立されたアルゴリズムがあります（読んでいないことを読んでください）。
このアルゴリズムは、2つのノードだけが存在するまで隣接するノードを効果的に結合し、次に2つのノード間に残っているエッジの数を数えることによって機能します。エッジの数は、グラフを分割するために必要な最小カット数です。
あなたの問題でKargerのアルゴリズムを実装する方法は、分割したい2つのノードに常にノードを参加させる必要があるという警告が必要です。さらに、元のエッジに戻ることができるようにするには、カットする必要があります。エッジが最初に属していたノードを参照する必要があります。
ここカーガーのアルゴリズムの偉大な可視化があります：http://en.wikipedia.org/wiki/Karger%27s_algorithm
しかし、ノード9を追加してノード1とノード6に接続すると、アーティキュレーションポイントはノード6になります。つまり、ノード6（4つのエッジ）をつなぐすべてのエッジをカットしなければならないのでしょうか？私は3つのエッジであるエッジ2-7,3-7と1-9（または9-6）をカットする必要があるためです。 – user2452870
まあまあです。ノード9を追加してそれをノード1と6に接続した場合、その時点でどのノードを削除してもグラフが接続されたままであるため、連結点はありません。アーティキュレーションペアを探すアートポイントを2プライで検索する必要があります。そのようなペアの1つは7と9でなければならず、上記の方法は依然として有効です。 –
しかし、これらのアーティキュレーションペアはどのようにして見つけられますか？どのようにすればいいのか、アートポイントアルゴリズムでどのような変更が必要なのか説明できますか？ – user2452870
あなたが欲しい何が分S-トンカットです。一般的なグラフで1つを見つける一般的な方法は、ソース0とシンク6を持つpush relabelのようなアルゴリズムを実行することです。これは、最大フローを計算する副産物としてmin s-t cutを計算します。 Kargerのアルゴリズムは、最小カットを見つける、すなわち、sおよびtおよびカットを最小化する。 sとtはあなたのために固定されているので、Karger'sは適切ではありません。アーティキュレーション頂点は頂点であり、その削除によってグラフが切断されます。頂点ではなくエッジを削除することに興味があります。
これは「最小カット」問題と呼ばれます。それは最短経路よりも最大流量に密接に関連している。 –