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

Question

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

graph

14

为什么有n个顶点的图有2^n-2种割？我想不通这个问题。对于4个顶点，我只能得到最多12种割，而无法得到14种。我错过了什么吗？

通过“割”，我指的是将V分成两个非空顶点列表A和B的方式。

- Achow

5个回答

6

你最后一句话说的没错 - 割是将顶点集划分为两个集合，两个集合都不为空。

因此，要定义一个特定的割，只需取V的某个子集，这定义了A和B，它的补集。

当|V|=n时，V的子集数是幂集V的基数2^n。但是您必须减去两种情况，因为A既不能是空集，也不能等于V，否则B将为空。因此2^n-2。

- Andrew Mao

谢谢。是的，我理解了其中的概率部分，我特别想知道如何在4个顶点图中获得14个切割。 - Achow

6

这个很显然，我想：

每个顶点都可以在集合A或集合B中
我们有n个顶点
n个顶点有两种可能性可以组成2^n个排列
去掉所有顶点都在A或B中的情况
这样就得到了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个...

- fgysin

1

一次切割意味着一个顶点将被分到集合A或集合B中。

由于两个集合都必须非空，因此以下是唯一的可能性。

1、(n-1) ==> 这意味着在集合A中有1个顶点，在集合B中有(n-1)个顶点。选择n个中的1个的方式数为nC1。

2、(n-2) ==> 在集合A中有2个顶点，在集合B中有(n-2)个顶点。选择n个中的2个的方式数为nC2。

3、(n-3) ==> 在集合A中有3个顶点，在集合B中有(n-3)个顶点。选择n个中的3个的方式数为nC3。

(n-1), 1 ==> 在集合A中有(n-1)个顶点，在集合B中有1个顶点。选择n个中的n-1个的方式数为nCn-1。

因此，总切割次数为：

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

- Sumit Trehan

0

起初，我在计算4个顶点（正方形）有多少切口时遇到了类似的问题。

请记住，您可以通过正方形的对角线进行切割。这将为您提供缺失的2个切口。

- user3618363

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- FatalError · Accepted Answer

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