一类无向图的生成树数目及其渐近性分析

发布时间：2018-11-10 11:37

【摘要】：图论中关于图的生成树数目的研究有很长的历史.它在众多领域,例如,网络的可靠性分析,物理学上电路的设计等有广泛的实际应用[6,10,14].因此,研究图的生成树数目及其渐近性质有重要的理论和实际意义.近年来无向循环图倍受关注[2,8,13,27,28],本文致力于研究这类图的生成树数目及其渐近性质.针对一类特殊的循环图,本文主要讨论它的生成树数目与其参数之间的关系式,并深入探讨了它的生成树数目的整体性质.首先,本文推导了上述循环图的生成树数目简单精确的计算公式,实现了由图的一些简单参数便可以直接求得其生成树数目,改进了计算循环图的生成树数目的方法.其次,分析了生成树数目的渐近性质,给出了生成树数目的渐近值的计算公式,其中为整数,,表示最小公倍数.这一渐近值表示生成树数目的平均增长率[13].由此可以精确计算出这类循环图的生成树数目的平均增长率,克服了之前公式不易直接计算得到精确值的缺点,在很大程度上简化了计算,便于实际的应用.最后,讨论了生成树数目的渐近值的最值问题,证明了此渐近值具有单调递增性质,进一步刻画了该类循环图的生成树数目平均增长率的性质,具有一定的理论和实际应用价值.
[Abstract]:The research on the number of spanning trees in graph theory has a long history. It has a wide range of practical applications in many fields, such as network reliability analysis, physics circuit design and so on. Therefore, it is of great theoretical and practical significance to study the number of spanning trees and their asymptotic properties of graphs. In recent years, undirected cyclic graphs have attracted more and more attention. In this paper, the number of spanning trees and their asymptotic properties of undirected cyclic graphs are studied. For a special cyclic graph, this paper mainly discusses the relationship between the number of spanning trees and its parameters, and discusses the global properties of the number of spanning trees. First of all, this paper deduces a simple and accurate formula for calculating the number of spanning trees of the above cyclic graphs. It is realized that the number of spanning trees can be directly obtained from some simple parameters of a graph, and the method of calculating the number of spanning trees of a cyclic graph is improved. Secondly, the asymptotic properties of the number of spanning trees are analyzed, and the formula for calculating the asymptotic value of the number of spanning trees is given, in which the number of spanning trees is an integer, representing the minimum common multiple. This asymptotic value represents the average growth rate of the number of spanning trees [13]. Thus, the average growth rate of the number of spanning trees of this kind of cyclic graphs can be calculated accurately, which overcomes the shortcoming that the previous formulas are not easy to directly calculate the exact values, and simplifies the calculation to a great extent, which is convenient for practical application. Finally, the problem of the asymptotic value of the number of spanning trees is discussed, and the monotone increasing property of the asymptotic value is proved. The properties of the average growth rate of the number of spanning trees of this kind of cyclic graphs are further characterized. It has certain theoretical and practical application value.
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】