基于編碼的相交圖圖同構(gòu)查詢處理與優(yōu)化技術.pdf

1、相交圖是圖中非常重要的有著廣泛應用的圖，相交圖的應用背景涉及生物、矩陣分析、統(tǒng)計學、任務分配等多個領域，而正是由于其具有廣泛應用背景使得它在最近二三十年間得到了迅速的發(fā)展。相交圖中有一些圖類，對于圖同構(gòu)問題等有著良好的線性時間算法。在相交圖中，區(qū)間圖和置換圖等，是被廣泛研究的圖類，原因之一是它們自然的出現(xiàn)在如任務調(diào)度，基因組學，系統(tǒng)發(fā)育和考古學等方面。
　　正因為這類圖在現(xiàn)實世界中有著很重要的應用，因此本文對于相交圖的編碼和基于編

2、碼的相交圖圖同構(gòu)算法進行了深入研究。本文系統(tǒng)地介紹了圖的發(fā)展歷史，國內(nèi)外對于圖編碼和圖同構(gòu)的研究現(xiàn)狀。然后，針對圖編碼和圖同構(gòu)，進行了研究。圖編碼的目的主要是為了壓縮存儲空間，并且能夠還原圖的信息，加快圖的同構(gòu)查詢。上述目標并不能同時滿足，有的算法達到很好的壓縮比例，但對于編碼后的圖，無法還原成原來的圖。本文的主要工作是，使得編碼以后的圖，能加快圖的同構(gòu)查詢。本文針對圖的同構(gòu)問題，深入研究了區(qū)間圖的編碼和同構(gòu)問題，對已有的PQ樹進行了改

3、進，得到了標簽PQ樹和它的規(guī)范化編碼表示，在此基礎上提出了基于標簽PQ樹的區(qū)間圖圖同構(gòu)算法——GIBPQ-Tree算法，該算法具有線性時間復雜度。本文對已有的圖譜編碼算法進行了改進，在鄰接矩陣的特征值的基礎上加入頂點的度，提出了改進的基于圖譜編碼相交圖圖同構(gòu)算法——GIBS算法，該算法具有良好的時間性能，能應用在更廣泛的圖同構(gòu)中。
　　最后，對所提出的圖同構(gòu)算法進行了相應的實驗性能評價與分析。對于GIBPQ-Tree算法的響應時間