最优化光纤通信问题已经成为很多大学里光电通信技术课程的必不可少的部分。在光纤最优通信中,波分复用(WDM)技术是为了使若干独立信号能在一条公共光纤通路上传输,而将其分别配置在分立的波长上的复用。波分复用技术在远程通信中扮演着极其重要的作用。在上个世纪九十年代,WDM技术的发展革命性地推动了光电产业的进步。同时引发了许多新兴的有挑战性的优化问题。如波长分配和路染色问题,波长转换问题,请求排序问题和环负载问题等。如果我们把通信网络模拟成一个图,对于通信中的每个请求,其中,一个通信请求是网络中的两个顶点：一个源信号顶点和一个接收信号顶点,我们需要在网络上选择一个通信信道来满足这个通信请求。而对于所有此类的通信请求,我们需要在模型图中选择一系列的通路来实现网络中的通信请求。满足这些通信请求的所有通路的集合就构成了网络中的一个路由。但是在实际生活中,每个通信请求包含两个或者两个以上的网络中的顶点,因此我们可以把这些通信请求模拟成一个超图,每个通信请求是超图的一条超边。我们希望找到一种路由算法来满足这些通信请求。也就是,我们希望找到网络中的一个通信路由来连接超边上的每个顶点。在设计这样一种路由算法的过程中,最重要的问题是：使得网络图中每条边上的最大阻塞最小。其中阻塞是指每条边上通过的通路的数目。这个问题被称作：路由和波长(RWA)分配问题。现在我们考虑RWA问题的一种常见情况：我们将通信网络限制在一个圈网络中,那么我们将得到一类被称为：最小化超图嵌入圈的最大阻塞(MCHEC)问题。这类问题在现实生活中有着广泛的应用,已经引起很多研究者的兴趣。而MCHEC问题的赋权情况是一个崭新的问题,也是一个更难的问题。例如,我们给超图的每条边或者圈的每条边赋一个权重。显然这类问题在实际生活中的应用更加的普遍。在本文中,我们第一次提出了：最小化超图嵌入带权圈的最大阻塞(MCHEWC)问题。在实际生活中,通信请求可能会是有方向的(源‘顶点和接收顶点),所以超图的每条边可能是有方向的,所以在本文中,我们也考虑了超图嵌入这一类问题的有向情况。MCHEC问题已经被证明是NP-完备问题,因此以上所提到的MCHEC问题的延伸问题,如加权情况,有向情况,显然也是NP-完备的。对于NP-完备问题,我们感兴趣的是,设计出此类问题的多项式时间近似方案。在本论文中,我们考虑了MCHEC问题的一些一般性情况,例如加权,有向。我们分别给出了这些情况下的多项式时间近似算法。论文可分为五个部分：在第一章我们主要介绍了MCHEC问题的相关背景,MCHEC问题的来源,算法的一些基本定义,与MCHEC问题有关的最优化问题和这类问题目前的研究进展。在第二章中,我们第一次提出：最小化超图嵌入带权圈的最大阻塞(MCHEWC)问题,并且我们给出了MCHEWC问题的两种非常简单的,高效的,两倍的近似算法。首先,我们把MCHEWC问题归结为整数线性规划问题(NILP*),然后利用解它的松弛问题和有界启发可以得到一个2倍的近似解。然后我们又设计了一个非常简单有效的线性时间近似算法,这个算法也可以得到和前一个算法(通过解整数线性规划问题的放松问题)一样好的近似解：最差情况下得到的近似解是最优解的两倍。定理0.0.1.以NILP*为基础的rounding算法给出的最大阻塞,最多是MCHEC,MCGEWC(图嵌入带权圈)和MCHEWC问题最优解的两倍。定理0.0.2.最大权重连接边移除算法给出的最大阻塞,最多是MCHEC,MCGEWC和MCHEWC问题的最优解的两倍。在第三章中我们继续深入研究了MCHEWC问题,我们给出了MCHEWC问题的一个多项式时间近似方案(PTAS),彻底解决了这一问题。在这个多项式时间近似算法中,我们首先把超图的超边集合和圈的边集合分别分为两部分,在这两部分上使用不同的方法。主要思想是类似于穷举法和解整数线性规划问题(ILP)的放松问题,反随机方法和其他的一些技巧。我们证明了如下引理：引理0.0.3.令X1,X2,...,Xn为n个独立的0-1随机变量,其中Xi以概率pi,0<pi<1取1。令X=∑in=1 aiXi,0<ai≤1,μ-E[X]。则对任意的0<δ≤1/2,Pr(X>μ+δn)<exp{-1/3nδ2}。我们得到如下的定理：定理0.0.4.存在MCHEWC问题的一个多项式时间近似方案。在第四章中我们考虑了将有向超图嵌入树环(DHETR)的问题。这个问题也是NP-完备的,我们给出了它的一个多项式时间近似方案。定理0.0.5.存在DHETR问题的一个多项式时间近似方案。在第五章中,我们第一次提出了最小化带权超图嵌入带权圈的最大阻塞(MCWHEWC)问题。这个问题是最小化超图嵌入圈的最大阻塞问题的最一般性问题,也是最难的问题。迄今为止,没有人研究这一类问题。据我们所知,至今,最好的近似算法是Ho和Lee[16]提出的最小化带权超图嵌入圈的最大阻塞(MCWHEC)问题的1.5倍的近似算法。在本章中,我们对超边的权重给了一个非常合理的限制,在这个限制下,给出了MCWHEWC问题的一个多项式时间近似方案。定理0.0.6.如果我们给超边的权重一个限制：最大权重与最小权重的比值小于某一个正常数,则MCWHEWC问题存在一个多项式时间近似算法。本论文的每一章的内容都是有关MCHEC问题的新问题,并且我们都给出了解决方案。从某些方面来说,我们彻底解决了有关MCHEC的这一系列问题。