为什么有n个顶点的图有2^n -2个割？

Question

为什么有n个顶点的图有2^n -2个割？我搞不懂这件事。有4个顶点，我不能得到14个切割。我可以叫麦克斯。裁员12次？我遗漏了什么？

我的意思是V被分成两对非空的顶点列表-A和B。

Answer 1

一种使其合理化并枚举切割的简单方法是为每个节点分配一个二进制数字。0表示它在集合A中，1表示它在集合B中。然后简单地递增，忽略0和2^n -1的情况，留下2^n -2个剪切。因此，对于一个具有顶点P，Q，R，S的四顶点图：

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

因此，为了定义一个特定的切割，你只需要取V的一些子集，它定义了A，还有B，它是它的补集。

V的子集的个数，其中|V| =n是V的幂集的基数，2^n。然而，你必须减去两种情况，因为A不能为空，也不能等于V，因为那样B就会为空。因此，2^n - 2。

Answer 3

我认为这是相当明显的：

每个顶点既可以在集合A中，也可以在集合B中，我们有n个顶点，n个顶点上的两种可能导致2^n个顶点，其中所有顶点都在A或B中。

• 给出了2^n -2

<

• >F211>

或者把它想象成一个真实表。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个...