一个边染色图称为单色的，如果它的所有边都有相同的颜色，而一个边染色图称为杂色的，如果它的任意两条边的颜色均不相同。一个r-边染色图G的单色树分解数定义为最小的整数k，使得只要用r种颜色对图G的边进行染色，都存在k个点不交的单色树覆盖图G的所有顶点。r-边染色图G的单色圈分解数和单色路分解数可以同样的方法定义。 本文分为两部分，第一部分主要考虑边染色图的单色子图划分问题，第二部分主要考虑边染色图的杂色子图划分问题。 第一部分由第二和第三章组成。第二章我们考虑如下优化问题：给定一个r-边染色图G，求最少个数的顶点不交的单色树、圈或路，覆盖图G的所有顶点(文中分别简称为PGMT、PGMC和PGMP问题)。对于这三个问题我们有如下结果： 1.PGMT问题是一个NP-完备问题，并且不存在常数因子的近似算法，除非P=NP。实际上，我们证明了：对于二部图，PGMT问题仍然是一个NP-完备问题。 2.PGMC问题是一个NP-完备问题，并且不存在常数因子的近似算法，除非P=NP。 3.PGMP问题是一个NP-完备问题，并且不存在常数因子的近似算法，除非P=NP。 若r为一个固定的整数，我们把r边染色图的PGMT、PGMC和PGMP问题分别称为r-PGMT、r-PGMC和r-PGMP问题.对单色子图分解的问题有如下了更强的NP-完备性结果。 4.对于任何固定的整数r≥5，r-PGMT问题是一个NP-完备问题。 5.对于任何固定的整数r≥5，r-PGMC问题是一个NP-完备问题。 6.对于任何固定的整数r≥5，r-PGMP问题是一个NP-完备问题。 第三章主要考虑2-边染色的完全多部图中单色子图划分问题，有如下的结果。 7.对于完全多部图，2-PGMP问题仍然是NP-完备问题。因此，2-PGMP问题是NP-完备问题。 8.对于完全多部图，2-PGMC问题仍然是NP-完备问题。因此，2-PGMC问题是NP-完备问题。 9.对于完全多部图，2-PGMT问题是一个P-问题，即可以在多项式时间内求解。 根据结论9的证明，我们不仅可以在多项式时间内找到2-边染色完全多部图的一个最优单色树分解，而且可以给出它的单色树分解数的显性表达式(首先由Kaneko，Kano和Suzuki[30]证明)的一个更自然的证明。 第二部分由第四和第五章组成。首先，对应于单色树、圈、路分解数的概念我们引入r-边染色图G的杂色树、圈、路分解数的概念，定义为最小的整数k，使得只要用r种颜色对图G的边进行染色，都存在k个顶点不交的杂色树、圈、路覆盖图G的所有顶点。 第四章主要考虑边染色完全多部图的杂色树分解数问题。Kaneko，Kano和Suzuki[30]对r-边染色完全多部图的单色树分解数仅仅解决了r=2的特殊情形，而我们对一般的整数r彻底解决了r-边染色完全多部图的杂色树分解数问题。尽管我们没有能够给出其显性表达式，我们构造了两种典型r-边染色，据此 10.我们可以在多项式时间内求出r-边染色完全多部图的杂色树分解数的值。作为推论，完全图和完全二部图的杂色树分解数则可以给出显性表达式。 类似单色子图划分的情形，第五章我们考虑如下优化问题：给定一个r-边染色图G，求最少个数的顶点不交的杂色树、圈或路，覆盖图G的所有顶点。我们分别称之为Minimumheterochromatictree，cycleandpathpartition问题。我们证明如下结果。 11.Minimumheterochromatictree(cycle)partition问题为NP-完备问题，并且不存在常因子的近似算法，除非P=NP。实际上，我们证明了：对于二部图，Minimumheterochromatictreepartition问题仍然是NP-完备的。 12.对于2-边染色图，Minimumheterochromaticpathpartition问题为NP-完备问题；因此，对于一般图Minimumheterochromaticpathpartition问题为NP-完备问题.由此结论还可得到：对于2-边染色图，Minimumheterochromatictreepartition问题为NP-完备问题。