有关对称无权图生成树数目的拆分定理 - 厦门大学学报（自然科学版）.PDF

第 卷 第 期 ( ) 55 4 厦门大学学报 自然科学版 Vol.55 No.4 年 月 ( ) 2016 7 JournalofXiamenUniversit NaturalScience Jul.2016 y : / doi10.6043 .issn.0438-0479.201512026 j 有关对称无权图生成树数目的拆分定理 , 1* 12 , 龚和林 王 伟 ( , ; , ) 厦门大学数学科学学院 福建 厦门 塔里木大学信息工程学院 新疆 阿拉尔 1. 3610052. 843300 摘要: , 设 是一个对称平面图 等证明了一个有关 的生成树数目的拆分定理 也就是 的生成树数目可用两 G .Ciucu G G , , , 个小图的生成树数目乘积来表示 在此基础上 提出了一种图变换 给出了图在这种变换下生成树数目的变化关系式 再 . , , 结合矩阵 树定理给出了该拆分定理的一个简短证明 同时 受 等证明的赋权图生成树权和的拆分定理启发 还给 - . Zhang 出了一个关于对称无权图生成树数目的等价拆分公式. 关键词: ; ; ; 生成树数目 矩阵 树定理 对称性 平面图 - 中图分类号: 文献标志码: 文章编号: ( ) O157.5 A 0438-0479201604-0554-04 ((),()) (), () () [ ], [ ], 给定图 若 记 记 G=V G EG . v∈V G d v ii G =G V ∪V G =G V ∪V G G L L C R C R C (), [] [ ]则 ( ) ( ) ( ) ( ) 为 在 中的度 若 记 为 的导出子 =G