摘要每个分支是路的森林称为路森林。如果一族路森林的边集合可以构成图 的一个边分解，则称这族路森林为图 的路分解。在图 的路分解中最小的路森林的个数称为图 的线性荫度，记为 。如果我们限制每条路的边数最多为 ，则我们得到一个特殊分解，在这种类型的分解中路森林的最小个数称为线性 荫度，记为 。 本文研究图 的线性 荫度。首先介绍一些简单图如：圈、路、星等图形的线性 荫度。然后，给出完全图 和完全二部图 的线性 荫度的值。最后给出不含相交 圈的平面图的线性 荫度的一个上界，此上界改进了文献[12，13]中的结果。43698
毕业论文关键词： 线性 荫度，圈，路，星，树，完全图，完全二部图，平面图
ABSTRACT A forest in which every component is path is called a path forest. A family of path forests whose edge sets form a partition of the edge set of a graph is called a path decomposition of a graph . The minimum number of path forests in a path decomposition of a graph is the linear arboricity of and denoted by . If we restrict the number of edges in each path to be at most , then we obtain a special decomposition. The minimum number of path forests in this type of decomposition is called the linear arboricity and denoted by , In this paper we will study the linear arboricity of graph . In chapter ， we give the linear arboricity of cycle, path, star and tree, and complete graph and complete bipartite graph . In chapter 3, giving an upper bound of the linear arboricity of planar graphs with no interesting cycle. This improves the results in [11],[12].
Keywords：the linear arboricity, cycle, path, star, tree, complete graph, complete bipartite graphs, planar graph.
目录
摘要 2
ABSTRACT 2
第一章 绪论 3
1.1 课题的目的及意义 3
1.3 基本概念及符号说明 6
1.3.1 基本概念 6
1.3.2 符号说明 7
1.4 用到的引理 8
第二章 几类简单图形的线性 荫度 9
2.1 路、圈、星、树的线性 荫度 9
2.2 完全图及完全二部图的线性 荫度 14
第三章 不含相交 圈的平面图的线性 荫度 23
参考文献 30
致谢 34 第一章 绪论
1.1 课题的目的及意义
运筹学分支中的图论在生活中应用广泛，它在包括物理学、化学、控制论、信息论、科学管理、电子计算机等重要领域范畴起着重要的作用．在实际生活中、生产和科学研究实践时，有非常多的要用到图论的理论和计算的方法来解决问题。图的染色可以解决许多实际中的问题例如时间表问题、分工表问题和运输问题。图的荫度理论是关于图的染色问题的理论的具体分析。同时图的染色问题里面的研究方向是从图的点染色到边染色。图的点染色是把图的点集分解成一些互不相交的点的独立集的具体方法，图的边染色就是把图的边集分解成一些互不相交的边的独立集的具体方法。然后人们考虑是否可以用其他形式把图的点集或边集分解成呢?首先考虑的是树,从而就产生了图的荫度理论。 几类特殊图形的线性2-荫度:http://www.youerw.com/shuxue/lunwen_44661.html