algorithm - グラフでカットセットを見つける

Question

V = {a、b、c}およびE = {ab、bc、ca}の三角形グラフGを考えてみます。エッジサブセットS={ab、bc}が削除されると、エッジacが残ります。私の質問はSが有効なカットセットです（Gを2つの頂点サブセット{b}と{a、c}に分割します）

注：カットは、グラフの頂点を2つの互いに素なサブセットに分割したものです。カットのカットセットは、エンドポイントがパーティションのさまざまなサブセットにあるエッジのセットです。

Answer 1

はい。

{ab、bc}はカットを誘発するため、カットセットです。{ab、bc}によって引き起こされるカットは（{a、c}、{b}）です。

定義を明確にします：

• カットは、グラフの頂点のパーティションです。たとえば、（{a、c}、{b}）はカットです。これは、グラフの各頂点が2つのセットのうちの1つに正確に属しているためです。
• カットのカットセット（S、T）は、次のエッジのセットです。SのuとTのv}。たとえば、（{a、c}、{b}）のカットセットは{ab、bc}です。
• エッジのセットEは、Eがそのカットセットであるカットが存在する場合にのみカットセットです。あなたの例では、頂点cがSまたはTのどちらに属しているかを判断できないため、セット{ab}はカットセットではありません。セット{ab、bc、ca}は、簡単に証明できるため、カットセットではありません。{ab、bc、ca}がそのカットセットであるカットがないという矛盾によって。