如何生成满足给定节点度、无自环且允许平行边的随机多重图

前置合法性校验 #

首先确认你的度序列满足以下3个条件，否则不存在符合要求的图：

• 所有度数为非负整数
• 总度数为偶数（符合握手定理）
• 最大节点度 ≤ 总度数/2（无自环要求下，单个节点的所有边都要连到其他节点，度不能超过其余所有节点的度之和）

推荐算法：改良版配置模型 #

原配置模型生成的带自环的图可以通过轻量调整完全消除自环，同时严格保留原始度序列，实现效率远高于逐边随机分配的方案，步骤如下：

1. 按原始配置模型逻辑生成随机多重图，允许暂时存在自环
2. 批量消除自环：
   • 每取出两个自环(u,u)和(v,v)，删除这两个自环，新增两条平行边(u,v)，两个节点的度完全不变，自环直接消除
   • 若最终剩余1个自环（仅当总度数模4余2时可能出现），则随机选一条非自环边(a,b)，删除该边和剩余自环，新增(a,u)和(b,u)，三个节点的度均保持不变，自环消除

可直接运行的实现代码 #

import networkx as nx
import random
from collections import defaultdict

def generate_valid_multigraph(deg_sequence):
    # 生成初始配置模型多重图
    G = nx.configuration_model(deg_sequence, create_using=nx.MultiGraph)
    # 收集所有自环的节点
    self_loop_nodes = [u for u, v in G.edges() if u == v]
    
    # 处理成对的自环
    while len(self_loop_nodes) >= 2:
        u = self_loop_nodes.pop()
        v = self_loop_nodes.pop()
        # 移除两个自环
        G.remove_edge(u, u)
        G.remove_edge(v, v)
        # 添加两条跨节点平行边，度保持不变
        G.add_edge(u, v)
        G.add_edge(u, v)
    
    # 处理剩余的单个自环
    if self_loop_nodes:
        u = self_loop_nodes[0]
        G.remove_edge(u, u)
        # 随机找一条非自环边用于调整
        while True:
            a, b = random.choice(list(G.edges()))
            if a != b:
                break
        G.remove_edge(a, b)
        G.add_edge(a, u)
        G.add_edge(b, u)
    
    # 校验结果合法性
    assert [d for _, d in G.degree()] == deg_sequence, "度序列不匹配"
    assert not any(u == v for u, v in G.edges()), "仍存在自环"
    return G

原有逐边分配代码的问题 #

你现有代码的核心缺陷是没有死锁回退机制：当分配到最后剩余少量节点时，前面的随机选择可能导致剩余度数无法配对（比如仅剩余1个节点还有2度待分配），没有调整路径。如果要保留现有逻辑，需要在分配结束后增加重连调整步骤：找到待分配的度数和已有的边，通过修改已有边的端点来消化剩余度数，同时不改变度序列。

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