论文部分内容阅读
网络的拓扑结构可以用图来表示,称为网络拓扑图.可以通过研究图的性质来研究网络的结构.研究图的性质的理论是图论,图论在计算机科学中的应用非常广泛.例如在开关理论与逻辑设计,数据结构,形式语言,操作系统,编译原理,信息组织与检索等方面都有很重要的应用.
匹配理论是图论的重要组成部分.导出匹配作为匹配理论的一个重要分支在计算机科学中也有重要的应用.例如:在偶图G=(U、V、E)中令U代表广播节点,V代表接收节点,E代表广播节点和接收节点之间的信道,我们从E中选取k条边,使得信道i上的信息从广播节点传输到接收节点,如果这k条边正好为图G的一个导出匹配,则这k条信道上的信息在传输过程中便不会泄露也不会相互干扰.本文重点研究导出匹配理论中导出匹配划分问题和导出匹配覆盖问题的计算复杂性,并对导出森林覆盖问题的计算复杂性做了一定的研究.
Cameron和Faudree等人在1989年对导出匹配的基本性质和存在性条件进行了研究.导出匹配k-划分问题最早出现在组合优化领域.由Yuan,Wang和Yang对该问题进行了研究,得到了一些有意义的结果.导出匹配k-覆盖问题由Dong和Yuan在2006年提出.对于上述两问题的研究,目前结论还不是很多.对于导出森林k-划分问题前人做了不少的研究,但对于导出森林k-覆盖问题的研究却不是很多,结论也很少.
本文证明了直径为5的图的导出匹配2-划分问题和导出匹配2-覆盖问题,直径分别为3和4的图的导出匹配3-划分问题和导出匹配覆盖问题及直径为2的图的导出森林2.覆盖问题都是NP一完全的。
本文共分为五章.第一章简要介绍了匹配理论的基本概念、历史和进展状况,论文的工作及文章的组织结构.第二章研究了小直径图的导出匹配划分问题的计算复杂性,证明了直径为5的图的导出匹配2.划分问题,直径为4的图的导出匹配3.划分问题,直径为3的图的导出匹配3-划分问题均是NP-完全的.第三章研究了小直径图的导出匹配覆盖问题的计算复杂性,证明了直径为5的图的导出匹配2-覆盖问题,直径为4的图的导出匹配3.覆盖问题,直径为3的图的导出匹配3.覆盖问题均是NP.完全的.第四章研究了直径为2的图的导出森林2-覆盖问题的计算复杂性,证明了直径为2的图的导出森林2.覆盖问题是NP.完全的.第五章总结全文,并提出下一步要解决的问题.