论文部分内容阅读
图的Laplace矩阵和Tutte多项式都是研究图的性质的重要工具,关于这两方面的研究都已经有了大量的结果,最近提出了一个建立在连通图上的游戏模型,称之为筹码发射游戏(Chip-firing game),它与图的Laplace矩阵以及Tutte多项式都有着紧密的联系,本文主要介绍与之相关的一些结果。本文共分为四章第一章介绍了文中所涉及的内容的基本概念,图的基本概念及相关的定义以及几种乘积图的概念,Laplace矩阵和Tutte多项式的定义及几个重要的性质。第二章介绍了图的Laplace矩阵及其边形式在幺模相合及幺模相抵下的性质,并完全刻画了能够幺模相合到其Smith标准型的简单图。第三章介绍连通图上的筹码发射游戏,以及它的变形美元游戏,讨论了游戏的性质,介绍了由美元游戏中的临界态构成的临界群,并给出了临界态与支撑树集合之间的——对应关系,最后介绍了临界态数目与Tutte多项式系数的一些关系。第四章为临界群的具体计算,总结了在计算中所用到的生成元方法,介绍了之前得到的关于一些图的临界群,并刻画了几类笛卡尔乘积图的临界群,证明了笛卡尔乘积图Km×Pn的临界群始终是m-1个循环群的直积,并给出了笛卡尔乘积图Km×Cn以及C5×Cn的表达式.最后一节给出了一些关于全连边乘积图的临界群的结论。