完全图的生成树中的完全m叉树

陈晓杰



完全图的生成树中的完全叉树

陈晓杰

(中国矿业大学 理学院, 江苏 徐州, 221008)

在完全叉树中, 假设其叶数为, 分支点数为, 则(-1)=-1. 证明了完全图的生成树中的完全叉树的个数和构造是有规律的, 而且当完全图的顶点数固定时, 其生成树中的完全叉树的个数就被固定, 构造也有规律可循, 且当为偶数时, 生成树中不含有完全偶数叉树.

完全叉树; 完全图; 生成树

定义1 除根之外, 度>1的顶点称为分支点[1].

1 引理

2 定理

[1] 徐俊明. 图论及其应用[M]. 合肥: 中国科学技术大学出版社, 2004: 1-100.

[2] 任韩. 图论[M]. 上海: 上海科技教育出版社, 2009: 1-90.

[3] 林翠琴. 组合学与图论[M]. 北京: 清华大学出版社, 2009: 1-90.

Completebinary trees of complete graphs′ spanning trees

CHEN Xiao-jie

(School of Science, China University of Mining and Technology, Xuzhou 221008, China)

In completebinary trees, the number of leaves is, the number of branch points is. Then (-1)=-1, it is proven that the number and structure of the completebinary trees of the complete graphs' spanning trees are regular, and the structure regular is in relation to the vertices of the complete graphs when the number of the vertices of the complete graphs is fixed, the number of the completebinary trees of the spanning trees is fixed, and the structure is regular, whenis even, there’s no complete even binary tree.

completebinary tree; complete graph; spanning tree

10.3969/j.issn.1672-6146.2011.03.001

O 221.1

1672-6146(2011)03-0001-02

2011-07-28

陈晓杰(1987-), 女, 硕士生, 研究方向为运筹学与控制论. E-mail: chenxiaojie_1987@163.com

(责任编校: 刘晓霞)