基于Karp猜想的圖性質的研究方法.pdf

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

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