两类图的生成树的计数

发布时间：2021-01-05 04:47

　　任给一个权函数为ω:E（G）→（0,∞）的边权图G=（V（G）,E（G））,若将G中每一条边的权看作该边的电导（即电阻的倒数）,则任一边权图等价于物理学中的一个电网络图.假设T（G）表示一个边权图G的所有生成树的集合,对任意一棵生成树T∈T（G）,定义T的权ω（T）为它的所有边的权的乘积,即ω（T）=∏_e∈E（T）ω（e）.设t（G）表示图G的所有生成树的权之和,即t（G）=∑_T∈T（G）ω（T）.显然,当G的每条边的权均为1时,t（G）等于图G的生成树的数目.利用电网络中的等价网络替换原理、广义星-三角形变换以及串并联法则等方法,本文首先给出了边权图的线图的定义,并研究了边权图的生成树的权和的计算问题,给出了相应的计数公式,推广了权函数为1的线图的生成树的计数方面的结果;第二,我们研究了与统计物理密切相关的一类所谓的广义Farey网络图的生成树的计算问题,得到了计数公式;最后,我们给出了电网络理论中著名的Foster定理的一个简单证明. 

【文章来源】：集美大学福建省

【文章页数】：37 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 绪论
    1.1 基本概念
    1.2 生成树的应用背景及研究进展
    1.3 本文主要内容和研究方法
第2章 边权图的线图的生成树权和
    2.1 引言
    2.2 电网络方法
    2.3 主要结果及其证明
    2.4 应用
第3章 广义Farey图的生成树的计数
    3.1 引言
    3.2 主要结果及其证明
第4章 Foster定理的一个简单证明
    4.1 引言
    4.2 主要结果
致谢
参考文献
在学期间科研成果情况



本文编号：2958048