Day 025-Q4 — Wilson's Algorithm (LERW) + 有効抵抗

問題

無向連結グラフ $G$ から Wilson's Algorithm で一様ランダムスパニングツリーを生成。$K$ 回試行で辺頻度を計測し、ラプラシアン擬似逆行列を用いた有効抵抗の理論値と比較する。

制約

入出力例

3 3 1000
1 2
2 3
1 3
12345

(理論的に各辺の有効抵抗 ≈ 2/3)

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
import random
import numpy as np
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    edges = []
    adj = [[] for _ in range(N)]
    adj_matrix = [[False] * N for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        edges.append((u, v))
        adj[u].append(v); adj[v].append(u)
        adj_matrix[u][v] = adj_matrix[v][u] = True
    seed = int(input())
    rng = random.Random(seed)

    def wilson(rng_instance):
        in_tree = [False] * N
        next_node = [-1] * N
        tree_edges = set()
        in_tree[0] = True
        for i in range(1, N):
            if in_tree[i]: continue
            v = i
            while not in_tree[v]:
                nxt = rng_instance.choice(adj[v])
                next_node[v] = nxt
                v = nxt
            v = i
            while not in_tree[v]:
                in_tree[v] = True
                u = next_node[v]
                tree_edges.add((min(v, u), max(v, u)))
                v = u
        return tree_edges

    sample_tree = wilson(rng)
    print(f"Sample URST (seed={seed}):")
    edge_strs = " ".join(f"({u+1},{v+1})" for u, v in sorted(sample_tree))
    print(f"Edges: {edge_strs}")
    print()

    edge_to_idx = {(min(u,v), max(u,v)): i for i, (u, v) in enumerate(edges)}
    freq = [0] * M
    for _ in range(K):
        tree = wilson(rng)
        for e in tree:
            if e in edge_to_idx:
                freq[edge_to_idx[e]] += 1

    L = np.zeros((N, N))
    for i in range(N):
        for j in range(N):
            if adj_matrix[i][j]:
                L[i][j] = -1.0
                L[i][i] += 1.0
    Lpinv = np.linalg.pinv(L)
    def R_eff(u, v):
        return Lpinv[u][u] + Lpinv[v][v] - 2 * Lpinv[u][v]

    print(f"Edge frequencies over {K} trials:")
    for i, (u, v) in enumerate(edges):
        print(f"({u+1},{v+1}): {freq[i]/K:.3f} (theoretical: {R_eff(u,v):.3f})")
    print()
    print("Effective resistances:")
    for u, v in edges:
        print(f"({u+1},{v+1}): {R_eff(u,v):.4f}")

main()

Step-by-Step 解説

よくあるミス

次のステップ

• Aldous-Broder との収束速度比較
• 代数的連結度 (Fiedler 値) と有効抵抗

自己評価

自分の回答

気づき・メモ