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

Question

为什么有 n 个顶点的图有 2^n -2 次切割？我无法弄清楚这一点。有 4 个顶点，我不能得到 14 次切割。我可以得到最大。 12刀？我错过了什么？

通过 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。