论文部分内容阅读
本文主要研究树的L(2，1)标号问题．通过对树枝段的性质的研究给出一些结构的性质．文章最后研究了任意最大度的树，并给出了树为一类的充分条件．
设v0vt…vkvk+1为最大度为3的树中一条路，当d(v0)=d(vk+1)=3，d(vi)=2(1≤k)时，我们称这段路为树枝段，并且根据它2度点的个数k称此段为Sk．第二章中给出了树枝段的性质，包括禁i段，允i段，满i的，全满的等。这些性质直接决定了树枝段在树的L(2，1)标号问题中的作用及影响．
1：证明了S6是满4的，Sk(k≥7)是全满的；
2：任何Sk1(k1=2或k1≥4)与Sk2(k2≥5)的链接以及Sk(k≥7)都是全满的，从一端开始的第一个2度点以及在另一端的最后一个2度点均可以取到E={2，3，4)中任何一值．因此在树中标号的传递性上没有影响．树中出现这种结构时可以将其删去，截断处用树叶代替而分成两棵树T1与T2；仅当其均为第一类时原树为第一类的。
3：给出计算F(i，k1，k2)(Sk1与Sk2 链接后的4-L(2，1)标号中1号位被标为i时最后一位可能的标号集合)的表达式(定理2.2.2)，给出推论F(i，k1，k2)()f(i，k1+k2+1)(推论2.2.2)．
第三章中给出：
4：若3度树中的所有树枝段Sk有k≥2且不含两个S3与一个Sk(k=2，3，4，5，6)交于一点的结构，则该树属于第一类的。
5：给出了3度树的L(2，1)标号等价分解的定义．给出了I型结构的分解规则以及11类共24个可以分解的结构，如果树中出现此种结构可以将树从此处分解成两个或多个小树．对树进行分类仅需判断所有小树即可．
6：对任意最大度的树进行了研究．证明了，对最大度△≥4的树当任意最大度点之间距离不为1或2且任意顶点v至多存在△-3个最大度点与其距离为2则该树为第一类的。