如何获取图中所有满足最小割条件的边割集？

你的需求是找出图中所有大小为最小割（此处为2）的边割集，NetworkX的minimum_edge_cut仅返回单个结果，以下是两种可行的解决方案：

方法一：枚举验证法（适合小规模图） #

思路 #

1. 先计算最小割的大小k
2. 枚举所有k条边的组合，逐一验证移除这些边后图是否变为非连通
3. 对验证通过的边集去重（无向图中边的顺序不影响割集有效性）

代码实现 #

import itertools
import networkx as nx

# 构建目标图
test_graph = nx.Graph()
edges = [
    (0,1), (0,2), (0,4), (1,2), (1,3), (2,3), (2,4), (3,4),
    (3,5), (4,8), (5,6), (5,7), (5,8), (6,7), (7,9), (8,9),
    (8,10), (8,11), (9,10), (9,11), (10,11)
]
test_graph.add_edges_from(edges)

# 获取最小割的大小
min_cut_size = nx.min_edge_cut_size(test_graph)
all_min_cuts = set()

# 枚举所有min_cut_size条边的组合
for edge_comb in itertools.combinations(test_graph.edges(), min_cut_size):
    # 复制原图并移除候选边
    temp_graph = test_graph.copy()
    temp_graph.remove_edges_from(edge_comb)
    # 检查图是否非连通
    if not nx.is_connected(temp_graph):
        # 用frozenset存储边集，避免重复（如(4,8)和(8,4)视为同一条边）
        normalized_cut = frozenset(frozenset(edge) for edge in edge_comb)
        all_min_cuts.add(normalized_cut)

# 转换为可读格式输出
for idx, cut in enumerate([set(c) for c in all_min_cuts], 1):
    print(f"最小割集 {idx}: {cut}")

优缺点 #

• 优点：逻辑简单，容易理解和实现
• 缺点：当图的边数较多时，组合数会指数级增长，效率低下。比如边数为100、最小割为3时，组合数超过16万，计算量会很大。

方法二：基于s-t最小割遍历（高效通用） #

思路 #

根据图论知识，全局最小割一定是某一对节点s-t之间的最小割。因此可以：

1. 遍历所有节点对s-t
2. 用nx.all_edge_cuts获取这对节点之间所有大小为最小割的边割集
3. 收集所有割集并去重

代码实现 #

import networkx as nx
from itertools import combinations

# 构建目标图
test_graph = nx.Graph()
edges = [
    (0,1), (0,2), (0,4), (1,2), (1,3), (2,3), (2,4), (3,4),
    (3,5), (4,8), (5,6), (5,7), (5,8), (6,7), (7,9), (8,9),
    (8,10), (8,11), (9,10), (9,11), (10,11)
]
test_graph.add_edges_from(edges)

# 获取最小割的大小
min_cut_size = nx.min_edge_cut_size(test_graph)
all_min_cuts = set()

# 遍历所有不重复的节点对（避免重复计算s-t和t-s）
for u, v in combinations(test_graph.nodes(), 2):
    # 获取u-v之间所有大小为min_cut_size的边割
    for cut in nx.all_edge_cuts(test_graph, s=u, t=v, k=min_cut_size):
        # 标准化边集以去重
        normalized_cut = frozenset(frozenset(edge) for edge in cut)
        all_min_cuts.add(normalized_cut)

# 输出结果
for idx, cut in enumerate([set(c) for c in all_min_cuts], 1):
    print(f"最小割集 {idx}: {cut}")

优缺点 #

• 优点：效率远高于枚举法，适合大多数规模的图
• 缺点：需要理解图论中全局最小割与s-t最小割的关系，代码逻辑稍复杂

内容的提问来源于stack exchange，提问作者Mehdi Hamzezadeh