顶点切割和边切割之间的关系

Question

一般来说，图的最小顶点割和最小边割之间有什么关系吗？

我在一个情况下，我已经计算了一个图的最小边割。现在我想找出同一个图的最小顶点割，我想知道我是否可以通过简单地从最小边割计算顶点割来获得一个好的估计。也就是说，我将简单地找到顶点的子集，使它们覆盖边切割中的所有边。

然而，我不确定这种方法是否真的会产生最小顶点切割的良好估计，因此出现了这个问题。

Answer 1

是。顶点割的基数是K(G)小于或等于边割的基数。