使用Python查找图中两分区割边的方法及NetworkX优化、自动平衡分区与最小割实现问询

我来逐个拆解你的问题：

1. 你的割边查找方法是否正确？ #

是的，你的方法完全正确。你要找的是两个预定义分组之间的跨组割边，通过遍历所有边并检查端点是否分属不同分组，这个逻辑完全匹配这类割边的定义。

小提醒：图论里还有另一种“割边（Bridge）”的概念——指去掉后会增加图连通分量数的边，和你这里的跨分组割边不是同一回事。你的代码针对的是前者，逻辑没有问题。

2. NetworkX有没有更高效的内置函数？ #

当然有！NetworkX提供了nx.cut_edges()函数，专门用来计算给定节点子集与补集之间的割边，比手动遍历更简洁高效（大图场景下内置函数做了优化，性能更优）。

用你的代码举例，只需要替换手动遍历的部分：

import networkx as nx
G = nx.Graph()
edges = [ (1,2),(1,3),(2,3), (4,5),(5,6),(4,6), (7,8),(8,9),(9,7), (10,11), (3,4),(6,7),(9,10) ]
G.add_edges_from(edges)
group1 = {1,2,3,4,5}

# 直接用内置函数获取割边
cuts = list(nx.cut_edges(G, group1))
print(cuts)

这个函数会自动识别group1和它的补集（即你的group2）之间的所有跨组边，省去了手动判断的冗余代码。

3. 如何自动实现平衡分区并找到最小割？ #

如果你不需要手动定义分组，而是想找到割边数最少（最小割）且两个分区大小尽可能平衡的划分，可以分两种场景处理：

场景1：优先找全局最小割（不强制平衡） #

NetworkX的nx.stoer_wagner()算法可以计算无向图的全局最小割，它会返回最小割的边数，以及其中一个分区的节点集合（另一个分区是整个图节点的补集）。

示例代码：

min_cut_size, partition = nx.stoer_wagner(G)
group_a = partition
group_b = set(G.nodes()) - group_a

print(f"最小割边数: {min_cut_size}")
print(f"分区1: {sorted(group_a)}")
print(f"分区2: {sorted(group_b)}")
# 对应的割边列表
cut_edges = list(nx.cut_edges(G, group_a))
print(f"割边列表: {cut_edges}")

注意：这个算法只保证割边数最少，得到的分区不一定是平衡的。

场景2：找平衡的最小割（兼顾割边数和分区大小） #

如果需要分区大小尽可能接近，同时割边数尽可能少，可以尝试谱聚类的方法。它通过图的拉普拉斯矩阵特征向量来划分节点，能得到比较平衡的分区，且割边数接近最小割。

示例代码：

import numpy as np
from sklearn.cluster import KMeans

# 生成图的归一化拉普拉斯矩阵
laplacian = nx.normalized_laplacian_matrix(G).toarray()
# 计算特征值与特征向量
eigenvalues, eigenvectors = np.linalg.eigh(laplacian)
# 取最小的两个特征向量（谱聚类核心）
top_two_evecs = eigenvectors[:, :2]
# 用KMeans分成2个簇
kmeans = KMeans(n_clusters=2, random_state=42)
cluster_labels = kmeans.fit_predict(top_two_evecs)

# 转换为分区集合
group1 = {node for idx, node in enumerate(G.nodes()) if cluster_labels[idx] == 0}
group2 = set(G.nodes()) - group1

print(f"平衡分区1: {sorted(group1)}")
print(f"平衡分区2: {sorted(group2)}")
print(f"割边数: {len(list(nx.cut_edges(G, group1)))}")
print(f"割边列表: {list(nx.cut_edges(G, group1))}")

这种方法在你的示例图上，会得到大小接近的分区，同时割边数接近全局最小割。

内容的提问来源于stack exchange，提问作者Joe root