完全圖的生成樹中的完全m叉樹

陳曉杰

?

完全圖的生成樹中的完全叉樹

陳曉杰

(中國礦業(yè)大學 理學院, 江蘇 徐州, 221008)

在完全叉樹中, 假設(shè)其葉數(shù)為, 分支點數(shù)為, 則(-1)=-1. 證明了完全圖的生成樹中的完全叉樹的個數(shù)和構(gòu)造是有規(guī)律的, 而且當完全圖的頂點數(shù)固定時, 其生成樹中的完全叉樹的個數(shù)就被固定, 構(gòu)造也有規(guī)律可循, 且當為偶數(shù)時, 生成樹中不含有完全偶數(shù)叉樹.

完全叉樹; 完全圖; 生成樹

定義1 除根之外, 度>1的頂點稱為分支點[1].

1 引理

2 定理

[1] 徐俊明. 圖論及其應(yīng)用[M]. 合肥: 中國科學技術(shù)大學出版社, 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

(責任編校: 劉曉霞)