圖論中的分割及相關問題

Abstract

分割問題是圖論中的一大類問題,旨在將圖 的點或邊分割成最少數目具某種特性的圖.本 計畫主要是研究路徑分割□點著色(即是將點 集分割成獨立集)以及相關問題.路徑分割和漢 米爾頓路徑問題息息相關,甚至較之更難.這問 題在二分圖及弦圖上均為NP難,前人在區間圖和 圓弧圖上已得到有效演算法,本計畫的目標則 放在弦圖的各類子圖上設計有效演算法,例如: 樹形圖□有向路徑圖□無向路徑圖□可序圖□強弦圖.在點著色方面,本計畫將探討距離圖上 的點著色問題和稱為L(2,1)標號的一種點著色推 廣問題.距離圖是以某度量空間的點為點,兩點 距離是某一指定數則連邊,所形成之圖;此種圖 上點著色數的結果,目前以一維或二維歐式空 間之子空間為主,我們的目標除了在低維空間 將前人未完的結果加強外,更希望往高維空間 研究.L(2,1)標號是要求相鄰兩點所著顏色至少 差2,距離2的不同點要著不同色;我們的目標是 在前人的上□下界定理之外,研究演算法的設 計.在其他相同問題上,我們也研究獨立集的問 題,特別在計數一個圖的最大獨立集個數上,尋 求一些定性結果.基於研究選址問題的需要,我們也將研究弦圖上各類子圖的中心集□中位集 及其各種變型問題.