[1] 条件の言いかえ

全域木を選ぶことは各二重頂点連結成分において全域木を選ぶことと同じです。

グラフの二重頂点連結成分のうち \(1\) つをとり、成分内の頂点に”ぶら下がっている”頂点の数の偶奇に着目します。より正確には、二重頂点連結成分に属する頂点を \(v_1,v_2,\dots,v_n\) としたとき、各頂点 \(v_i\) に対し、集合 \(S_i=\{u\mid \) \(j=1,2,\dots,n\) に対して、 頂点 \(u,v_j\) を結ぶ単純パスは必ず頂点 \(v_i\) を含む \(\}\) を頂点 \(v_i\) に”ぶら下がっている”頂点集合とし、その要素数の偶奇に着目します。例えば下図のグラフにおいて、頂点 \(1,2,3,4\) からなる二重頂点連結成分に着目した際、頂点 \(1,2,3,4\) にぶら下がっている頂点の数はそれぞれ \(4,1,3,5\) です。

[1-1] 二重頂点連結成分内の \(|S_i|\) の偶奇が一致しない場合

この場合、二重頂点連結成分内で隣接する \(2\) 頂点 \(v_i,v_j\) であって \(|S_i| \equiv 1, |S_j| \equiv 0\ (\bmod\ 2)\) を満たすものが存在します。このような \(v_i,v_j\) に対して、二重頂点連結成分内の全域木のうち、頂点 \(v_i\) が葉であり、頂点 \(v_j\) とのみ隣接するようなものをとり、それを含むような全域木上で完全マッチングが取れるかを考えます（このような全域木が取れることは二重頂点連結性からわかります）。木上の完全マッチングの存在判定は葉側から貪欲にマッチさせることで判定できることに注意すると、 \(|S_i| \equiv 1\) であったことから頂点 \(v_i\) は頂点 \(v_j\) とマッチしなくてはなりません。しかし \(|S_j| \equiv 0\) であったことから、葉側から貪欲にマッチさせた場合、頂点 \(v_j\) は \(S_j\) 内のいずれかの頂点とすでにマッチしているため、頂点 \(v_i,v_j\) はマッチさせることができません。以上よりこのケースでは条件を満たさないことがわかります。

[1-2] 二重頂点連結成分内の \(|S_i|\) がすべて偶数である場合

この場合、各頂点 \(v_i\) は \(S_i\) 内のいずれかの頂点とマッチすることになるため、二重頂点連結成分内の辺はマッチングに用いられません。よって二重頂点連結成分内の辺をすべて削除したグラフにおいて、各連結成分が条件を満たすことと同値です。

[1-3] 二重頂点連結成分内の \(|S_i|\) がすべて奇数である場合

二重頂点連結成分内で次数が \(3\) 以上の頂点 \(v_i\) が存在する場合（すなわち、ある \(v_i\) に対して頂点 \(v_i\) と頂点 \(v_1,v_2,\dots,v_n\) を結ぶ辺が \(3\) つ以上存在する場合）、完全マッチングを持たない全域木が存在することを示します。以下、頂点 \(v_1\) と頂点 \(v_2,v_3,v_4\) が辺で結ばれているものとします。

\(S_1\) 内の頂点からなる全域木 \(T_1\)、\(S_1\) 内の頂点以外からなる全域木 \(T_2\) をとります。 \(T_2\) を \(v_4\) を根とする根付き木とみなし、 \(G\) の全域木として以下の \(3\) 種類の木を考えます。

• \(T_1,T_2\) が含む辺に \(v_1,v_2\) を結ぶ辺を追加したもの
• \(T_1,T_2\) が含む辺に \(v_1,v_3\) を結ぶ辺を追加したもの
• \(T_1,T_2\) が含む辺から \(v_2,v_3\) と根側の頂点を結ぶ辺をそれぞれ削除し、 \(v_1\) と \(v_2,v_3,v_4\) を結ぶ辺を追加したもの

下図はこれら \(3\) 種類の全域木を左から順に並べたものです。

