領域展開-Dual graph 解 Hamilton cycle在平面圖上的存在性問題
本研究以對偶圖的性質,取代以往著重點或邊數量的方法,探討平面圖中漢米爾頓迴圈的存在性。我們設計一套定理,判斷對偶圖對應之原圖是否存在漢米爾頓迴圈,並提出「T 搜索」,有效降低電腦計算的時間複雜度。此外,我們建立多項化簡定理,能在不影響迴圈存在與否的前提下,透過邊、點的替換與收縮,或圖的結構分解來簡化圖形。研究中也討論 Herschel Graph 與 Tutte’s Graph,並提出當圖中出現特定結構時,原圖不具漢米爾頓迴圈的判別條件。最後,成果可用於構造具漢米爾頓迴圈平面圖之對偶圖,並期望數學方法推導出無漢米爾頓迴圈的平面圖,或用電腦窮舉所有無漢米爾頓迴圈平面圖之對偶圖,以便延伸討論。