非平凡树的最小路分解数

(长江大学信息与数学学院，湖北 荆州 434023) (湖北省洪湖市第一高级中学，湖北 洪湖 433200)

笔者讨论的图均为没有重边的简单图。对图G，用|V(G)|和|E(G)|分别表示图G的顶点数和边数。一条从x0到xk的路径P表示为P=x0x1…xk，其中Pxi=x0…xi,xiP=xi…xk。用Pk表示图中包含k个顶点的路径，其长度为k-1。如果图G的边集E(G)可以分解为若干边不重合的子图H时，就称G有H分解，若H={P1,P2,…,Pk}，则称图G有路分解，令p(G)=min{||:是G的一个路分解}，即图G的路分解的最小条数，设是G的一个路分解，若||=p(G)，则称是图G的一个最小路分解。设v是图G的一个点，dG(v)表示图G中与点v相关联的边的条数，称为点v的度。一个连通且没有圈的图称为树，通常用字母T来表示树。其中仅有一个点构成的树称为平凡树，否则称为非平凡树。树T中度为1的点称为悬挂点(叶子)，通常用L(T)表示树T中叶子的集合，与它相关联的边称为悬挂边。设x是任意的实数，[x]表示不超过x的最大整数，┌x┐表示不小于x的最小整数。所涉及的相关符号见参考文献[1] 。

1 相关引理

图1 dT(v)为偶数 图2 dT(v)为奇数

引理2设是树T的一个最小路分解，∀v∈V(T)。若dT(v)为偶数，则在中不存在以点v为端点的路径；若dT(v)为奇数，则在中必存在以点v为端点的路径。

另一方面，当dT(v)为奇数时，假设中不存在以v为端点的路径，那么过v点的每条路都会经过与v相关联的2条边，从而与v相关联的边数为偶数，这与dT(v)为奇数相矛盾。

引理3设T是一个树，且T′=T-{u}，其中u∈L(T)，则有p(T)≥p(T′)。

p(T′)≤t-1=p(T)-1

p(T′)≤t=p(T)

综上所述p(T)≥p(T′)。

2 主要结论

证明T是非平凡的，故|T|≥2。用数学归纳法证明。

当|T|=k时，不妨取u∈L(T)，点u在T中的邻点记为v。令T′=T-{u}，则有|T′|=|T|-|{u}|=k-1

1)当dT′(v)为奇数时，由引理2，在T′的最小路分解中，必有一条路P∈是以v为端点，此时构造一条路径P′使得P′=P+vu，则′=-P+P′是T的路分解。故有：

p(T)≤|′|

2)当dT′(v)为偶数时，由引理2知，在T′的最小路分解中，不存在以v点为端点的路径。设P∈是一条通过v的路径，不妨令P={…wvt…}，由P及u构造2条路径则为T的路分解。可得：

p(T)≤|′|

由引理3知，p(T)≥p(T′)，当dT′(v)为偶数时，即dT(v)为奇数，则取等号不成立。

综上即有：

p(T′)

故：

3 应用

例1某个树T的结构如图3，求树T的最小路分解数。

由定理1易知在度为1和2的点上结果为0，故现只讨论度大于2的点的情况。

=1+1+2+1+1+1+1=8

图3 最小路分解数为8的树

注1一个树最小路分解的数目与该树的叶子数无关。

不难看出,图4和图5中其叶子数目都是6，但是在图4中最少分解路为4，而在图5却为3。由此得出，结论树最小路分解的数目与该树的叶子数无关。

图4 最小路分解数为4的树 图5 最小路分解数为3的树

4 结语

研究了树可分解路的最小条数，这一结论为一般连通图中的路径的研究奠定基础，在图论的结构理论研究中有着重要的意义。由树的路分解，进一步可以研究树的路因子理论，这将是以后的重点研究对象。