在图形中找到一个割集

| 考虑三角图G，其中V = {a，b，c}并且E = {ab，bc，ca}。如果边缘子集S = {ab，bc}被去除，那么我们得到边缘ac。我的问题是S是有效的割集（它将G划分为两个顶点子集{b}和{a，c}） 注意：割是图的顶点划分为两个不相交的子集的部分。切口的切口集是端点在分区的不同子集中的一组边。     
2019-12-31 2 条评论
分享

没有找到相关结果

    已邀请:

    届甸衬丝蚕

    是。 {ab，bc}是一个割集，因为它引起割伤。由{ab，bc}引起的割是（{a，c}，{b}）。 我将澄清定义： 割是图顶点的分区。例如，（{a，c}，{b}）是一个割，因为图中的每个顶点恰好属于这两个集合之一。 切口（S，T）的切口集是以下边集： S中的u和T中的v}。例如，（{a，c}，{b}）的割集为{ab，bc}。 当且仅当存在一个以E为割线集的割线时，边集E才是割线集。在您的示例中，集合{ab}不是割集，因为您无法确定顶点c是属于S还是T。集合{ab，bc，ca}不是割集，因为您可以轻松地矛盾地证明，{ab，bc，ca}是其割据集的割据。     
    2019-12-31 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.053518056869507