该文主要可分为两个部分,第一部分所讨论的问题是,k-匹配的子正交匹配分解及一些近似算法,包括第一章到第四章;第二部分是,路染色问题,包括第五章.在这一部分中,该文的主要结构是如下:第一章:引言部分简单介绍问题的应用背景,及一些基本概念,还有目前的一些主要结果和算法.第二章:将证明给定的图G是简单二部图,匹配M是图G一个完美匹配,则图G存在关于匹配M的正交匹配分解.并给出边集的一个关于M的正交匹配分解算法.第三章:将舍弃二部图的限制,讨论给定一个最大度为k的简单图G,M是G的一个完美匹配,寻找关于M的最小子正交匹配分解.第四章:在这一章中将给出(P)问题的一个最多需要2k-1次匹配的近似算法,并且讨论这种贪心算法的下界.在第二部分中,将主要讨论光网络中的路染色问题.路染色问题可以描述如下:在一个连通图G上,对于给定的一组路的集合P,给每一条路分配一种颜色,使得任意有公共边的两条路分配不同的颜色,目标是求最小颜色数.在光网络中,连通图G的拓扑结构是特殊的,根据光网络的常用拓扑结构,得到抽象的图G是树、环和树环等,该文就主要讨论在这三种特殊图G上的路染色问题.