K邊導出子圖問題研究.pdf

1、解決問題的方法也叫做算法，并不是計算機科學的專有名詞，早在幾千年前就有該方面的研究，當時把其認為是數(shù)學的一個分支。計算機的出現(xiàn)使得人們能夠利用計算機模擬并解決實際問題，而且由于上世紀計算機CPU處理能力的局限性，內(nèi)存，磁盤等資源的缺乏，使得人們開始注重對解決問題的最優(yōu)方法的研究。這極大的刺激了算法的發(fā)展，針對各類問題的各種算法開始大量的涌現(xiàn)。同時，為了對算法的好與壞進行評定，人們發(fā)展出了一套算法復雜性理論。人們主要是從算法解決問題所需要

2、的步驟也就是運行時間，以及其使用的額外空間來評定算法的好壞。如果算法的運行時間是關于算法輸入的長度的多項式，則通常被認為是好算法。人們通過研究逐漸發(fā)現(xiàn)，有一些問題似乎不可能存在一個好算法。更加令人驚奇的是，這些問題中的任何一個如果存在一個好算法可解，則這些問題都能找到一個好算法。因此人們把這類問題歸為一類，叫做NP完全問題，一般認為NP完全問題是不可能存在多項式時間的算法的。圖論是數(shù)學中的一個古老而有趣的分支，圖論與算法有著天然的聯(lián)系，