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

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

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

3、 UGs) 并基于網(wǎng)樹數(shù)據(jù)結構提出了網(wǎng)樹求解無向圖中具有長度約束的非簡單路徑的算法(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算法都是將問題轉化為一棵網(wǎng)樹后,利用樹根路徑數(shù)這一性質對其進行求解。對NSPLCDAG算法進行改造,可以對最長路徑問題進行求解,形成了網(wǎng)樹在有向無環(huán)圖中求解最長路徑的算法(Nettree for the Longest Path in DAGs, NLPDAG),NLPDAG算法可找到所有的最長路徑,再對NLPDAG算法做進一步改進以形成改進的NLPDAG算法,改進的NL