为什么有n个顶点的图有2^n-2种割?我想不通这个问题。对于4个顶点,我只能得到最多12种割,而无法得到14种。我错过了什么吗?
通过“割”,我指的是将V分成两个非空顶点列表A和B的方式。
通过“割”,我指的是将V分成两个非空顶点列表A和B的方式。
一种简单的合理化方法,以及列举割的方式,是为每个节点分配一个二进制数字。 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。
你最后一句话说的没错 - 割是将顶点集划分为两个集合,两个集合都不为空。
因此,要定义一个特定的割,只需取V的某个子集,这定义了A和B,它的补集。
当|V|=n时,V的子集数是幂集V的基数2^n。但是您必须减去两种情况,因为A既不能是空集,也不能等于V,否则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个...
一次切割意味着一个顶点将被分到集合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
起初,我在计算4个顶点(正方形)有多少切口时遇到了类似的问题。
请记住,您可以通过正方形的对角线进行切割。这将为您提供缺失的2个切口。