graph - n個の頂点を持つグラフに2^n -2カットがあるのはなぜですか？

Question

n個の頂点を持つグラフに2^n -2カットがあるのはなぜですか？私はこれを理解することはできません。4つの頂点があるので、14のカットを取得できません。私は最大を得ることができます。12カット？私は何が欠けていますか？

カットとは、Vが空でない頂点リストの2つのペア（AとB）に分割されることを意味します。

Answer 1

それを合理化し、カットを列挙する簡単な方法は、各ノードに2進数を割り当てることです。0はセットAにあり、1はセットBにあることを示します。次に、0と2 ^ n -1の場合を無視して単純にインクリメントし、2 ^n-2カットを残します。したがって、頂点P、Q、R、Sを持つ4頂点グラフの場合：

PQRS
0000 A : { P,Q,R,S } B : {} // ignore, B is empty
0001 A : { P,Q,R } B : { S }
0010 A : { P,Q,S } B : { R }
0011 A : { P,Q } B : { R,S }
0100 A : { P,R,S } B : { Q }
0101 A : { P,R } B : { Q,S }
0110 A : { P,S } B : { Q,R }
0111 A : { P } B : { Q,R,S }
1000 A : { Q,R,S } B : { P }
1001 A : { Q,R }, B : { P,S } 
1010 A : { Q,S } B : { P,R }
1011 A : { Q } B : { P,R,S }
1100 A : { R,S } B : { P,Q }
1101 A : { R } B : { P,Q,S }
1110 A : { S } B : { P,Q,R }
1111 A : {} B : { P,Q,R,S } // ignore, A empty

それはあなたに14、2^4-2を残します。

Answer 2

あなたの最後の文はそれを言います-カットは単に頂点セットを2つのセットに分割したものであり、どちらも空ではありません。

したがって、特定のカットを定義するには、Vのサブセットを取得し、それがAとその補集合であるBを定義します。

Vのサブセットの数。ここで|V| = nは、Vのべき集合2^nのカーディナリティです。ただし、Aを空にすることも、Vと等しくすることもできないため、2つのケースを減算する必要があります。これは、Bが空になるためです。したがって、2^n-2。

Answer 3

これは私が思うにかなり明白です：

• 各頂点は、セットAまたはセットBのいずれかになります。
• n個の頂点があります
• n個の頂点で2つの可能性があり、2^n個の順列になります
• すべての頂点がAまたはBにある1回を削除します
• それは私たちに2^n-2を与えます

または、それを真理値表と考えてください。a頂点がセットAにあるbことを意味し、セットBにあることを意味します。

Vertices
1 2 3 4
a a a a
a a a b
a a b a
a a b b
a b a a
a b a b
a b b a
a b b b
b a a a
b a a b
b a b a
b a b b
b b a a
b b a b
b b b a
b b b b

a a a aとb b b bセットを削除すると、必要な14が残ります...

Answer 4

カットは、頂点が1つのセットAまたはセットBのいずれかにあることを意味します。

両方のセットが空でない必要があるため、以下が唯一の可能性です。

1、（n-1）==>これは、セットAに1つの頂点があり、セットBに（n-1）があることを意味します。n=nC1から1つを選択する方法はありません。

2、（n-2）==>セットAの2つの頂点とセットBの（n-2）。n=nC2から2つを選択する方法はありません。

3、（n-3）==>セットAの3つの頂点とセットBの（n-3）。n=nC3から3つを選択する方法はありません。

（n-1）、1 ==>（n-1）セットAの頂点とセットBの1。n=nCn-1からn-1を選択する方法はありません。

したがって、カットの総数は次のとおりです。

nC1 + nC2 + nC3 + ..... nCn-1 = 2^(n)-2

Answer 5

最初は、4つの頂点（正方形）に対してカットがいくつあるかを数えながら、同様の問題に直面しました。

正方形の対角線でカットできることを忘れないでください。これはあなたに行方不明の2を与えるでしょう。