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

Question

为什么具有n个顶点的图形具有2 ^ n -2个切割？我无法想出这个.有4个顶点,我只能得到14个削减.我可以得到最多.削减？我错过了什么？

通过cut,我的意思是V被分成2对非空顶点列表-A和B.

Answer 1

合理化它以及枚举切割的一种简单方法是为每个节点分配一个二进制数字.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

你的最后一句话是这样的 - 剪切只是顶点的一个分区,分为两组,两组都不是空的.

因此,要定义特定的切割,您只需要采用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中的onces
• 这给了我们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 ...