图中的最小割 — min_cut • igraph 网络分析库

min_cut() 计算图中两个顶点之间的最小 st-割（如果给定了 source 和 target 参数），或者计算图的最小割（如果 source 和 target 均为 NULL）。

用法

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

参数

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

值

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

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

详细信息

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

图的最小割是移除将图分成（至少）两个组件所需的最小边总权重。（这意味着在有向图中使图不强连通。）

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

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

参考文献

M. Stoer and F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997.

参见

其他流相关函数：dominator_tree(), edge_connectivity(), is_min_separator(), is_separator(), max_flow(), min_separators(), min_st_separators(), st_cuts(), st_min_cuts(), vertex_connectivity()

示例

g <- make_ring(100)
min_cut(g, capacity = rep(1, vcount(g)))
#> [1] 2
min_cut(g, value.only = FALSE, capacity = rep(1, vcount(g)))
#> $value
#> [1] 2
#> 
#> $cut
#> + 2/100 edges from 1d310f7:
#> [1] 1--2 2--3
#> 
#> $partition1
#> + 1/100 vertex, from 1d310f7:
#> [1] 2
#> 
#> $partition2
#> + 99/100 vertices, from 1d310f7:
#>  [1]   1   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
#> [20]  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39
#> [39]  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58
#> [58]  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77
#> [77]  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96
#> [96]  97  98  99 100
#> 

g2 <- make_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)
#> $value
#> [1] 1
#> 
#> $cut
#> + 1/7 edge from 0091ab1:
#> [1] 2->3
#> 
#> $partition1
#> + 1/6 vertex, from 0091ab1:
#> [1] 2
#> 
#> $partition2
#> + 5/6 vertices, from 0091ab1:
#> [1] 1 3 4 5 6
#>