如何将NetworkX构建的图拆分为最多4个连通子图的所有组合

要解决将图拆分为2、3、4个连通子图的所有可行方式的问题，我们可以通过递归枚举+剪枝的方法，结合连通子图的预计算来实现。以下是具体步骤和代码：

步骤说明 #

1. 预计算所有连通子图：生成原图的所有连通诱导子图，并为每个子图分配唯一索引。
2. 递归枚举合法分区：通过递归方式，每次选择包含剩余节点中最小节点的连通子图（避免重复生成同一分区的不同排列），逐步构建符合要求的分区（大小为2、3、4）。
3. 去重与整理结果：确保每个分区仅被记录一次，最终输出符合要求的索引元组列表。

完整代码 #

import networkx as nx
from itertools import combinations

# 构建原图
Graph = nx.Graph()
nodes = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
Graph.add_nodes_from(nodes)
Graph.add_edges_from([(5, 1),(5, 2),(1, 2),(1, 8),(15, 14),(8, 12),(8, 10),(8, 9),(12, 13),(9, 14),(9, 11),(2, 10),(4, 7),(4, 6),(4, 3),(4, 12),(7, 8),(13, 15),(6, 12),(6, 7),(3, 7),(3, 5),(3, 1),(11, 10)])

# 生成所有连通诱导子图
def get_all_connected_subgraphs(G):
    connected_subgraphs = []
    all_nodes = set(G.nodes)
    # 遍历所有非空节点子集
    for k in range(1, len(all_nodes)+1):
        for subset in combinations(all_nodes, k):
            subgraph = G.subgraph(subset)
            if nx.is_connected(subgraph):
                connected_subgraphs.append(frozenset(subset))
    return connected_subgraphs

# 获取所有连通子图并建立索引映射
connected_subgraphs = get_all_connected_subgraphs(Graph)
subset_to_idx = {subset: idx+1 for idx, subset in enumerate(connected_subgraphs)}  # 索引从1开始

# 存储最终结果
result = []
full_node_set = frozenset(nodes)

# 递归查找合法分区
def find_valid_partitions(remaining_nodes, current_partition):
    if not remaining_nodes:
        # 只保留大小为2、3、4的分区
        if 2 <= len(current_partition) <= 4:
            # 排序索引以避免重复分区（如(A,B)和(B,A)视为同一分区）
            sorted_partition = tuple(sorted(current_partition))
            result.append(sorted_partition)
        return
    
    # 如果当前分区已达4个，停止递归
    if len(current_partition) >= 4:
        return
    
    # 取剩余节点中的最小节点，确保每次选择包含该节点的子图，避免重复生成排列
    min_remaining_node = min(remaining_nodes)
    
    # 遍历所有包含最小节点且是剩余节点子集的连通子图
    for subset in connected_subgraphs:
        if min_remaining_node in subset and subset.issubset(remaining_nodes):
            new_remaining = remaining_nodes - subset
            subset_idx = subset_to_idx[subset]
            # 递归继续查找
            find_valid_partitions(new_remaining, current_partition + [subset_idx])

# 启动递归
find_valid_partitions(full_node_set, [])

# 去重（递归逻辑已避免重复，此步骤可省略但作为保障）
unique_result = list(set(result))
# 对结果排序（可选，提升可读性）
unique_result.sort()

# 输出结果
print(unique_result)

代码说明 #

• 连通子图生成：通过遍历所有非空节点子集，检查每个子集诱导的子图是否连通，收集所有连通子图并转为frozenset以便哈希和索引。
• 递归剪枝：每次选择包含剩余节点中最小节点的连通子图，确保每个分区仅被生成一次，避免重复的排列组合。
• 结果整理：将分区索引排序后存储，确保同一分区的不同排列不会被重复记录。

内容的提问来源于stack exchange，提问作者Nicolás Rivera