Prufer codes與Generalized Cayley's Formula -开发者知识库

Prufer codes與Generalized Cayley's Formula -开发者知识库,第1张

Prufer序列

  在一棵n個節點帶標號樹中,我們認為度數為1的點為葉子。n個點的樹的Prufer序列是經過下面流程得到的一個長度為n-2的序列。

    1.若當前樹中只剩下兩個點,退出,否則執行2。

    2.找到樹中編號最小的節點,將與它相連的那個點的編號加入Prufer序列的末尾,並將這個葉子刪除。返回1。

  顯然,每棵樹都唯一對應一個Prufer序列,而每個Prufer序列也唯一對應一棵樹。可以通過一下流程得到這棵樹。

    1.令A={1,2,...,n},不斷重復2直到Prufer序列為空。

    2.找到A中最小的不在Prufer序列中的點,將其與Prufer序列首元素連邊,然后同時刪除這個點與序列首元素。

    3.此時A中還剩下兩個點,將這兩個點連邊。

  根據以上流程,不難發現:若點i在樹中的度數為a[i],則它在Prufer序列中會出現a[i]-1次。

 

Cayley's Formula

  Prufer序列中的每個元素都可以從1取到n,且每種方案會唯一對應一棵帶標號無根樹。

  所以,由於Prufer序列共有$n^{n-2}$個,n個點的帶標號無根樹就有$n^{n-2}$種。

  拓展:

    1.顯然,n個點的帶標號有根樹有$n^{n-2}$種。

    2.當樹中每個點的度數$a_i$都已經確定后,由Prufer序列得,滿足條件的樹共有$\frac{(n-2)!}{\prod a_i!}$種。

  例題:BZOJ1005,BZOJ1211,BZOJ1430

 

Generalized Cayley's Formula

  已知n,k,求f(n,m)表示n個點組成的共有m棵樹的森林,且1,2,...,m分別屬於不同的樹,的方案數。

  先給出結論:$f(n,m)=m\cdot n^{n-m-1}$。

  (顯然可以發現$f(n,1)=n^{n-2}$)

  證明:

    顯然,$f(1,1)=0$,$f(n,0)=0(n\geq 1)$

    數學歸納,假設對於所有$i<n$的$f(i,j)$都已證明。

    考慮1號點屬於的那棵樹,枚舉1號點的度數i,則刪除后這張圖會變成n-1個點,m i-1棵樹。

    $f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}f(n-1,m i-1)$

    將原式代入,有$f(n,m)=\sum\limits_{i=0}^{n-m}\binom{n-m}{i}(m i-1)(n-1)^{n-m-i-1}=mn^{n-m-1}$

    命題得證。

  拓展:

    顯然n個點組成有根樹森林的方案為$\sum\limits_{k=1}^{n}n^{n-k-1}\times k\times \binom{n}{k}$

  應用:CF1109D

  給定n,m,a,b,求有多少個n個點的帶標號無根樹,滿足所有邊權在[1,m]中,且a到b的簡單路徑長度為m。

  顯然枚舉a,b中的邊數,那么a,b中間的點有$P_{n-2}^{i-1}$種方案,這中間i條邊的邊權共有$C_{m-1}^{i-1}$種方案,其余邊權有$m^{n-i-1}$種方案,而剩下的就是n個點組成i 1棵樹,其中在a,b簡單路徑上的i 1個點分別屬於其中一棵樹的方案數,也就是$f(n,i 1)=(i 1)n^{n-i-2}$。

 

定理拓展:

  n個帶權的點,定義每條邊的權值為相連的兩個點的權值之積,定義一棵樹的權值是所有邊的權值之積,求所有樹的權值和。

  相當於每棵樹中每個點的權值的度數次方的和。考慮Prufer序列,每個點都恰出現度數-1次。於是根據乘法分配律,答案為(所有點權值之積)*(所有點權值之和)^(n-2)。

  這個推論包含了上面所有定理。當所有點權值取1時,就是Cayley's Formula。當將點1~m縮成一個權值為m的點時,就是Generalized Cayley's Formula。

  以上所有似乎都可以用Matrix Tree那一套理論通過化簡行列式得到。

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复