行列木定理(全域木の数え上げ)
無向グラフで、頂点 $v$ の次数を $(v, v)$ 成分に、 $u$ と $v$ を結ぶ辺の本数に $-1$ を掛けた値を $(u, v)$ 成分( $u \ne v$)に置いた $N \times N$ 行列をラプラシアン行列といいます。全域木の個数は、ラプラシアン行列からどれか 1 つの頂点の行と列を取り除いた行列の行列式に等しくなります(行列木定理)。
有向グラフでは、 $v$ に入る辺の本数を $(v, v)$ 成分に、 $u$ から $v$ への辺の本数に $-1$ を掛けた値を $(u, v)$ 成分に置きます。この行列から根 $r$ の行と列を取り除いた行列の行列式が、 $r$ から外向きの全域木の個数です。
行列式は、素数を法とするガウスの消去法で求めます。ガウスの消去法(mod p) の det_mod と同じものを、このファイルの中に入れてあります。
count_spanning_trees(n, edges, mod): 頂点数 $n$( $n \ge 1$)と無向辺のリストedges = [(u, v), ...]のグラフの全域木の個数を、素数modで割った余り。自己ループは無視し、多重辺は別々の辺として数える。連結でなければ $0$。 $O(N^3)$count_arborescences(n, edges, root, mod): 頂点数 $n$ と有向辺のリストedges = [(u, v), ...]( $u$ から $v$ への辺)のグラフで、rootを根とする外向きの全域木の個数を、素数modで割った余り。自己ループは無視し、多重辺は別々の辺として数える。 $O(N^3)$
外向きの全域木は、根以外のどの頂点にもちょうど 1 本の辺が入り、根からすべての頂点へ辺の向きに沿って行ける、 $N - 1$ 本の辺の集合です。どの辺も根から離れる向き(親から子への向き)になります。根に向かう全域木(どの辺も子から親への向き)を数えるときは、すべての辺の向きを逆にして呼びます。
例:
MOD = 998244353
print(count_spanning_trees(4, [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)], MOD)) # 8
print(count_arborescences(3, [(0, 1), (1, 2), (0, 2), (2, 1)], 0, MOD)) # 3
# 頂点数 n の完全グラフの全域木は n^(n-2) 個
n = 5
print(count_spanning_trees(n, [(u, v) for u in range(n) for v in range(u)], MOD)) # 125
コード
def _det_mod(M, mod):
# 正方行列 M の行列式 mod(mod は素数、M の成分は 0 以上 mod 未満。M を書き換える)
n = len(M)
det = 1
for c in range(n):
piv = -1
for i in range(c, n):
if M[i][c]:
piv = i
break
if piv == -1:
return 0
if piv != c:
M[c], M[piv] = M[piv], M[c]
det = -det
row = M[c]
det = det * row[c] % mod
inv = pow(row[c], mod - 2, mod)
for i in range(c + 1, n):
Mi = M[i]
if Mi[c]:
f = Mi[c] * inv % mod
for k in range(c, n):
Mi[k] = (Mi[k] - f * row[k]) % mod
return det % mod
def count_spanning_trees(n, edges, mod):
# 頂点 0..n-1(n >= 1)、無向辺 edges = [(u, v), ...] のグラフの全域木の個数 mod(mod は素数)
# 自己ループは無視し、多重辺は別々の辺として数える
L = [[0] * n for _ in range(n)]
for u, v in edges:
if u != v:
L[u][u] += 1
L[v][v] += 1
L[u][v] -= 1
L[v][u] -= 1
# ラプラシアン行列から頂点 0 の行と列を除いた行列の行列式
return _det_mod([[x % mod for x in L[i][1:]] for i in range(1, n)], mod)
def count_arborescences(n, edges, root, mod):
# 頂点 0..n-1、有向辺 edges = [(u, v), ...](u から v への辺)のグラフで、
# root から外向きの全域木(すべての辺が根から離れる向き)の個数 mod(mod は素数)
L = [[0] * n for _ in range(n)]
for u, v in edges:
if u != v:
L[v][v] += 1 # v に入る辺の本数
L[u][v] -= 1
# root の行と列を除いた行列の行列式
idx = [i for i in range(n) if i != root]
return _det_mod([[L[i][j] % mod for j in idx] for i in idx], mod)