图染色和网络算法设计与分析的一些新结果

发布时间：2020-03-22 03:29

【摘要】：图论是现代应用数学的一个重要分支,其研究对象通常是一张图G(V,E),这里V是图的顶点集合,E是图的边集合。经过一百多年的发展[17],图论已经演化为一个拥有众多分支领域诸如染色理论,拉姆齐理论,网络理论等的庞大家族。一方面,从纯粹基础理论研究的角度,推动图论不断发展的是其理论领域本身的内部矛盾。例如四色猜想就是最为重要的理论推动力之一。在攻克四色猜想的过程中,不断涌现出的新方法和新问题使得图的染色理论逐渐发展为图论中主要的研究领域之一。而四色猜想问题本身最终于1976年被K.Appel和W.Haken借助电子计算机所证明。另一方面,由于图本身所具有普适性,使得其被广泛的应用于表示和描述很多复杂的现实问题。因而很多由实际应用如通信网络中所产生的问题是推动图论不断发展的另一重要源泉。本论文分别从图论的理论和实际这两个角度出发,着重研究了染色理论中的Steinberg猜想和在实际的弹性光网络EON以及网络虚拟化中算法的设计与分析。在第一章中,我们首先介绍了Steinberg猜想及其发展现状,以及关于弹性光网络EON和网络虚拟化的相关背景。从理论方面,在第二章中,我们证明了平面图不含四圈和六圈是7/2可染的,这一结论说明了所有不含四圈和六圈的平面图的分数色数的上界不超过7/2。这一结论和Steinberg猜想有较为紧密的联系。在四色猜想被攻克以后,Richard Steinberg于1976年提出了如下猜想:Steinberg猜想:所有不含四圈和五圈的平面图是三色可染的。在16年之后,为了逼近这一猜想,Paul Erdos于1991年提出了对这一猜想的如下松弛:即确定这样的k的最小值(如果存在的话)使得所有不含4,5,…,k圈的平面图是三色可染的[32]。在2005年,Borodin等人证明了k≤7[92]。在2017年,V.Addad,M.Hebdige,D.Kral,Z.Li和E.Salgado 否定了Steinberg 猜想[93],即k5。因此,Erdos所提出的最小的k值是否等于6是最后没有确定的临界值。我们的结论对k=6成立提供了支持。在实际应用方面,随着万物互联时代的到来,世界范围内的通讯需求和多样化的实际应用需求呈现井喷式的发展。这场信息革命要求未来的通讯网络更加高效,智能,敏捷和可扩展。为了满足下一代通信网络的趋势,许多新兴的网络架构和网络技术例如弹性光网络EON和网络虚拟化已经不断的涌现。弹性光网络EON,由于其在光谱上的灵活性,被视为下一代光网络的标准架构。网络虚拟化则被视为克服目前互联网僵化问题的最为有前景的网络技术。伴随着这些新架构和技术而来的是很多亟待解决的新兴的图论问题,例如弹性光网络EON中的路由和频谱分配的RSA问题以及网络虚拟化中的虚拟网络嵌入的VNE问题。在第三章中,我们研究了弹性光网络EON中的路由问题。在这一问题的研究上,一直存在一个令人困惑的问题:那就是通信请求的分布和底层EON拓扑结构的变化是如何影响路由算法的。因为路由问题在整个RSA中起着决定性的作用,我们对分布和底层拓扑对于路由问题的影响进行了详细的理论分析。在研究过程中,我们提出了两条关键的理论作用链:(1)在EON中,路由算法的最优性是由其相应的冲突图的色数所决定,而冲突图的色数又与任意两条光路(由路由算法所决定)的相交概率成正比;(2)通信请求的分布和底层EON拓扑的影响可以被一个由冲突系数所构成的冲突矩阵所刻画。而基于冲突矩阵,任意两条光路的相交概率可以被一个二次型规划所决定。结合这两条理论链,我们刻画了通信请求分布和底层EON拓扑结构对路由算法的影响,并且给出了最优的路由决策和相关的近似算法。实际的数值仿真结果验证了我们所提出的理论链的有效性。在第四章中,我们对RSA中的频谱分配问题进行了研究。在路由阶段结束之后(所有的通信请求都已设定在其相应的光路上),任意两条光路之间如果经过了一条或多条相同的底层光纤,则为了减少相应的信号干扰以及保证通信的质量和安全,分配给他们的信号频谱应当在光谱上被一定的警戒带宽所隔离。而警戒带宽大小的设定则由任意两条光路的具体的干扰情况所决定。因此不同光路之间的警戒带宽的大小应当是根据实际情况而变化的。但目前相关的研究均把所有的警戒带宽设定为一致的大小,从而造成了巨大的频谱浪费。针对这种情况,本论文对提出了一种距离频谱分配的的DSA模型来对在警戒带宽大小变化的情况下的频谱分配进行研究。我们首先证明了 DSA问题是NP困难的,并对其的不可近似性进行了刻画。之后,通过与冲突图的色数和哈密顿路问题建立联系,我们给出的DSA的最优解的紧的理论上界和下界。为了高效的解决DSA问题,我们进一步提出了一个二阶段算法。算法的第一阶段产生一个DSA问题的初解,并且我们证明了该初解在一些图类中能达到最优解或保证一定的近似比。之后,算法的第二阶段采用一个随机划分算法对初解的结果进行了进一步的提升和改进。实际的数值结果证明了我们所提出的算法能得到较好的次优解,并且具有快速的运算时间和良好的可扩展性。虚拟网络嵌入的VNE问题是网络虚拟化中的最核心且具有挑战性的问题,其主要的任务是将一些虚拟请求的网络嵌入到一个共享的底层网络中去。VNE问题是一个NP困难的问题,其中虚拟网络的拓扑多样性是造成其难以较好的被解决的主要原因之一。但在实际的应用中,很多的虚拟请求网络都具有一些共同的拓扑结构特征,例如都是路和圈。为了取得更好的实际效果,设计出针对这些特殊结构的虚拟请求网络的专有算法是提升效能的关键。此外,路和圈是最为基础的网络拓扑结构也是构成所有复杂结构的基石,因此针对路和圈的结构的VNE问题的研究对一般结构的VNE问题起到至关重要的作用。在第五章中,我们对路和圈的VNE问题进行研究。对于路的VNE问题,在一个简化的情况下,我们证明了它下仍然是NP困难的,并且借助欧拉环游设计了相应的近似算法。在真实情况下,我们证明了它的不可近似性,并且设计了一个高效的基于多背包问题和多维背包问题的启发式算法。对于圈的VNE问题,我们构造了一个赋权有向辅助图,并在此基础上设计了一个多项式时间的圈到圈VNE的最优嵌入算法。与一般的VNE算法相比,实际的数值结果证明了我们所提出的算法能提高路和圈VNE的实际接受率和收益。
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5
，

本文编号：2594400