獨立集之計數

Abstract

某一圖中的獨立集為一兩兩不相鄰的點集，而最大獨立集除了是個獨立隻之外，還有 它不是任何其他獨立集的真子集；極大獨立集是一個獨立集，而且其點數是所有獨立 集中個數最多的。討論一個圖中獨立集個數的問題首推Erdos與Moser，他們考慮一個 包含n個點的圖形中，最大獨立集的個數可能的最大值為，而可達到此值的極圖又為 何？上述問題由Moon與Moser解決了。大約20年後的最近，許多數學家投入研究相同 的問題，但他們改變方向只對一些特殊圖形作討論，其中包括樹圖、連通圖、無三角 形圖、還有二分圖。此篇論文將上述問題作推廣。我們也對獨立集與極大獨立集的相 關問題提出一些看法。除此之外，其最大獨立集為定值的圖形，我們圖找出它們的行 為迉式。最後提出演算法的觀點做為此篇論文的總結。第二章中，我們將重心放在某 些特殊圖形（如：一般圖形、連通圖、林圖、樹圖、至多一循環連通圖、與無三角形 連通圖），討論其最大獨立集與極大獨立集個數可能之最大值為多少，並進一步的找 出有那些極圖。第三章中，我們有興趣的是k-連通圖中其獨立集表現如何。第四章中 ，我們從另一個角度來觀察，那就是擁有固定的最大獨立集個數的圖形中，其點集的 表現如何，再者，何種圖形可使其點數達到最多。最後，第五章中我們列了三個演算 法，分別計算樹圖中的獨立集、極大獨立集、與最大獨立集的確實個數。