在全光网络中，波分复用(Wavelength Division Multiplexing)网络技术在现实的通信世界中扮演着基础和决定性的角色． 若把网络看作一个图的模型，对于网络中的每一个通讯请求，如果每一个通讯请求恰好只有网络中的两个节点组成(一个源信号节点和一个接收信号节点)，那么在图模型中需要选择一条路当作它的通讯频道来满足其通讯请求．而对于所有此类通讯请求，需要在图模型中选定一系列通路来实现网络中的通讯请求，这些通路就组成了这组通讯请求的一个路由． 通常在实际的通讯网络中一个通讯请求含有网络中两个以上的节点，所以这种更普遍的情况是将这一系列通讯请求看作是图(或网络)中的一个超图，而其中每个通讯请求看作是此超图中的一条超边．为了实现这种通讯请求，对超图中每条超边需要确定一个路由算法来建立图(或网络)中一条虚拟通路或者说专用通路来连接此超边的每个节点，在确定这样一个路由算法中最重要的一点是使得图中的每条边上的最大阻塞度(congestion)最小，其中阻塞度为任意一条边上通过的通路的数量，此问题称作路由和波长(BLWA)分配问题． 如果将网络限定在一个环网络中，问题变为确定一个路由算法来实现超图在此环中的通讯请求，并且使得此环中任意一边上的最大阻塞度最小．此问题称作最小化超图嵌入圈的最大阻塞度(MCHEC)问题．此问题的结果在实际生活中应用广泛，例如在并行计算问题中，并行计算机的处理器可以代表是超图的所有顶点，其中需要互相传递信息的各组处理器看作是一条超边，MCHEC问题的最优解对每一组内所有处理器之间的通讯确定了一个路由算法使得计算机之间的最大阻塞度最小． 本论文主要研究来源于WDM网络带宽分配问题的几个超图嵌入问题，对两类有较深应用价值的网络结构：树环网络和环圈网络，考虑了其超图嵌入问题；而后讨论了有关加权有向超图在网络中的嵌入问题，以及图论中有向图的几个问题，共分为五章．第一章主要介绍了WDM网络的一些相关的最优化问题，关键定义和相关结论，以及一些有向图问题的来源和相关结论． 在第二章我们简化了MCHEC问题的算法，用新的方法证明了几个关键引理并且分别给出MCHETR(超图嵌入树环)问题和MCHERC(超图嵌入环圈)问题的PTAS算法． Ganley和Cohoon提出了MCHEC问题并且证明了此问题为NP-完备的． 定理1[51]MCHEC问题为NP-完备的． MCHEC问题存在一个PTAS算法[20]．在算法进行过程中我们将超边分为两部分来嵌入：R<,i1,i2，..ik>和U<,i1,i2，..ik>对不同的U=｜U<,i1,i2，..ik>｜超边的嵌入又分两种情况来讨论． 当超边的数目为一个小数目时，利用穷举的方法易证MCHEC问题的PTAS算法是存在的． 定理2[20]对任意的常数C>O，当超边的数目u≤C(log n)时，U<,i1,i2，..ik>中的超边嵌入到圈中存在一个PTAS算法．特别地，对任-ε>0，一个(1+ε)近似比的近似结果可以在O(n<(C+1)>/ε>)时间内找到． 应用线性放松和反随机方法来近似的解决超边为大数目时的MCHEC问题．可得如下定理． 定理4[20]当超边数目m足够大，且Copt≥cm(0