【摘 要】
：
该文主要可分为两个部分,第一部分所讨论的问题是,k-匹配的子正交匹配分解及一些近似算法,包括第一章到第四章;第二部分是,路染色问题,包括第五章.在这一部分中,该文的主要结
论文部分内容阅读
该文主要可分为两个部分,第一部分所讨论的问题是,k-匹配的子正交匹配分解及一些近似算法,包括第一章到第四章;第二部分是,路染色问题,包括第五章.在这一部分中,该文的主要结构是如下:第一章:引言部分简单介绍问题的应用背景,及一些基本概念,还有目前的一些主要结果和算法.第二章:将证明给定的图G是简单二部图,匹配M是图G一个完美匹配,则图G存在关于匹配M的正交匹配分解.并给出边集的一个关于M的正交匹配分解算法.第三章:将舍弃二部图的限制,讨论给定一个最大度为k的简单图G,M是G的一个完美匹配,寻找关于M的最小子正交匹配分解.第四章:在这一章中将给出(P)问题的一个最多需要2k-1次匹配的近似算法,并且讨论这种贪心算法的下界.在第二部分中,将主要讨论光网络中的路染色问题.路染色问题可以描述如下:在一个连通图G上,对于给定的一组路的集合P,给每一条路分配一种颜色,使得任意有公共边的两条路分配不同的颜色,目标是求最小颜色数.在光网络中,连通图G的拓扑结构是特殊的,根据光网络的常用拓扑结构,得到抽象的图G是树、环和树环等,该文就主要讨论在这三种特殊图G上的路染色问题.
其他文献
在油藏数值模拟研究中,多孔介质中油、水两相渗流混溶驱动问题是一类主要研究对象.这个问题又可分为不可压缩混溶驱动问题和可压缩混溶驱动问题.前者的数学模型是由椭圆型的
设R是一个局部环,N是R上A(n≥3)、D(n≥4)、E型Chevalley代数的由正根基向量生成的幂零子代数.本文证明了N的任一个自同构ψ都可以表示为图自同构g、例外自同构v、对角自同构
有一张照片,近50年来我始终细心地珍藏着,在“文革”期间也没有丢掉。因为照片上有刘少奇同志的形象,把这样的照片保留下来也要有风险的。现在回忆起拍这张照片时的情形,还
Ehm在1981年解决了多指标稳定过程局部时的存在性、连续性及其Holder律;Xiao在2003年讨论了可加Lévy过程局部时的相应的问题.尽管Jain,Pruitt和Taylor等曾讨论单指标稳定分
蛋白质空间结构的研究是蛋白质功能研究的必经之路,因为结构决定功能.面对大量新发现的蛋白质,传统的用来测定蛋白质三维结构的实验方法——X光晶体衍射和NMR(核磁共振)技术
该文共分四章:第一章概述研究背景和作者的主要工作第二章叙述向量有理插值的定义和基本概念,向量有理插值的构造方式和计算方法第三章对向量有理插值的存在性进行了初步的研
《小学科学课程标准(2011年修订版)》指出:“全面提高每一个学生的科学素质是科学课程的核心理念。”小学科学作为小学生科学文化素质教育的核心课程,其实施效果的好坏直接关
10月19日至20日,中共海南省委四届五次全会在海口召开,会议经过充分讨论、认真审议,一致通过了《中共海南省委关于贯彻落实〈中共中央关于加强党的执政能力建设的决定〉的意
中商情报网2012-6-15报道:前4个月,外商投资企业依然是我国纸和纸板出口主体,占我国纸和纸板出口总量的76.4%,共出口113万吨,同比下降3.2%;共出口无机物涂布纸81万吨,同比下
在全光网络中需要通过使用波分复用技术(WDM)来充分利用巨大的带宽.一条光纤连接可以同时传输若干逻辑信号,只要保证他们使用不同的波长.波分复用技术在不远将来的通信领域将