论文分三部分,第一部分讨论无向环和无向环形树的负载问题,包括第一,二章：第二部分讨论有向环和有向环形树的路径选择问题,包括第三,四章。第三部分提出改进的有向环负载问题的多项式时间近似方案,包括第五章。　　环形树在通讯网络中有着广泛的应用。一个环形树G是一个由一棵树T得到的图：把树的每个顶点换成一个环(叫做顶点环),然后收缩树的边,使得两个对应于一边的两个顶点的环有且只有一个相同的顶点,且没有三个顶点环共用一点。(一个更广的定义允许三个环共用一点)。第一,二章的问题是,给定一个要求的集合,D={d(i,j),i,j∈V(G)}每个要求是定义在一对顶点之间的一个非负实数。在同一个环上,每对顶点之间的所有要求必须且只能在两条可能道路中选择同一条道路来输送。算法的目的是找出一个路径选择方案,对每个要求,在环形树上找出一条路来满足它,且使得环形树上的各边的最大负载最小化,在这里一条边的负载指的是通过这条边的所有路的要求值之和。我们提出一个多项式时间近似方案来解决此问题。　　对于这个问题,主要有以下结果：　　算法2.1：环形树负载问题的多项式时间近似算法　　定理2.1：算法2.1是一个多项式时间近似方案　　定理2.2 程序结束时每个要求所对应的两点之间的路径是唯一的。　　第三,四章讨论有向环和有向环形树的负载问题。有向环形树由有向双环构成,构造方法与环形树的构造方法相同。只是把原来无向环形树上的每个无向环Ci换成有向双环,即两个方向相反的有向环Ci_+和Ci_-。对有向环形树的路径选择问题,主要有以下结果：　　算法4.1有向环形树的路径选择的多项式时间算法　　定理4.1：算法4.1是一个多项式时间算法。　　有向环和有向环形树需要在适当的位置安装波长转换器。对有向环形树的转换器安排方案,主要有如下结果　　定理4.3：所有枢纽点集合对有向环形树是足够的