K邊導(dǎo)出子圖問題研究.pdf

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

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