完整後設資料紀錄
DC 欄位語言
dc.contributor.author潘俊杰en_US
dc.contributor.author張鎮華en_US
dc.date.accessioned2014-12-12T01:48:09Z-
dc.date.available2014-12-12T01:48:09Z-
dc.date.issued2003en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT008722803en_US
dc.identifier.urihttp://hdl.handle.net/11536/47223-
dc.description.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維漢明圖的同距覆蓋數。zh_TW
dc.language.isoen_USen_US
dc.subject路徑分割zh_TW
dc.subject誘導路徑分割zh_TW
dc.subject同距路徑覆蓋zh_TW
dc.subjectpath partitionen_US
dc.subjectinduced-path partitionen_US
dc.subjectisometric-path coveren_US
dc.title圖形之路徑分割及其變型zh_TW
dc.titlePath Partition and Its Variations in Graphsen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
顯示於類別:畢業論文


文件中的檔案:

  1. 280301.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。