具有相同路徑層矩陣的無割點四正則圖.pdf

1、圖論是應(yīng)用數(shù)學(xué)的一個重要分支,它有著廣泛的應(yīng)用背景.圖論是一門既古老又年輕的學(xué)科,它已經(jīng)有二百多年的歷史了,但隨著計算機(jī)技術(shù)的出現(xiàn)和進(jìn)步,圖論的理論有了飛速的發(fā)展,煥發(fā)出青春的活力.該文所研究的具有相同路徑層矩陣的圖的問題是在藥品分析的實際應(yīng)用領(lǐng)域中提出來的.一個圖G的路徑層矩陣τ(G)(the pathlayer matrix)包含關(guān)于圖G中的所有路徑的定量信息.矩陣元素τ<,i,j>表示圖G中起點為i,路徑長度為j的路徑數(shù).圖的路徑

2、層矩陣與圖的同構(gòu)問題密切相關(guān).對于頂點數(shù)較少的圖,路徑層矩陣相等是圖的同構(gòu)的充要條件,已經(jīng)驗證當(dāng)圖G的頂點數(shù)p(G)≤11時,該結(jié)論成立.目前已知的具有相同路徑層矩陣的不同構(gòu)的圖的最小頂點數(shù)為14.已知的具有相同路徑層矩陣的不同構(gòu)的四正則圖的最小頂點數(shù)為44,具有相同路徑層矩陣的不同構(gòu)的五正則圖的最小頂點數(shù)為48,具有相同路徑層矩陣的不同構(gòu)的六正則圖的最小頂點數(shù)為51(楊元生,J.Graph Theory 39(2002)219-221

3、).早期所構(gòu)造出的具有相同路徑層矩陣的不同構(gòu)圖對都是有割點的,1999年,Dobrynin構(gòu)造出了一對的具有相同路徑層矩陣的不同構(gòu)的36個頂點的無割點三正則圖和一對具有相同路徑層矩陣的不同構(gòu)的31個頂點的無割點圖(A.A.Dobrynin,J.Graph Theory 38(2001)177-182).該文對Dobrynin的構(gòu)造具有相同路徑層矩陣的圖對的基本圖的特性進(jìn)行了更深入的探討,明確了基本圖的特性,給出了一種新基本圖,并從理論上

4、證明了這種利用新基本圖通過交叉連接的方法構(gòu)造具有相同路徑層矩陣的圖對的方法的正確性.針對新基本圖的構(gòu)造過程中的關(guān)鍵問題,在生成具有相同頂點度序列的圖,計算路徑向量,查找無割點圖等方面,該文設(shè)計和實現(xiàn)了一系列較好的算法,成功地解決了構(gòu)造新基本圖的問題.利用上述算法,該文構(gòu)造出了一對頂點數(shù)為18的具有相同路徑層矩陣的不同構(gòu)的無割點的四正則圖,從而把具有相同路徑層矩陣的四正則圖的最小頂點數(shù)與無割點圖的最小頂點數(shù)的上界均降到18.相關(guān)的論文已經(jīng)