轮图和多轮图的生成树的计数

轮图和多轮图的生成树的计数 林 ( )茂名学院数学系, 广东 茂名 525000 摘要: 本文应用计算生成树个数的有向图、分块矩阵的行列式计算法以及常系数线性递归方程的解 ( )法, 计算得到轮图和多轮图的生成树个数的表达式显式或递推式. 关键词: 轮图; 多轮图; 生成树 在平面上作 个同心圆, 并作最大圆的K 条半径, 把所得 个交点和圆心作为图 n k n G ( 的顶点, 两点之间的线段或弧线 不经过其它 ) 点作为图 的边, 所得的图称为 轮图, 记G k 为, 它有 = + 1 个顶点, = 2条W k , n p k n q k n 边. 当 n ?3 时为简单图, 一般情况下为 n ? 1. 这一定义实际上给出了的一个平面 W k , n 嵌入. 若 = 1, 简记= , 即一般的轮 k W 1, n W n 图. ?2 时为多轮图. 如图 给定, k W k , n G W k , n 向, 每条边的方向是从轮心外指, 或从内圆指 向外圆, 或使每圈成 1?2? ??1 的有向 n 圈, 称为定向, 所得有向图记为. 本 W k , n () 文目的是求的生成树个数 , 简记W k , n ΣW k , n . Ξk , n 图 G 1 轮图的生成树的个数W n 设的完全关联矩阵为, 适当排列行列可得W n M e J O 1×n 1×n M =e ()1 - E n E n + S n 其中 为全 1 矩阵, 为全 0 矩阵, 为单位矩阵, 为矩阵J O E S n 0 0 - 1 - 1 0 ω fi - 1 0 n - 1 T( ) ( ) 易见 为正交矩阵, = 转置 , 把首行轮心对应之行作为参考行, 去之得关联S n S n n S M e 矩阵 ) ()(M = - E E + S 2n n n - E nT )(? N = M M = - E E + S n n n TE + S n n 2 - 1- 1 ) ) () )(((= - E + E + S E + S = E +E + S + S + E n n n n n n n n n n T( ) = 3E n + S n + S n 3T () ) ()(熟知 ΣW = Ξ= de t M M 4n n 我们先来处理如下一类矩阵: T () )( F a = a E + S + S 5n n n n 易见 a - 1 0 0 - 1 - 1 a - 1 0 0 0 - 1 a 0 0 () ()F a = n 6 0 0 0 a - 1 1 - 1 0 0 - a n () () () 令| | = , 对| | 按首行展开, 易得F n a f n a F n a () () () ()f a = a g a - 2g a - 2, n ? 3 7n n- 1 n- 2 () () 其中 = || , 而g n a G n a a - 1 0 0 0 0 - 1 a - 1 0 0 0 0 - 1 a 0 0 0()() G n a = 8 0 0 0 - 1 a - 1 0 0 0 0 - 1 a () 对|n | 按首行展开, 易得 G a () () () ()g a = a g a - g a , n ? 3 9n n- 1 n- 2 2 () () () () 且有 = - 1, = , 令 = 1, 使9式对 ?2 也成立, 此是常系数线性齐次 2g 2 a a g 1 a a g 0 a n 阶递归方程, 特征方程为 2 ()x - a x + 1 = 0 10 特征根为 a + ?a - ?2 ()Α=- 4 11 a , Βa =, ? = a 22 满足 + = , - = ?, = 1.Αa Βa a Αa Βa Αa Βa n n () ()? g a = C Α+ C Β, n ? 0 12n 1 2 a a () () () 把 = 1, = 代入 12式易解得待定系数g 0 a g 1 a a Α a Βa C = 1 , C = - . 2 ? ? 1 n+ 1 n+ 1 () () (), n ? 0 13g n a = Αa a - Β ? () () () 13式为矩阵 G n a 的行列式的通项表示. 代入 7式可得 n n () ()f + Β- 2, n ? 1 n a = Α14a a () () 约定 = 0, 使14式对 = 0 也成立. 遂得 f 0 a n () () 引理 1 矩阵 的行列式按 14式表出. F n a 由引理 1 便知 ? 5 3n n () Ξn = f n 3= Α+ Β- 2, n ? 1, Α3 Β3 = r ()3 3 15 2 易得知 满足如下递推, 可方便计算:Ξn () Ξn = 3Ξn- 1 - Ξn- 2 + 2, n ? 3; 16 () ()Ξ= ΞΞ+ 4, n ? 1; 172n n n 2 () () Ξ= ΞΞ+ 3, n ? 1 183n n n () Ξ= ΞΞ+ 2Ξ+ 2Ξ- Ξ, m > n ? 1; 19m + n m n m n m - n n ()Ξ= Α- 1, n ? 1 20n 3 式中[ ]表示不大于 的最大整数. {}的前 10 项为t t Ξn () 1, 15, 16, 45, 121, 320, 841, 2205, 5776, 15125 21 2 2 轮图的生成树的个数W 2, n 按标准定向所得有向图W 2, n 的完全关联矩阵为 O M F O () 1×n e n+ 1×n()2 ()22 , F = M = e O - E E + S E n×2n n n n n () 以第一行 轮心对应行为参考行, 去之得关联矩阵 M E O n n () 2 ()23 M = O - E E + S n×2n n n n 故 T M O 2n×n TM E O n n() ()() 222 E - E N = M M = n n O - E E + S n×2n n n n T O E + S n n n T M M + E - E n n =T) () (- E E + E + S E + S n n n n n n T - E () 4E + S + S n F 4- E n n n n n ()==24T()- E F 3 - E 3E + S + S n n n n n n 引理 2 设A 、B 、C、D 均为 n 阶方阵, 且A 、B 可换, 则 A B ) ()(de t= de t D A - CB 25 C D 证 若可逆, 则A - 1E A B n A O A B n =- 1O D - CA BC D C E n n - 1- 1= A D - CA B = D A - CA B A = D A - CB |||| || || 若A 不可逆, 令A t = A + tE , 则 t 充分大时A t 可逆, 显然A t 与B 仍可换, 故 A t B = D A - CB ||t C D () 上式两边均为 的多次式, 其常数项也相等, 也就是 25式成立.t () () 显然, 在24式右边矩阵中, 4与 可换, 故由引理 2 得F n E n () 2 )(() () )(= de t NF 3F 4- E Ξ2n = de t n n n TT(= | 4E + S + S ) ( ) - E |E + S + S 3n n n n n n n T T 2 2 ) = 13E + 7S + 7S + S + S ||n n n n n TT (= cE + S + S ) ( d E + S + S ) | |n n n n n n () () () () = F cF d = F c F d || ||||n n n n n n n n () () ()= Α+ Β- 2Α+ Β- 2, n ? 1 26c c d d 7+ 5 7- 5 式中 c= , d = , 可由待定系数法求得. 最后一步利用了引理 1, 其中2 2 11 Αc = , Βc = , 7 + 5 + 38 + 14 57 + 5 - 38 + 14 5 4 4 11()27 Α= , Β= d d 7 - 5 - 38 - 14 57 - 5 + 38 - 14 54 4 为了寻求 Ξ2, n 的递推公式以方便计算, 设 n n n n ) ) ) ) () (((u = ΑΑ+ ΑΒc+ ΑΒ+ ΒΒ, n ? 0;n c d d c d c d n n n n ()v = Α+ Β+ Α+ Β, n ? 0 28c c d d n 约定 Ξ2, 0 = 0, 则 ()Ξ= u - 2v + 4, n ? 0 292, n n n 4 3 2 容易推导知 , , , 满足方程 - 11+ 25- 11+ 1= 0, , , , 满足方 Αc Αd Αd Βc Αc Βd Βc Βd ς ς ς ς Αc Αd Βc Βd 4 3 2 程 - 7+ 13- 7+ 1= 0, 从而{}、{}分别适合递推方程ς ς ς ς u n v n ()u = 11u - 25u + 11u - u , n ? 4; 30n n- 1 n- 2 n- 3 n- 4 ()v = 7v - 13v + 7v - v , n ? 4 31n n- 1 n- 2 n- 3 n- 4 4 3 ( ) ( 由此两式求得 和 代入 29式可求得 . 另外, {- 2} 适合特征方程 - 11+u n v n Ξ2, nu n v n ς ς 2 4 3 2 ( ) ) 25- 11+ 1? - 7+ 13- 7+ 1= 0 对应的递推方程, 故{} 适合以下递推方 ς ς ς ς ς ς Ξ2, n 程: Ξ= 18Ξ- 115Ξ+ 336Ξ- 481Ξ+ 336Ξ2, n 2, n- 1 2, n- 2 2, n - 3 2, n - 4 2, n - 5 ()- 115Ξ+ 18Ξ- Ξ+ 20, n ? 8 322, n- 6 2, n- 7 2, n - 8 算得 Ξ2, n 的前 8 项为 () 1, 29, 361, 3509, 30976, 261725, 2163841, 17688869 33 3 轮图的生成树的个数k W k , n ()k () (仍按标准定向所得有向图的完全关联矩阵的首行 轮心对应行为 1, , 1, W k , n M e ) 0, , 0, 以此为参考行, 去之得关联矩阵 M K M K M K() k ()34 M = ω M K M k n×2k n () ) (其中同2式, = 为 ×2阶矩阵, 则M K E n O n n n T() ()()k k k N = M M T T TM M + K K KM T T T T M K M M + K K KM TTTT M K M M + K K KM = ωT T T T M K M M + K K KM T T M K M M k n () F 4- E n n () - E F 4- E n n n () - E F - E 4n n n()35 = ω () - E F 4- E n n n () - E F 3 n n k n 式中用到 T T () ()M M + K K = F 3+ E = F 4n n n T T T ()KM = - E ,M K = - E , M M = F 3n n n ()k ()()1 2 () () . 我们已得到= 的表达式15式和的表达式26式. N N N () 所求的 ΣW k , n = Ξk , n = de tN 参考文献: 1 , . [. , Bo ndy J A M u r tg U S RG rap h T h eo rg w ith A pp lica t io n s M L o ndo n and B a sing sto k eT h e M acm illan P re ss L td, 1976. 2 北京大学数力系. 高等代数[. 北京: 人民教育出版社, 1978.M ( ) 3 柯召, 魏万迪 1 组合论[M ] 1 北京: 科学出版社, 1981. Ca lcula t ion of Spann in g Tree of W hee lgraph an d M ult iwhee lgraph 2L IN Q u an w en (), , 525000, D ep a r tm en t o f M a th em a t ie sGuangdo ng M aom ing Co llegeM aom ing C h ina ( ) : , A bstrac tIn th is p ap e rexp re ssio n s exp lic it exp re ssio n and recu r sio n exp re ssio n o f sp ann ing t ree num be r s o f w h ee lg rap h and m u lt iw h ee lg rap h a re o b ta ined th ro ugh ca lcu la t ing , sp ann ing t ree num be r s w ith d ig rap h m e tho dca lcu la t ing b lo ck m a t r ix de te rm inan t and so lv ing .co n stan t co eff ic ien t linea r recu r r ing equa t io n : ; ; Keywordsw h ee lg rap hm u lt iw h ee lg rap hsp ann ing t ree