k边导出子图问研究.pdf

K 边导出子图问题的研究 摘 要 解决问题的方法也叫做算法，并不是计算机科学的专有名词，早在几 千年前就有该方面的研究，当时把其认为是数学的一个分支。计算机的 出现使得人们能够利用计算机模拟并解决实际问题，而且由于上世纪计 算机 CPU 处理能力的局限性，内存，磁盘等资源的缺乏，使得人们开始 注重对解决问题的最优方法的研究。这极大的刺激了算法的发展，针对 各类问题的各种算法开始大量的涌现。同时，为了对算法的好与坏进行 评定，人们发展出了一套算法复杂性理论。人们主要是从算法解决问题 所需要的步骤也就是运行时间，以及其使用的额外空间来评定算法的好 坏。如果算法的运行时间是关于算法输入的长度的多项式，则通常被认 为是好算法。人们通过研究逐渐发现，有一些问题似乎不可能存在一个 好算法。更加令人惊奇的是，这些问题中的任何一个如果存在一个好算 法可解，则这些问题都能找到一个好算法。因此人们把这类问题归为一 类，叫做NP 完全问题，一般认为NP 完全问题是不可能存在多项式时间 的算法的。 图论是数学中的一个古老而有趣的分支，图论与算法有着天然的联系， 如哥尼斯堡七桥问题。在Karp 给出的21 个基本NP 完全问题中，就有几 V 个是关于图论的。图论中的困难问题更是不胜枚举，有许多看起来简单 的问题却是NP 完全的。 本文对图论中的K 边导出子图问题进行了研究，即问一个图中是否存 在一个含有K 条边的导出子图。本文给出了多项式时间规约证明了在一 般图上该问题是一个困难问题，即是NP 完全的。同时本文还在各种图类 上对该问题的复杂进行了研究，也得到了一些否定或正面的结论。 关键词：算法，复杂性，导出子图，规约 VI Study of The k-Edge Induced Subgraph Problem ABSTRACT Solution to problems, also known as algorithm, is not only a technical term for computer science. It has been studied for thousands of years as a branch of mathematics. The emergence of the computer makes it possible to use computer simulation and to solve practical problems, and as a result of the last century computer CPU processing power limitations, memory, disk, such as a lack of resources so that people began to focus on the best ways to solve the problem. This greatly stimulated the development of algorithms for a variety of types of problems . At the same time, in order for the algorithm to be evaluated good or bad, it developed the complexity theory. It is the main method to solve the problem from the steps required is the time to run, as well as the use of additional space to evaluate the quality of the algorithm. If the algorithm is running on the algorithms input the length of