用母函数求解图的生成树问题  

A new method of extracting spanning trees by home function

作　　者：高静[1] 李实秋[1] 陈云[2] 

机构地区：[1]重庆邮电大学通信与信息工程学院,重庆400065 [2]重庆邮电大学计算机科学与技术学院,重庆400065

出　　处：《重庆邮电大学学报（自然科学版）》2007年第B06期167-169,共3页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

摘　　要：如何精确求解出图的全部生成树,是图论研究的重要课题之一。引入组合数学的母函数原理,结合图论相关理论,提出了一种求图的全部生成树的新方法,该方法易于在计算机上实现,能精确求解连通图的生成树数目及其全部生成树,快速找出带权图的最小生成树,并给出了严密证明。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.

关 键 词：母函数 生成树 最小生成树 

分 类 号：O233[理学—运筹学与控制论]