重複の可能性:
アルゴリズム: G = (V,E) の場合、エッジのセット (e は E に属する) がグラフの有効なカット セットであるかどうかを判断する方法
グラフ G = (V,E) のエッジの部分集合 S は、それがグラフの有効なカットセットであるかどうかをどのように確認できますか? 注: カットとは、グラフの頂点を 2 つのばらばらのサブセットに分割することです。したがって、カットのカットセットは、端点がパーティションの異なるサブセットにあるエッジのセットです。この問題のアルゴリズムを見つけることに興味があります
つまり、S のエッジに異なるラベルの端点があり、E - S のエッジに同じラベルの端点があるようなラベル付け V -> {0, 1} が存在するかどうかを判断したいとします。このようなラベリングが存在する場合、常に次の手順で作成できます。
G をトラバースします (深さ優先と言いますが、実際には問題ではありません)。トラバーサル ルートに任意のラベルを付けます。ラベル付きノード u から他のノード v へのエッジ e を処理するたびに、e が S にない場合は u のラベル、S にある場合は u のラベルの反対で v にラベルを付けます。v が既に別のラベルを持っている場合、S はカットセットではありません。それ以外の場合、トラバーサルが問題なく終了した場合、S はカットセットです。