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

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

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