最短路径子图

在大型网络中两节点之间的最短路径常常不止一条，而且在带限制条件的路径选择等应用上，常常需要找出多条最优或近优的路径．一些经典的单源最短路径算法，如Dijkstra算法，能找出一条从起始点到目的点的最短路径，但并不能求解两点之间的所有最短路径．本文给出了最短路径子图的概念，用于存储图中两节点之间所有最短路径信息，能够节约存储空间．并给出了最短路径子图构造算法SPSG，其时间复杂度为O(n e)，比同类算法时间复杂度更低．随机网络模型的仿真结果表明：SPSG算法效率更高，     

应用网络流模型解决航班衔接问题

针对单枢纽机场航线结构的特点，以所需飞机数最少为目标，提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题，并建立一个描述航班节衔接问题的二部图，将航班衔接问题转化为二部图的最大匹配问题，然后由二部图生成一个具有单源汇网络特征的辅助图，利用Ford-Fulkerson算法求该网络的最大流，进而得到二部图的最大匹配，从而得到了一个需用飞机数最少的航班节衔接方案，为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限，可以得出不同的航班衔接方案，为制订生产计划提供了必要的灵活性。     

K(n,m)图的边色数

设K(n,0)＝Kn,V(Kn)={v1^0,v2^0…,vn^0}，分别从v1^0,v2^0,…,vn-1^0,出发作长为m的n-1各路vi^0,vi^1,…,vi^m,i=1,2,…,n-1；然后，对j=1,2,…,m，添加边{vi^i,vk^i|k,i=1,2,…,n-1,且k≠1}，这样得到的图用K(n,m)表示，证明了对图K（n,m)当n≥2、m≥1时的边色数为n。     

关于图的Mycielski图的边色数

对图G(V,E),μ(G)称为G的Mycielski图,V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w},且w V(G),而E(μ(G))=E(G)∪{uv′|u∈V(G),v′∈V′,且uv∈E(G)}∪{wv′|v′∈V′}, 其中wV(G),V′={v′|v∈V(G)}.猜想对简单图G,χ′(μ(G))=Δ(μ(G))+1当且仅当G=K2.其中,χ′(G)表示G得边色数,且证明了Δ(G)＞(|V(G)|)/(2)时猜想为真.     

基于图论的平面交叉口竖向设计研究与软件开发

分析了目前平面交叉口竖向设计软件的不足，的设计方法筒捷、精确，适用于所有平面交叉IZl样式，型的构建和等高线的绘制。提出了一种全新的平面交叉口模型——图模型。基于该模型能快速自动实现交叉口区域的划分，计算点的生成，立体模     

关于图的单圈划分

图的划分问题曾引起图论界的广泛关注，本文讨论了一般的单圈划分问题，利用禁用构形刻划了一个图存在单圈划分的条件，并进一步得到一个算法，有效地解决了判定一个图是否存在单圈划分，若存在则求其单圈划分的问题。     

一种有向概率图连通性仿真算法

图的连通性分析在系统可靠性分析、系统结构优化等领域有重要作用,该文为分析有向概率图的连通性提出了一种仿真算法。对该方法使用MATLAB和GENIE软件进行仿真,首先通过MATLAB计算网络连通分布情况,得到中间结果,然后将中间结果输入到GENIE,可以根据相互独立的各边失效度分析有向概率图连通的概率、各边失效时网络连通概率、网络不连通时各边失效概率以及进行灵敏度分析。仿真结果表明,该方法精度准确,运算速度快,适用于复杂结构的有向概率图连通性分析。     

基于图论的舰船水消防系统故障诊断顺序确定方法

快速地准确诊断出舰船水消防系统的故障,可以显著改善舰船损管水平,提出了一种图论与经验公式相结合的方法,将故障抢修时间为准则的经验公式值作为诊断路径中弧的权值,运用"反向追踪"算法计算从故障现象到具体可修理的故障部件的最短路径,以确定水消防系统的故障诊断顺序。实验数据表明:该方法不仅综合权重各潜在故障对水消防系统的重要性,所确定的故障诊断顺序与损管的经验做法相符。     

数模混合电路故障诊断新方法

在基于DES理论的电路测试中,最小测试集的求取一直是重点和难点。该文提出了一种基于网络撕裂法和图论法相结合的算法来求取最小测试集。通过网络撕裂法将大规模的电路分割为小规模数字电路部分和模拟电路部分,然后再分别对其使用图论法来求取各自的最小测试集,最后整合得到电路的最小测试集。该方法计算量小、诊断定位精度高,适合于工程应用。     

基于最短路径算法的舰船通道逃逸路线研究

当舰船发生灾变时,正确的疏散指挥是避免和减少人员伤亡的关键,而选择合理的逃逸路线又是正确指挥的前提.在N-最短路径的模型基础上,讨论了逃逸路线的可行性以及道路权重的计算;然后根据舰船的实际情况建立简易模型,讨论两点之间前N条最短逃逸路径的求法.对结果进行了分析并提出进一步开展优化的设想.