14

为什么具有 n 个顶点的图有 2^n -2 个割？我想不通这个。有 4 个顶点，我不能得到 14 次切割。我可以得到最大值。12刀？我错过了什么？

通过 cut ，我的意思是 V 分为 2 对非空顶点列表 - A 和 B。

4

5 回答 5

22

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

于 2013-02-21T15:01:48.193 回答
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 aandb b b b集合，我们就剩下所需的 14 ......

于 2013-02-21T15:00:43.603 回答
6

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

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

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

于 2013-02-21T14:52:28.523 回答
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
于 2014-11-02T18:19:32.130 回答
0

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

请记住，您可以按正方形的对角线切割。这将为您提供缺少的 2。

于 2016-04-07T02:26:16.227 回答