標題: | 圖形之路徑分割及其變型 Path Partition and Its Variations in Graphs |
作者: | 潘俊杰 張鎮華 應用數學系所 |
關鍵字: | 路徑分割;誘導路徑分割;同距路徑覆蓋;path partition;induced-path partition;isometric-path cover |
公開日期: | 2003 |
摘要: | 假設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維漢明圖的同距覆蓋數。 |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT008722803 http://hdl.handle.net/11536/47223 |
顯示於類別: | 畢業論文 |