如何用Python统计无向图中的K3_3完全二部子图数量？

你的现有代码存在几个关键问题：

• 错误地检查整个图是否为二部图，而非当前遍历的6节点子图
• 变量逻辑混乱：result未赋值给返回的res，且找到一个候选后未继续统计所有符合条件的子图
• 统计逻辑错误：len(bad_m)/6无法正确计数K3,3的数量

以下是两种可行的实现方案：

方案一：基于NetworkX实现 #

利用NetworkX的子图处理和二部图工具，步骤清晰且易于维护：

import itertools as it
import networkx as nx
from networkx.algorithms import bipartite

def count_k33(G):
    count = 0
    node_list = list(G.nodes())
    
    # 遍历所有6节点的组合（K3,3恰好包含6个节点）
    for nodes in it.combinations(node_list, 6):
        subG = G.subgraph(nodes)
        
        # 快速过滤：K3,3有且仅有9条边，边数不符直接跳过
        if subG.number_of_edges() != 9:
            continue
        
        # 检查子图是否为二部图
        if not bipartite.is_bipartite(subG):
            continue
        
        # 获取二部图的两个分划集合
        try:
            X, Y = bipartite.sets(subG)
        except ValueError:
            continue
        
        # 分划必须各含3个节点
        if len(X) != 3 or len(Y) != 3:
            continue
        
        # 验证是否为完全二部图（双向全连接）
        is_complete = True
        for u in X:
            if not Y.issubset(subG.neighbors(u)):
                is_complete = False
                break
        if is_complete:
            count += 1
    
    return count

关键优化点： #

• 先通过边数过滤：K3,3固定有9条边，可快速排除大部分不符合的子图
• 使用issubset替代双重循环，简化全连接验证逻辑

方案二：纯Python实现（无第三方库依赖） #

如果需要脱离NetworkX，可直接基于邻接表实现：

import itertools as it

def count_k33_pure(graph):
    # graph格式：{节点: 邻居集合}，例如 {0: {1,2,3}, 1: {0,2,3}, ...}
    count = 0
    nodes = list(graph.keys())
    
    for combo in it.combinations(nodes, 6):
        # 固定第一个节点在分划X中，从剩余5个节点选2个组成X，避免重复计数
        for x_rest in it.combinations(combo[1:], 2):
            X = {combo[0]} | set(x_rest)
            Y = set(combo) - X
            
            # 验证X中所有节点都与Y全连接
            valid = True
            for u in X:
                if not Y.issubset(graph[u]):
                    valid = False
                    break
            if not valid:
                continue
            
            if valid:
                count += 1
                break  # 找到有效分划即停止，避免重复统计
    
    return count

核心逻辑： #

• 遍历所有6节点组合，通过固定第一个节点的分划归属，避免因X/Y互换导致的重复计数
• 利用集合的issubset方法快速验证全连接关系

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