\(1,2\) 番目の全域木が完全マッチングを持つ場合のみを考えていいです。このとき、図のように \(v_2\) は \(v_1\) とマッチしており、特に \(v_2\) の子頂点は葉側の頂点とのマッチに使用されています。 \(v_3\) についても同様です。このような状況下で \(3\) 番目の全域木が完全マッチングを持つかを考えます。頂点 \(v_2\) の子頂点はすべて葉側の頂点とマッチしているため、頂点 \(v_2\) は頂点 \(v_1\) とマッチする必要があります。一方 \(v_3\) についても同様のことが成り立ってしまいます。よってこの全域木は完全マッチングを持ちません。以上より上記の \(3\) 種類の全域木のいずれかが完全マッチングを持たないことが示せました。

ここまでの議論から \(|S_i|\) がすべて奇数のとき、二重頂点連結成分は橋または偶数長のサイクルであることがわかります。

[1-1], [1-2], [1-3] での議論から \(G\) が条件を満たすには、以下の手順で構築できるグラフであることが必要です。

• \(N\) 頂点をいくつかのサイクル・橋に分割する
• 全体が連結になるまで以下を行う
  • まだ連結でないサイクル・橋を \(2\) つ以上選ぶ。選んだ各サイクル・橋から代表点を \(1\) つ選び、それらを \(v_1,v_2,\dots,v_k\) とする。 \(v_1,v_2,\dots,v_k\) が二重頂点連結になるように \(v_1,v_2,\dots,v_k\) を端点とする辺を追加する。

逆に \(G\) がこのようにして構築されたグラフである場合、全域木を取ると各サイクルについて、サイクル内の \(2\) 通りのマッチングのうちどちらか片方は全域木上でとれ、橋は全て全域木に必ず含まれるため、全域木はかならず完全マッチングを持ちます。

よって上記の手順で構築されるグラフを数え上げればいいです。

[2] 二重頂点連結グラフの数え上げ

条件を満たすグラフを数えるにあたって連結グラフ、二重頂点連結グラフの数え上げを考えます。

まず \(n\) 頂点からなる連結グラフの数を \(f_n\) とおきます。 \(n\) 頂点からなるグラフの数は \(2^{\frac{n(n-1)}{2}}\) であり、頂点 \(1\) を含む連結成分のサイズが \(k\) であるようなグラフの数は \(\binom{n-1}{k-1}f_k \times 2^{\frac{(n-k)(n-k-1)}{2}}\) であるため、

\[\displaystyle f_n + \sum_{k=1}^{n-1} \binom{n-1}{k-1}f_k \times 2^{\frac{(n-k)(n-k-1)}{2}} = 2^{\frac{n(n-1)}{2}}\]

が成り立ちます。これをもとに \(f_1,f_2,\dots,f_N\) を \(O(N^2)\) で求めることができます。

次に二重頂点連結グラフの数え上げを考えます。 \(n\) 頂点からなるラベル付き単純連結無向グラフであって、二重頂点連結成分の数が \(k\) であるグラフの数を \(g_{n,k}\) とします。このとき、

\[\displaystyle \sum_{i=1}^{n} g_{n,k} = f_n\]

であることを利用して \(g_{n,1}\) を求めていきます。

\(2 \leq k\) に対する \(g_{n,k}\) について考えます。二重頂点連結成分の数が \(k\) である連結グラフをとり、頂点 \(1\) を始点とするBFS木を考えます。各二重頂点連結成分に属する頂点のうち、最も根側の頂点を除いた頂点からなる “グループ” を作ります。これにより頂点 \(2,3,\dots,n\) は \(k\) 個のグループに分かれ、それぞれちょうど \(1\) つのグループに属します。

今、 \(k\) 個のグループへの分け方を \(1\) つ固定します。各グループのサイズを \(a_1,a_2,\dots,a_k\) としたとき、このグループ分けを達成するグラフの数は \(n^{k-1} \prod_{i=1}^k g_{a_i+1,1}\) になります。

