广义完全多部图的生成树个数

摘要

谱图理论主要是对邻接矩阵和Laplacian矩阵矩阵的代数性质和组合性质进行研究。图的邻接矩阵的谱的研究最早是在量子化学研究方面。图的Laplacian矩阵的谱的研究与邻接矩阵的谱的研究相比要早得多。1847年，G.Kirchhoff用图的Laplacian矩阵的谱来研究电流网络时，得出了著名的矩阵-树定理。本文应用矩阵-树定理的结果去计算广义完全多部图的生成树个数。众所周知在很多城市建设中的优化问题，比如在道路建设中我们往往喜欢找出即便利又经济的交通路线，那么这个问题的关键就是要找到最小生成树，所以说关于生成树的研究是有一定的实际意义的。
　　 本文第一章主要介绍了本文用到的基础知识和主要结论；第二章首先介绍了研究广义完全多部图生成树个数的一个新方法，然后用这个方法重新求出了已有的扇型广义完全多部图的生成树个数，随后求得了轮子型的和圈型的广义完全多部图的生成树个数；第三章首先对图的生成树的个数的界做了个综述，然后对一般广义的完全多部图的生成树个数的界进行了刻画。