摘要
如何精确求解出图的全部生成树,是图论研究的重要课题之一。引入组合数学的母函数原理,结合图论相关理论,提出了一种求图的全部生成树的新方法,该方法易于在计算机上实现,能精确求解连通图的生成树数目及其全部生成树,快速找出带权图的最小生成树,并给出了严密证明。
Extracting Spanning Trees in a graph is one of the important contents of graphic theory studying. This paper introduces a new method of extracting all spanning trees and its argument. This method combines Home function theories and Graphic theory theories, with which can count the spanning trees and extract all the spanning trees accurately in connective graph, and also can find out the least spanning tree quickly in weighted graph. It is easy to realize in computer.
出处
《重庆邮电大学学报(自然科学版)》
2007年第B06期167-169,共3页
Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)
关键词
母函数
生成树
最小生成树
home function
spanning trees
least spanning tree