与えられた次数分布を満たす無向グラフの構成法

与えられた次数分布を満たす無向グラフを作りたい場合は、Havel-Hakimiのアルゴリズムが使えます。Python実装を以下に示します。

import pprint

def havel_hakimi(degrees):
    n = len(degrees)
    degrees = [(v, i) for (i, v) in enumerate(degrees)]
    
    edges = [[] for i in range(n)]
    while len(degrees) > 0:
        degrees = sorted(degrees)[::-1]
        
        dx, x = degrees[0]
        degrees = degrees[1:]
        
        if (dx < 0) or (len(degrees) < dx):
            return None
        
        for i in range(dx):
            dy, y = degrees[i]
            degrees[i] = (dy - 1, y)
            
            edges[x].append(y)
            edges[y].append(x)
        
    return edges

degrees = [4, 2, 2, 2, 2]
result = havel_hakini(degrees)

print("degrees = ")
pprint.pprint(degrees)
print("graph = ")
pprint.pprint(result)

与えられた次数分布を満たすような無向グラフは常に存在するわけではなく、その条件はErdős-Gallai定理としてまとめられているようです。Erdősさんって、多分Erdős–RényiグラフのErdősさんなので、グラフ界隈で頑張っていた人なんですかね。知らないですけど。