R igraph 手册页

min_cut {igraph}

R 文档

图中的最小割

描述

min_cut 计算图中两个顶点之间的最小 st 割（如果给定 source 和 target 参数）或图的最小割（如果 source 和 target 都为 NULL）。

用法

min_cut(
  graph,
  source = NULL,
  target = NULL,
  capacity = NULL,
  value.only = TRUE
)

参数

图	输入图。
来源	源顶点的 ID。
目标	目标顶点的 ID（有时也称为汇点）。
capacity	给出边容量的向量。 如果此值为 NULL（默认值），则使用 capacity 边属性。
value.only	逻辑标量，如果为 TRUE，则仅返回最小割值；如果为 FALSE，则还返回割中的边和两个（或更多）分区。

详细信息

source 和 target 之间的最小 st 割是消除从 source 到 target 的所有路径所需的最小总边权重。

图的最小割是使图分离成（至少）两个组件所需的最小总边权重。（即在有向情况下使图不是强连通的。）

图中两个顶点之间的最大流与最小 st 割相同，因此 max_flow 和 min_cut 本质上计算的是相同的值，唯一的区别是 min_cut 可以在不给出 source 和 target 参数的情况下调用，然后计算所有可能的最小割的最小值。

对于无向图，使用 Stoer-Wagner 算法（参见下面的参考）来计算最小割。

值

对于 min_cut，如果 value.only = FALSE，则为数值常数，即最小割的值。 在这种情况下，是一个具有以下组件的命名列表

value	数值标量，割值。
cut	数值向量，割中的边。
partition1	删除割边后，第一个分区中的顶点。 请注意，这些顶点实际上可能位于不同的组件中（删除割边后），因为该图可能会分解成两个以上的组件。
partition2	删除割边后，第二个分区中的顶点。 请注意，这些顶点实际上可能位于不同的组件中（删除割边后），因为该图可能会分解成两个以上的组件。

参考

M. Stoer 和 F. Wagner：一种简单的最小割算法，Journal of the ACM, 44 585-591, 1997.

参见

max_flow 解决相关的最大流问题, distances, edge_connectivity, vertex_connectivity

示例

g <- make_ring(100)
min_cut(g, capacity=rep(1,vcount(g)))
min_cut(g, value.only=FALSE, capacity=rep(1,vcount(g)))

g2 <- graph( c(1,2,2,3,3,4, 1,6,6,5,5,4, 4,1) )
E(g2)$capacity <- c(3,1,2, 10,1,3, 2)
min_cut(g2, value.only=FALSE)

---