基于Karp猜想的圖性質(zhì)的研究方法.pdf

1、圖論在許多領(lǐng)域中都有廣泛的應(yīng)用，這些應(yīng)用通常借助計(jì)算機(jī)來實(shí)現(xiàn)。在應(yīng)用計(jì)算機(jī)存儲(chǔ)圖形時(shí)，通常只需將圖的鄰接矩陣的上三角部分存儲(chǔ)到計(jì)算機(jī)即可，這就產(chǎn)生了一個(gè)問題：是不是必須存儲(chǔ)上三角部分的所有元素才能判斷一個(gè)圖G是否具有一些特殊的性質(zhì)?確切地說，對(duì)于一個(gè)n個(gè)頂點(diǎn)圖上的圖性質(zhì)P，是不是最多要存儲(chǔ)上三角部分的全部的n(n-1)/2個(gè)元素才能判斷一個(gè)圖G是否具有圖性質(zhì)P?人們猜測(cè)當(dāng)圖性質(zhì)P是非平凡而且單調(diào)時(shí)回答是肯定的，這就是著名的Karp猜想，

2、它是計(jì)算復(fù)雜性理論中的一個(gè)著名的懸而未決的問題，而且與圖論、拓?fù)洹⒋鷶?shù)相關(guān)聯(lián)，是數(shù)學(xué)與理論計(jì)算機(jī)科學(xué)中一個(gè)相當(dāng)引人入勝的研究課題。 本文的主要內(nèi)容如下： 第一章回顧了Karp猜想的發(fā)展歷史并介紹一些相關(guān)的基礎(chǔ)知識(shí)。 第二章介紹Karp猜想的四種研究方法，對(duì)每種方法給出分析和評(píng)述，并對(duì)其中的一些定理給出了本文的證明方法及相應(yīng)的推論。 針對(duì)上一章中介紹的第四種方法，我們?cè)诘谌轮刑岢鲆环N新的構(gòu)造布爾函數(shù)的算法