解决问题的方法也叫做算法，并不是计算机科学的专有名词，早在几千年前就有该方面的研究，当时把其认为是数学的一个分支。计算机的出现使得人们能够利用计算机模拟并解决实际问题，而且由于上世纪计算机CPU处理能力的局限性，内存，磁盘等资源的缺乏，使得人们开始注重对解决问题的最优方法的研究。这极大的刺激了算法的发展，针对各类问题的各种算法开始大量的涌现。同时，为了对算法的好与坏进行评定，人们发展出了一套算法复杂性理论。人们主要是从算法解决问题所需要的步骤也就是运行时间，以及其使用的额外空间来评定算法的好坏。如果算法的运行时间是关于算法输入的长度的多项式，则通常被认为是好算法。人们通过研究逐渐发现，有一些问题似乎不可能存在一个好算法。更加令人惊奇的是，这些问题中的任何一个如果存在一个好算法可解，则这些问题都能找到一个好算法。因此人们把这类问题归为一类，叫做NP完全问题，一般认为NP完全问题是不可能存在多项式时间的算法的。图论是数学中的一个古老而有趣的分支，图论与算法有着天然的联系，如哥尼斯堡七桥问题。在Karp给出的21个基本NP完全问题中，就有几个是关于图论的。图论中的困难问题更是不胜枚举，有许多看起来简单的问题却是NP完全的。 本文对图论中的K边导出子图问题进行了研究，即问一个图中是否存在一个含有K条边的导出子图。本文给出了多项式时间规约证明了在一般图上该问题是一个困难问题，即是NP完全的。同时本文还在各种图类上对该问题的复杂进行了研究，也得到了一些否定或正面的结论。