考虑一个v={a，b，c}和e={ab，bc，ca}的三角图g。如果边子集s={ab，bc}被移除，那么我们得到边ac left。我的问题是s是一个有效的割集（它将g划分为两个顶点子集{b}和{a，c}）
注：割是将图的顶点划分为两个不相交的子集切割的切割集是其端点位于分区的不同子集中的边集。
最佳答案
对。
{ab，bc}是一个割集，因为它诱导一个割集。由{a b，b c}引起的切割是（{a，c}，{b}）。
我将澄清这些定义：
割是图顶点的一个划分。例如，（{a，c}，{b}）是一个割集，因为图中的每个顶点恰好属于这两个集合中的一个。
切割集（S，T）是以下边的集合：{u v | u in S和v in T}例如，{a，c}，{b}的割集是{ab，bc}。
一个集合E是一个割集，当且仅当存在E的一个割集是它的割集时。在您的示例中，集合{ab}不是割集，因为您无法确定顶点c是否属于s或t。集合{ab，bc，c a}不是割集，因为您可以很容易地通过矛盾证明不存在{ab，bc，ca}是其割集的割集。