摘要
给出了生成子图和生成子图的计数定理。证明了生成子图的构造定理。提出了任意完全图Kp的生成树的计数方法和构造方法。给出了生成子树的计数公式。利用生成子圈的计数方法,寻找生成子图的生成树,证明了生成树的构造定理和计数定理。同时介绍了完全图K5的含圈生成子图及不含圈的生成树的计数和构造。生成树的计算公式过于庞大,且仅适用于完全图的Kp。平图例子验证了构造定理和计数定理的实用性和有效性,是构造一个完全图的生成树的简单易行的方法。
In this paper, spanning subgraphs and its counting theorem are given. The construction theorem of spanning subgraphs is proved. The methods of counting and constructing spanning subgraphs in an arbitrary complete graph Kp are proposed. Use the methods of spanning subcycle, find the spanning trees of spanning subgra^hs, and prove the counting theorem and construction theorem of spanning trees. In the meanwhile, the counting and construction of a complete graph Ks with and without cycle spanning tree ring are introduced. The calculation formula of spanning tree is very large, thus only applicable to complete graph Kp. Level diagram example shows the practicality and effectiveness of the construction theorem and counting theorem, which is a simple and easy method to construct a complete graph of the spanning tree.
出处
《沈阳师范大学学报（自然科学版）》
CAS
2010年第3期327-330,共4页
Journal of Shenyang Normal University:Natural Science Edition
基金
国家自然科学基金资助项目(10471096)
关键词
完全图
生成子图
生成树
构造
计数
complete graph
spanning subgraph
sparming tree
construction
counting
