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

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

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

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