SRM460 Div2 1000pts

戻る

注：Wolfram MathWorld(http://mathworld.wolfram.com/PrueferCode.html)から画像を引用しています。

[問題原文] TheCitiesAndRoadsDivTwo.txt
TheCitiesAndRoadsDivTwo.txt

グループkの中に含まれるノード数：gk
グループ数：m
全ノード数：n(=g1+g2+...+gm)
としたとき、ノード間の全域木の数が、




あることをPrüfer Codeを使って示す。

Prüfer Code
Wolfram MathWorld(http://mathworld.wolfram.com/PrueferCode.html

Prüfer Codeと呼ばれる数列が1対1で全域木に対応している。そのため、作れる数列の総数=全域木の総数と簡単に求められる。
ただ、全域木の個数がnn-2になるという結果は、証明には使わない。

リンク先の下の例をみると、Prüfer Codeがどんな全域木に対応しているのか分かると思う。
　{1,2,1,3,3,5}は
 　ノード1から直接つながっている葉（木の端っこ。1点としか繋がってない）で、一番ノード番号が若いものを削除。つまり4しかないので4を削除。
 　ノード2から直接つながっている葉で、一番ノード番号が小さいものを削除。6しかないので6を削除。
 　ノード1から直接つながっている葉で、一番ノード番号が小さいものを削除。2しかないので2を削除。
 　ノード3から直接つながっている葉で、一番ノード番号が小さいものを削除。1と7があるが、1のほうが小さいので、1を削除。
 　ノード3から直接つながっている葉で、一番ノード番号が小さいものを削除。7しかないので、7を削除。
 　ノード5から直接つながっている葉で、一番ノード番号が小さいものを削除。3と8があるが、3のほうが小さいので、3を削除。
この時点で、5-8が残っているが、木としては5-8はどのようにつながろうが1種類しかないので、これで終了。
このことから、全域木はn-1個の辺を使うが、最後に1辺のこるので、Prüfer Codeはn-2の長さであることが分かる。


簡単な具体例
m=3, g1=10, g2=1, g3=1, n=12について考えてみる。
グループ間の全域木は以下の3通り。



ノード間の全域木が何通りあるかを求めたい。

まず、{1}のケースを図示すると以下のようになる。


{1}のケースは、1-2と1-3の2本をつなげるので、例えば以下のような方法がある。


以下のように、2本とも同じノードにつないでも良い。


つまり、グループ1内にある10個のノードのどれかに2本の辺を足すので、
パターンは102通り

次に、{3}のケースを図示する。これは1-3の1本を、グループ1内の10個のノードのどれかにつなげればいいので、10通り。



最後に、{2}のケースは、{3}と同じになるので、10通り。

つまり、
{1} →  102通り
{3} →  10通り
{2} →  10通り
となり、ノード間の全域木は合計100+10+10=120通りとなる。

この例で分かる重要なことは、
グループ間の全域木で、あるグループkの次数（=グループkと接合する辺の数）をdkとすると、
ノード間の全域木はgkdk通りになるということである。
{1}のケースは、グループ1に10個のノードがあり、次数は2だったので（=2つの辺を接合したので）、10の2乗で100通りになった。
また、他のグループも複数のノードを含んでいた場合は、単に直積集合になるので、乗算すればいいだけ。つまり、
g1d1g2d2...gmdm通りとなる。

複雑な具体例
m=4について考えてみる。g1, g2, g3, g4, nについては任意とする。

グループ間の全域木は以下の16通り。



PrüferCodeと次数（=接合する辺の数）とノード間の全域木数を以下の表にまとめる。


Prüfer Code
次数{d1,d2,d3,d4}
ノード間の全域木数
()内の項=ノード間の全域木数/g1g2g3g4
{1,1}
{3,1,1,1}
g13g2g3g4
 
g12 
{2,1}
{2,2,1,1}
g12g22g3g4
g1g2
{3,1}
{2,1,2,1}
g12g2g32g4
g1g3
{2,2}
{1,3,1,1}
g1g23g3g4
 
g22 
{3,2}
{1,2,2,1}
g1g22g32g4
g2g3
{4,2}
{1,2,1,2}
g1g22g3g42
g2g4
{4,1}
{2,1,1,2}
g12g2g3g42
g1g4
{1,2}
{2,2,1,1}
g12g22g3g4
g1g2
{2,4}
{1,2,1,2}
g1g22g3g42
g2g4
{3,4}
{1,1,2,2}
g1g2g32g42
g3g4
{4,4}
{1,1,1,3}
g1g2g3g43
 
g42 
{2,3}
{1,2,2,1}
g1g22g32g4
g2g3
{3,3}
{1,1,3,1}
g1g2g33g4
 
g32 
{4,3}
{1,1,2,2}
g1g2g32g42
g3g4
{1,4}
{2,1,1,2}
g12g2g3g42
g1g4
{1,3}
{2,1,2,1}
g12g2g32g4
g1g3


このまま、g13g2g3g4+g12g22g3g4+...とノード間の全域木数の総和を求めれば答えはでるが、この式をもっと簡単にしたい。
まず、g1g2g3g4(g12+g1g2+...)と括弧でくくれる。()の中に入る項を上の表一番右に書いた。
	
さらに、Prüfer Codeと全域木の1:1対応のルールを使用する。例えば{1,1}のときは、
グループ1から出ている葉を2回削除して（グループ2とグループ3）、それでもまだグループ4と
は最後までつながっているので、グループ1には辺が3つあったことが分かる。つまり、
(Prüfer Codeにグループ番号kが出てきた回数)+1=そのグループkの次数
であるので、さらにg1g2g3g4で括れば、
(Prüfer Codeにグループ番号kが出てきた回数)  =()内の項グループkの次数
このことから、Prüfer Codeと()内の項に以下のような密接な関係があることが分かる。
  
  Prüfer Code : 4つ(1,2,3,4)の数字を重複可能で2回選ぶ。例えば、{1,1},{2,1}
  ()内の項    : 4つ(g1,g2,g3,g4)の文字式を重複可能で2回選んだものを掛け合わせた項をつくる。例えば、g12,g1g2

これは多項式の累乗を展開するときの計算と全く同じになる（逆算すればすぐ分かる。）。つまり、

g13g2g3g4+g12g22g3g4+...(残り12項分略)...+g12g2g3g42+g12g2g32g4
= g1g2g3g4(g12+g1g2+g1g3+g22+g2g3+g2g4+g1g4+g1g2+g2g4+g3g4+g42+g2g3+g32+g3g4+g1g4+g1g3)
= g1g2g3g4(g1+g2+g3+g4)2

一般解
上記の解をみると、
g1g2g3g4 はグループ内のノード数の積。
(g1+g2+g3+g4)ノードの総和nと等しい
()2の2は、()内の単項式の次数の和 = Prüfer Codeの長さ = (グループ数m)-2となる。先ほどの問題では4-2=2
ゆえに、一般解は以下の形になる。