【作者】 韩娜；

【导师】 梁志和；

【作者基本信息】 河北师范大学 ， 基础数学， 2008， 硕士

【摘要】 本文考虑的是由WDM网络的生存性设计所引发的满足DRC条件的圈覆盖问题．所谓DRC条件是将WDM网络中的”需求”在子网络上分配路径，使这些子网络保持相互独立．这个问题可被叙述如下：对于一个给定的图G，找到λK_n(λK_n,n)的边集的圈覆盖,其中V（λK_n）=V（G）(V(λK_n,n)=V（G）)，覆盖中的每个圈相对于G来说满足DRC条件，也就是说；对λK_n(λK_n,n)中的每条边对应G中一条路径，覆盖中的每一个圈中的边集所对应的路是顶点不交的．我们的目的是将覆盖中的圈数最小化．Jean-Claude Bermond等人在文献[1]中提出两个公开问题:当物理图G=C_n是—个大小为n的环并且逻辑图为λK_n或λK_n,n时,λK_n或λK_n,n的DRC覆盖的最小圈数为何值?对于这个问题，我们给出了最优解决方案，并且解决了有向图λK_n^*(λK_n,n^*)的DRC覆盖问题．更多还原

【Abstract】 This paper considers the cycle covering of complete graphs motivated by the design of survivable WDM networks, where the requests are routed on sub-networks which are protected independently from each other. The problem can be stated as follows:for a given graph G, find a cycle covering of the edge set ofλK_n (λK_n,n), where V（K_n）=V（G） (V(K_n,n)=V（G）), such that each cycle in the covering satisfies the disjoint routing constraint （DRC）, relatively to G.In other words: to each edge ofλK_n (λK_n,n) we associate in G a path and all the paths associated to the edges of a cycle of the covering must be vertex disjoint. We want to minimize the number of cycles in the covering. In[1], Bermond rised two problems: when we consider the case where G = C_n, a ring of size n and logical graph isλK_n orλK_n,n, how many cycles are needed at least? For the two problems, we give optimal solutions as well as for variations of the problem, namely, its directed version.更多还原