具有长度约束的路径数研究

摘要

图论是近年来发展迅速而又应用广泛的一门学科。它最早起源于一些数学游戏的难题研究,以及在民间广泛流传的一些游戏难题。 以后随着科学的发展,图论在解决工程科学、运筹学、网络理论、信息论、控制论、博弈论以及计算机科学等各个领域的问题时,显示出越来越大的效果。对于这样一门应用广泛的学科,其包含的内容当然是浩瀚如海。
　　具有长度约束的简单路径问题(Simple Paths with Length Constraint, SPLC)是指求解图G中任意两点间路径长度为m的简单路径数,是k-path 问题的一种特殊情况。本文在研究有向无环图中具有长度约束的简单路径问题(Simple Paths with Length Constraint in DAGs, SPLC in DAGs)前,先讨论了在无向图中具有长度约束的非简单路径数问题(Non-Simple Paths with Length Constaint in Undirected Graphs,NPLC in UGs) 并基于网树数据结构提出了网树求解无向图中具有长度约束的非简单路径的算法(Nettree for Non-simple Paths with Length Constraint in Undirected Graphs, NNPLCUG)；将NNPLCUG算法的求解思路引申到求解SPLC in DAGs中,形成了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs, NSPLCDAG),NNPLCUG 和NSPLCDAG算法都是将问题转化为一棵网树后,利用树根路径数这一性质对其进行求解。对NSPLCDAG算法进行改造,可以对最长路径问题进行求解,形成了网树在有向无环图中求解最长路径的算法(Nettree for the Longest Path in DAGs, NLPDAG),NLPDAG算法可找到所有的最长路径,再对NLPDAG算法做进一步改进以形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径。
　　最后,利用离散数学中提到的利用矩阵乘法求解具有长度约束的路径的理论对本文提出的算法进行正确性验证,并进行实验对算法的效率进行测试。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1-1 课题的研究背景及意义

§1-2 课题的研究现状

§1-3论文的研究内容及本文结构

第二章 图论基本定义及网树简介

§2-1 图论基本定义

§2-2生成有向无环图

§2-3 网树简介

§2-4本章小结

第三章 图中具有长度约束的路径数研究

§3-1 k-path问题及主要研究方法

§3-2 无向图中具有长度约束的非简单路径数

§3-3 有向无环图中具有长度约束的简单路径数

§3-4 本章小结

第四章 有向无环图中最长路径问题

§4-1 最长路径问题主要研究方法

§4-2有向无环图中最长路径的求解

§4-3 本章小结

第五章 总结与展望

§5-1 工作总结

§5-2 工作展望

参考文献

致谢

攻读学位期间所取得的相关科研成果