區(qū)間圖相關圖類若干結構與算法問題.pdf

1、區(qū)間圖的定義簡單自然，關于它已經(jīng)建立起豐富優(yōu)美的數(shù)學理論，還有許多深刻的公開研究問題和猜想。區(qū)間圖模型也在大量應用問題中出現(xiàn)，其實關于區(qū)間圖的最早一批系統(tǒng)結果就來自于美國蘭德公司數(shù)學實驗室的一批著名數(shù)學家。
　　本文工作主要是關于區(qū)間圖及其算法，主要結果如下:
　　第一部分是關于嚴格區(qū)間圖和單位區(qū)間圖的.我們探索了嚴格區(qū)間圖的極大鄰域搜索(MNS)性質并從幾個方面刻畫了嚴格區(qū)間圖，獲得了3步MNS線性算法來識別嚴格區(qū)間圖和單

2、位區(qū)間圖，從而推廣了Corneil在2004年設計的識別單位區(qū)間圖的3步字典序寬度優(yōu)先搜索(LBFS)算法.對單位區(qū)間圖我們還提出了新的兩步MNS認證算法.
　　第二部分是關于一般區(qū)間圖的.Corneil等人在2009年設計了6步LBFS算法來識別區(qū)間圖.在他們的基礎上我們設計出4步LBFS區(qū)間圖識別算法，這個算法還可識別單位區(qū)間圖.目前唯一已知的區(qū)間圖認證算法是由Kratsch等人給出的，他們利用了Korte和M(o)hring

3、給出的區(qū)間圖識別算法，且用了叫做MPQ樹的復雜數(shù)據(jù)結構.我們的算法可改進為區(qū)間圖的認證算法，不包含任何復雜的存儲結構且可在線性時間內實現(xiàn).
　　第三部分主要研究圖的漢密爾頓性質.我們的主要發(fā)現(xiàn)是如果一個圖存在充分厚的漢密爾頓排序，則它有很多支撐連通性質，特別地對于區(qū)間圖而言，相當多看起來無關的支撐連通性質都等價于存在某個k-厚的漢密爾頓序.基于漢密爾頓厚度和支撐漢密爾頓連通性質的聯(lián)系，我們得到了一些相關問題的線性算法.Broers

4、ma等人在文獻[12]中提出了一個開放性的問題:確定計算區(qū)間圖或者單位區(qū)間圖的支撐軌道連通性的時間復雜度.我們給出了一個線性的算法來解決這個問題，從而回答了Broersma等人的開放性問題.
　　最后一部分是關于區(qū)間圖1PC/1HP問題的.Damaschke在1993年提出區(qū)間圖1PC/1HP問題是否有多項式算法的公開問題.在2010年，Asdre和Nikolopoulos給出O(n3)的算法.我們找到了O(n+m)的算法來解決區(qū)