具有長度約束的路徑數(shù)研究.pdf

1、　　圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一門學(xué)科。它最早起源于一些數(shù)學(xué)游戲的難題研究,以及在民間廣泛流傳的一些游戲難題。 以后隨著科學(xué)的發(fā)展,圖論在解決工程科學(xué)、運(yùn)籌學(xué)、網(wǎng)絡(luò)理論、信息論、控制論、博弈論以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域的問題時(shí),顯示出越來越大的效果。對(duì)于這樣一門應(yīng)用廣泛的學(xué)科,其包含的內(nèi)容當(dāng)然是浩瀚如海。
　　具有長度約束的簡(jiǎn)單路徑問題(Simple Paths with Length Constraint, SPLC)

2、是指求解圖G中任意兩點(diǎn)間路徑長度為m的簡(jiǎn)單路徑數(shù),是k-path 問題的一種特殊情況。本文在研究有向無環(huán)圖中具有長度約束的簡(jiǎn)單路徑問題(Simple Paths with Length Constraint in DAGs, SPLC in DAGs)前,先討論了在無向圖中具有長度約束的非簡(jiǎn)單路徑數(shù)問題(Non-Simple Paths with Length Constaint in Undirected Graphs,NPLC in

3、 UGs) 并基于網(wǎng)樹數(shù)據(jù)結(jié)構(gòu)提出了網(wǎng)樹求解無向圖中具有長度約束的非簡(jiǎn)單路徑的算法(Nettree for Non-simple Paths with Length Constraint in Undirected Graphs, NNPLCUG)；將NNPLCUG算法的求解思路引申到求解SPLC in DAGs中,形成了在有向無環(huán)圖中求解SPLC問題的算法(Nettree for SPLC in Directed Acyclic Gr

4、aphs, NSPLCDAG),NNPLCUG 和NSPLCDAG算法都是將問題轉(zhuǎn)化為一棵網(wǎng)樹后,利用樹根路徑數(shù)這一性質(zhì)對(duì)其進(jìn)行求解。對(duì)NSPLCDAG算法進(jìn)行改造,可以對(duì)最長路徑問題進(jìn)行求解,形成了網(wǎng)樹在有向無環(huán)圖中求解最長路徑的算法(Nettree for the Longest Path in DAGs, NLPDAG),NLPDAG算法可找到所有的最長路徑,再對(duì)NLPDAG算法做進(jìn)一步改進(jìn)以形成改進(jìn)的NLPDAG算法,改進(jìn)的NL