矩阵方法求赋权图中最短路的算法

目的 给出一些计算赋权图中任意两个节点之间最短路的算法。方法 利用矩阵方法。结果 给出了赋权图中任意两点之间最短路的算法；任意两点之间在含有最少边数情况下的最短路算法；赋权图中的所有最短路算法，以及前N条最短路的算法。结论 所研究的算法解决了传统算法的某些不足，因基于矩阵运算，程序设计简单，实用性强。     

K条路的两个问题

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广———有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,使得k条路中最长的路的费用尽可能小.给出了问题①的一个最优算法,其复杂度为O(k|V|2),同时证明了该算法对于问题是k-近似的.     

最长路原理与图中的路和圈

设（其中）为图Ｇ中一条最长ｙ一路，即以ｙ为终点的路中最长者．那么且对也是最长ｙ一路．利用该简单原理证明：对于２－连通非Ｈａｍｉｌｔｏｎ图Ｇ的任一顶点ｙ．存在某最长ｙ－路Ｐ（ｘ，ｙ）使ｄ（ｘ）较大．据此直接推出关于周长的范更华定理等重要结果。     

图的路径运算矩阵与哈密顿回路等路径问题

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上.证明了一般路径运算矩阵的幂长公式并得到了简单图...     

最长路原理与图中的路和图

设Ｐ＝ｖ０ｖ１…ｖｋ（其中ｖｋ＝ｙ为图Ｇ中一条最长ｙ－路，即以ｙ为络点的路中最长者，那私Ｎ（ｖ０）包函于Ｖ（Ｐ），且对ｖｊ∷Ｎ（ｖ０），ｖｊ－１ｖｊ－２…ｖ０ｖｖｊ＋１…ｖｋ也是最长ｙ－路，利用该简单原理证明：对于２－连通非Ｈａｍｉｌｔｏｎ图Ｇ的任一顶点ｙ，存在某最长ｙ－路Ｐ（ｘ，ｙ）使ｄ（ｘ）较大。据此直接推出关于周长的范更华定理等重要结果。     

用摹矩阵寻求网络的最短路

应用了半城、摹矩阵和优选半域等概念,把摹矩阵的计算运用到图论中的寻求负权网络中的最短路以及寻求网络中各点间的最短路问题上。实例的计算结果表明,这是一种计算简便,行之有效的方法.     

连通[5，3]-图的最长路（圈）

如果G中任意s个点的导出子图中至少含有t条边,则称G为[s,t]图.文中证明了:阶数不小于6的连通[5,3]图的最长路的长度不小于n-2,且路长的界是紧的,其最长圈的长度可任意小.     

空间岔管展开图设计计算研究

本文研究了空间锥形与圆柱形的岔管设计,找出了岔管设计的展开图（下料图）计算数学模型,建立了一组相贯线影射到展开平面的递推公式与迭代算法 .利用数学模型设计空间岔管的展开图,既可精确、快速地计算下料中的曲线坐标值,又能利用计算机进行辅助设计和模拟装配,从而达到耗材少、相贯体吻合性好的设计效果 .     

最短路的几个算法的代数证明

一、引言设有一个有向图,顶点集合为V={V_i|i=1,2,…n),有向边集合记作E。对于每一条边,赋以一个实数,可正、可负、可为零,这个实数叫做这条有向边的长度。这样的有向图叫做(一般)网络,记作N(V,E)。我们把在网络中寻求各顶点间的最短路的长度问题叫做求解模型MINPATH。而找出最短路叫做模型MINPATH的解的实现。网络中如果含有负回路,则有些顶点间,尽管存在长度有限的路,却不一定存在最短     

全光Johnson网络容错路由设计

随着光通信技术的发展，如何在光网络中提供较好的容错路由成为光网络的主要研究内容．本文在Johnson网络模型中通过对结点位串中相异子串的转换运算，先找出网络中的任意结点间最短路，在寻找次短路时在源结点和目标结点的相同位串中转换一位后再在不同位串上应用最短路算法，最终提出一种按预先商定模式（pre-negotiated mode）的容错路由，使全光Johnson网络J（n,k）中任意两结点之间存在k条内部不相交的路，它们由最短路与次短路组成．     

一种有向图最长路的算法、灵敏度分析及其应用

本文给出了一种有向图的定义,得到了这种有向图从始点到其它任一顶点之间最长路的算法。在不影响整个最长路的条件下,通过边上机动资源变化的分析,给出了这种有向图灵敏度分析的方法,解决了这种有向图在应用过程中的优化分析问题。     

限定高度的Dyck路的计数

针对一类从(0,0)到(n,k)的限定高度的Dyck路的计数问题,应用递推关系得到发生函数满足的线性方程组,通过线性代数方法得到了相应的计数公式.     

图的最长路的一个性质

本文给出了图的最长路的一个性质:设G是有n个点的2-连通图,如果对于任一对使d（u,v）=2的点u和v而推出max{d（u）,d（v）}≥c/2（3≤c≤n）,那么存在一条最长路μ=v_1v_2…v_r,且min{d（v_1）,d（v_r）}≥c/2。由此可得到图中圈长性质的一个较简单的证明。     

K-桥图的本原指标

K-桥图是由连接A，B两点的K条内部不交路所组成的图．计算得到本原K-桥图的本原指标等于m-1或n-1，其中m是最大奇圈的圈长，而n是A，B间最长奇路(偶路)与最短偶路(奇路)的长度之和．     

最短路径子图

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

只有一条最长路的树的Wiener指标

一个图的Winer指标是指图的所有顶点对的距离之和.本文确定了所有只有一条最长路的n阶树中(n>19)Wiener指标从第一小至第五小的树.     

基于最短路的设备更新问题的数学建模

最短路问题在大学生数学建模竞赛和实际生活中有着广泛的应用.介绍了最短路问题的定义、求解最短路的Dijkstra算法和0-1规划法.最后,给出设备更新问题的最短路数学模型求解过程.     

高阶线性递推数列通项公式的研究

常系数高阶线性递推数列通项公式的求解是极为复杂的计算,只有小部分特定系数的高阶线性递推数列才能求出通项公式,而所求出的通项公式属于数值解,只适用于原题的计算。根据高阶线性递推数列的关系式,逐阶逐项展开,寻找其变化规律,并进行归纳、总结、推导,得出了一条公式解的通项公式,能通解任意常系数的高阶线性递推数列,计算正确、简便,适用于八阶之内的各阶齐次或非齐次的高阶线性递推数列的计算,达到了快速求解的效果。     

塔形Dyck路的面积

利用递推关系和发生函数,研究塔形Dyck路以及所有路径与x轴围成的区域面积,得到所有半长为n的塔形Dyck路的计数公式,和所有半长为n的塔形Dyck路与x轴所围区域总面积的计数公式.     

无圈竞赛图的内(外)生成树与路的计数

主要研究了无圈竞赛图中的外向生成树和指定点对的路问题,得到了图中全部外向生成树的计数公式τ+(Tn)=(n-1)!,在此基础上,得出图中全部内向生成树的计数公式τ-(Tn)=(n-1)!;两点之间全部路的计数公式σ(Tn)=2n-2,在此基础上,得出n阶无圈图全部路数为2j-i-1.