具有相同路徑層矩陣的無(wú)割點(diǎn)四正則圖.pdf

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

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

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

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