これは次のようにわかります。各グループ \(1,2,\dots,k\) について、根側の頂点を選び、その頂点となす二重頂点連結グラフを決めることでグラフが決まります。二重頂点連結グラフの作り方は \(\prod_{i=1}^k g_{a_i+1,1}\) であるため、根側の頂点の選び方を考えればいいです。根側の頂点をグループ \(j\) から選ぶ場合は \(a_j\) 通り選び方がある（頂点 \(1\) はグループ \(0\) と考えて \(a_0=1\) とします）ことに注意すると、解きたい問題は以下のような問題です。

• \(k+1\) 頂点からなる根付き木がある。頂点 \(i=1,2,\dots,k\) について、親頂点 \(p_i\) に対して \(a_{p_i}\) の重みを掛けるとき、ありえる木の重みの総和を求めよ

ここで、重みを辺 \((i,p_i)\) ごとに \(a_i \times a_{p_i}\) だけかけることにしても最後に \(\prod_{i=1}^{k} a_i\) で割れば元の問題の答えが求まります。結局以下の問題が解ければいいです。

• サイズ \(a_0,a_1,\dots,a_k\) の連結成分がある森グラフに対し、辺を足して全域木を作る方法は何通りか

これは有名問題で \(\prod_{i=0}^{k}a_i \times (a_0+a_1+\dots+a_k)^{k-1} = \prod_{i=0}^{k}a_i \times n^{k-1}\) であることが知られています。例えばプリューファー列の概念を用いることで証明できます。これを \(\prod_{i=1}^{k} a_i\) で割ることで最初に示した結論が得られました。

以上より \(g_{n,k}\) は

\[\displaystyle g_{n,k}=\frac{n^{k-1} \times n!}{k!} \sum_{a_1+a_2+\dots + a_k = n-1} \prod_{i=1}^{k} \frac{g_{a_i+1,1}}{a_i!}\]

となります。 \(2 \leq k\) のとき、 \(a_i\) は \(1 \leq a_i \leq n-2\) の範囲でしか動かないことに注意すると、上記の式の総和の部分は \(g_{n,1}\) を求めるごとに \(O(N^2)\) で求めることができます。よって \(1 \leq k \leq n \leq N\) に対する \(g_{n,k}\) は全体で \(O(N^3)\) で求めることができます。

[3] 条件を満たすグラフの数え上げ

\(N\) 個の頂点をサイクル・橋に分割した際、各サイクル・橋が含む頂点数を \(l_1,l_2,\dots,l_k\) とします。いくつかのサイクル・橋から代表点を選び、それらが二重頂点連結になるように辺を追加する操作を \(m\) 回行った場合、最終的にできるグラフでサイクル・橋を縮約して得られるグラフは \(k\) 頂点からなり、二重頂点連結成分が \(m\) 個存在するグラフになります。各二重頂点連結成分について代表点の選ぶ分の重みづけを行うことを考慮すると、[2] で考察した “グループ”分けを行った後の数え上げについて、

• グループ \(j\) 内の頂点から根側の頂点を選ぶとき、選び方は (グループ \(j\) に属するサイクル・橋の頂点数の総和) 通り
• グループ \(i\) に属する各サイクル・橋から代表点を \(1\) つ選ぶ

ように変更することで同じように数え上げができます。

まとめると \(k\) 個のサイクル・橋に分割した後、\(m\) 回操作を行ってグラフを作る方法は

\[\displaystyle \frac{n^{m-1} \times (k-1)!}{m!} \prod_{i=1}^{k} l_i \sum_{a_1+a_2+\dots + a_m = k-1} \prod_{i=1}^{m} \frac{g_{a_i+1,1}}{a_i!}\]

となります。総和部分については [2] で求めたとおりであり、あとは分割に対するサイクル・橋の頂点数の積の総和を求めればよく、これは \(O(N^3)\) で求まります。

以上より条件を満たすグラフの数は \(O(N^3)\) で求めることができます。