论文部分内容阅读
以经典的生成树的生成与计数问题为研究背景,运用图的矩阵表示和破圈理论研究了连通图含某些指定边的生成树的生成与计数问题。 第一,提出并讨论了连通图含某些指定边的生成树的环和矩阵生成法.在给出环补关联矩阵与环和矩阵等定义的基础上,给出并证明了连通图含某些指定边的生成树的生成方法——环和矩阵法. 第二,介绍了一种求图的含某些指定边的生成树的按类生成法.首先选取图的含所有指定边的任意一棵参考生成树,利用其它含所有指定边的生成树与参考生成树的距离,把除参考生成树之外的所有含所有指定边的生成树最多分成d类.然后给出并证明了这种分类生成树与基本可破圈及基本可破圈的环和的关系.从而证明了这种按类生成法能够生成图的含所有指定边的全部互异的生成树。 第三,讨论了连通图含某些指定边或含指定边中一条且仅一条边的全部生成树的计数问题.给出了一个连通图含k-爪或含k-爪中一条且仅一条边的全部生成树的数目公式.并例示了应用公式求一个连通图含k-爪或含k-爪中一条且仅一条边的全部生成树的数目。