區(qū)間圖相關(guān)圖類若干結(jié)構(gòu)與算法問題.pdf

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

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

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

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