有关树的若干计数问题的研究

研究各类树的计数一直是组合学中的经典问题，美国科学院院士Stanley的著作“Enumerative Combinatorics”进行过重点关注。它具有丰富的组合结构，在许多领域有重要应用。生成树的数目与统计物理中q-状态Potts模型的配分函数密切相关，也是衡量网络可靠性的一个最自然的参数之一。许多电网络中的问题可以转化成树的计数问题的研究。本项目主要研究以下问题：.1.研究Ehrenborg关于二部图G=(U,V)的生成树数目以其所有顶点度的乘积除以|U||V|为上界的猜想及其相关问题。.2.研究电网络中与生成树的计数理论相关的新方法。.3.应用电网络与生成树的计数理论，研究图上随机游动的各种参数的计算与估计。. 本项目预期成果将发展与丰富树的计数理论与电网络理论，为统计物理的一些研究对象提供数学理论依据，具有学科交叉性质和多方面的应用。

It has been a classical problem in combinatorics to study the enumeration of trees with some properties. Stanley, a member of American Academy of Sciences, paid attention to it in his famous books "Enumerative Combinatorics". It has rich combinatorial structures and important applications in many fields. The number of spanning trees is related closely to the partition function of the q-state model in statistical physics. It is also one of the most natural parameters to measure network reliability. Many problems in electrical networks can be studied by use of counting trees. This project will study the following problems: .1.Study the Ehrenborg's conjecture: the number of spanning trees in a bipartite graph G=(U,V) is bounded by the product of degrees of vertices divided by |U||V|, and related problems to it. .2.Study the new methods related to enumerative theory of spanning trees in the electrical network. .3.By using the electrical network and enumerative theory of spanning trees, study applications such as computing some parameters in random walks of graphs. . This project will develop and enrich the counting theory of trees and electrical network theory, and it will provide mathematical theory basis for some research objects in statistical physics and has interdisciplinary properties and applied background.