推 Fenikso:大概了解了 感謝<(_ _)> 12/09 10:40
※ 引述《Fenikso (我是蜜蜂~)》之銘言：
: 定義"車輪圖"Gn是一個n+1個點,2n條邊的圖
: 形狀就像車輪一樣,一個點在中間,n個點在圓周上
: (好難形容..)
: 如圖: http://img379.imageshack.us/my.php?image=wheelfy2.jpg
: 問Gn的不同的spanning tree的個數
: 用generating function或遞迴式表示
: 應該不會有close form吧orz
: (兩個spanning tree如果在旋轉後一樣 視為同一種)
: 例: G3的不同的spanning tree有6個, 如下圖
: http://img171.imageshack.us/my.php?image=g3pn6.jpg
感覺是用Burnside's lemma可以做
數(s, g) pair, s是spanning tree, g是作用在s上圖不變的group element.
則 sum(s) sum(g) (s, g) = sum(g) sum(s) (s, g)
LHS = (要數的東西)*|G|
RHS = (全部的spanning tree) + {g1 term} + {g2 term} + ...
例如說N+1 = 4的圖, G = Z_3
LHS = 要數的東西 * 3
RHS = (16) + 1 + 1
N+1 = 5的圖, G = Z_4
LHS = 要數的東西 * 4
RHS = (45) + 1 + (1^2 + 2^2) + 1
所以說
要數的東西 = 1/|G| * { (全部的spanning tree) +
sum{m over factors of N, exclude N} ((N/(m,N)) - 1) * m^2 }
算算看N+1 = 6的
(1/5) * { 121 + 4 * 1^2 } = 25
N+1 = 7的
(1/6) * { 320 + 5 * 1^2 + 2 * 2^2 + 1 * 3^2 } = 57
全部的spanning tree可以用matrix tree theorem算
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.73.81.177
※ 編輯: tester 來自: 203.73.81.177 (12/08 22:50)