圖論中的分割及相關問題
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.contributor.author |
張鎮華 | en_US |
dc.contributor.author |
Chang Gerard Jennhwa | en_US |
dc.contributor.department |
國立交通大學應用數學系 | zh_TW |
dc.date.accessioned |
2014-12-13T10:40:17Z | |
dc.date.available |
2014-12-13T10:40:17Z | |
dc.date.issued |
1994 | en_US |
dc.description.abstract |
分割問題是圖論中的一大類問題,旨在將圖 的點或邊分割成最少數目具某種特性的圖.本 計畫主要是研究路徑分割□點著色(即是將點 集分割成獨立集)以及相關問題.路徑分割和漢 米爾頓路徑問題息息相關,甚至較之更難.這問 題在二分圖及弦圖上均為NP難,前人在區間圖和 圓弧圖上已得到有效演算法,本計畫的目標則 放在弦圖的各類子圖上設計有效演算法,例如: 樹形圖□有向路徑圖□無向路徑圖□可序圖□強弦圖.在點著色方面,本計畫將探討距離圖上 的點著色問題和稱為L(2,1)標號的一種點著色推 廣問題.距離圖是以某度量空間的點為點,兩點 距離是某一指定數則連邊,所形成之圖;此種圖 上點著色數的結果,目前以一維或二維歐式空 間之子空間為主,我們的目標除了在低維空間 將前人未完的結果加強外,更希望往高維空間 研究.L(2,1)標號是要求相鄰兩點所著顏色至少 差2,距離2的不同點要著不同色;我們的目標是 在前人的上□下界定理之外,研究演算法的設 計.在其他相同問題上,我們也研究獨立集的問 題,特別在計數一個圖的最大獨立集個數上,尋 求一些定性結果.基於研究選址問題的需要,我們也將研究弦圖上各類子圖的中心集□中位集 及其各種變型問題. | zh_TW |
dc.description.sponsorship |
行政院國家科學委員會 | zh_TW |
dc.identifier.govdoc |
NSC83-0208-M009-050 | zh_TW |
dc.identifier.uri |
https://www.grb.gov.tw/search/planDetail?id=75586&docId=11513 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/97368 | |
dc.language.iso |
zh_TW | en_US |
dc.subject |
分割 | zh_TW |
dc.subject |
路徑 | zh_TW |
dc.subject |
點著色 | zh_TW |
dc.subject |
獨立集 | zh_TW |
dc.subject |
二分圖 | zh_TW |
dc.subject |
強弦圖 | zh_TW |
dc.subject |
距離圖 | zh_TW |
dc.subject |
演算法 | zh_TW |
dc.subject |
NP難 | zh_TW |
dc.subject |
中心集 | zh_TW |
dc.subject |
中位集 | zh_TW |
dc.subject |
Partition | en_US |
dc.subject |
Path | en_US |
dc.subject |
Vertex coloring | en_US |
dc.subject |
Independent set | en_US |
dc.subject |
Bipartite graph | en_US |
dc.subject |
Stronglychordal graph | en_US |
dc.subject |
Distance graph | en_US |
dc.subject |
Algorithm | en_US |
dc.subject |
NP-hard | en_US |
dc.subject |
Center | en_US |
dc.subject |
Median | en_US |
dc.title |
圖論中的分割及相關問題 | zh_TW |
dc.title |
Partition Problem and Related Topics in Graph Theory | en_US |
dc.type |
Plan | en_US |
檔案
本條目沒有附加檔案。
所屬典藏: 研究計畫