圖形之路徑分割及其變型

Abstract

假設P是一個圖形性質。圖形的P-分割是將點集分割成互不相交的的集合，使得這些集合都誘導出滿足性質P的子圖。P-分割數是是圖中所有P-分割的最小數，而P-分割問題是找出P-分割數的問題。同樣的，我們也可以定義所謂的P-覆蓋和P-覆蓋數，而他們和P-分割、P-分割數只差在不要求集合要互不相交而已。 各式各樣的P-分割和P-覆蓋早已在文獻中被探討。比如，著色數是P為「沒有邊」這個性質的P-分割數。由Chartrand，Kronk和Wall [8]所定義的點蔭度a(G)，其P為「森林」這個性質。由Harary [24]定義的線性點蔭度lva(G)，其P為「線性森林」這個性質。 這篇論文的目的是考慮P為「有一條漢米爾頓路徑」、「誘導路徑」或「原圖的同距路徑」性質。也就是說，此篇論文探討路徑分割問題、誘導路徑分割問題和同距覆蓋問題。 就路徑分割問題而言，我們在塊形為完全圖、圈或完全二分圖的圖形上，給了一個 O(|V|+|E|)-時間的演算法。 就誘導路徑分割問題而言，我們在塊形為完全圖、圈或完全二分圖的圖形上，給了一個 O(|V|+|E|)-時間的演算法。我們也在補可約的圖形上給了一個多項式時間的演算法。 在同距覆蓋問題上我們有三個結果。首先，我們決定了塊形圖形的同距覆蓋數，並給了一個找出對應的路徑，時間為O(|V|+|E|)的演算法。最後，我們算出完全r分圖、2維和3維漢明圖的同距覆蓋數。