无向连通图中求约束条件下近似最长路算法

在无向连通图中寻找最长路是一个NP问题,在实际应用中往往以近似最长路来代替最长路,但现存的算法都针对图中任意两点之间的近似最长路。该文利用一条最长路中是不可以被再插入一个新顶点的这个事实,通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法,以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路,而这样的一条路往往非常接近指定的起点与终点之间的最长路。该算法在绣花打版软件的应用中取得了良好的效果。

连通[5,3]-图的最长路(圈)

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

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

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

基于Dijkstra算法的一类最长路问题的一种改进算法

目前认为Dijkstra算法是求解指定两点间或从指定点到其余各点无负权网络最短路问题的最好方法,但不能求解最长路问题。提出一种改进算法,求解最长路问题,并给出一个实例说明该算法的正确性。

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

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

图的最长路与最长圈

路和圈是图论最基本的概念之一，Euler图问题和Hamilton问题都可归结为路和圈的研究。此外，路和圈在特定图中存在条件是我们最为关注的问题，而最长路和最长圈的研究更是引人入胜。本文就此问题作了较全面的回顾，并提出一些问题，供研究、探讨。

Δ-free图的最长路和最长圈

得到Δ free图的最长路和最长圈的下界为 2δ + 2 ,以及存在Hamilton圈的一个充分条件 :δ≥max{p3,α},δ是图G的顶点的最小度 ,α是G的独立数p =|V(G) |≥ 1 5 .

无爪图中的次和与Dominating最长路

设H为一图.H中由m个点组成的独立集和由m个点组成的割集分别称为m-独立集和m-割集,而经过v∈V（H）的圈v-圈.设D为H的子图,测|D|和H-D分别表示|V（D）|（D的阶）和H-V（D）.称H是无爪的,如果它不含K1,3作为导出子图.称H是m-路连通的（m≥1）,如果|H|≥2,H的任一对点都由长度≥m的路相联.称只有一个点的图为0-路连通的.H中的路R是一dominating路,如果R是Hamilton的,或者V（H-R）是一独立点集.对H的子图A和D。

图的最长路的一个性质

本文给出了图的最长路的一个性质:设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。由此可得到图中圈长性质的一个较简单的证明。

2－连通图的最长路

设Ｇ是２－连通图，对Ｇ中任一对不相邻的顶点ｕ，ｖ，｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｓ．Ｆａｕｄｒｅｅ猜测，当Ｇ的顶点数 ｓ为奇数时，Ｇ的最长路的顶点数 本文证明猜测当ｓ＞３时是真的．进而证明了除一类图外Ｐ（Ｇ）≥ｍｉｎ｛｜ｖ（Ｇ）｜，２ｓ＋ｌ｝．

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

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

范-条件与具有给定端点的最长路

令G是n阶2-连通图且d(u，v)=2→max{d(u)，d(v)}≥n／2．设{x,y}不是G的2-割集,记最长的(x，y)-路的长度为p(x，y)．本文证明了如下结论：(1)p(x，y)≥n-2；(2)若p(x，y)=n-2且P是最长的(x，y)-路中使得d(xp)最小的一条，那么d(xp)=2，3或者n／2，其中xp表示唯一一个不属于P的点．本文还刻画了3-连通且使得d(xp)=3的图．

脚是最长路,人是最高山

禾丰的名字寓意期待美好的未来，译成英文即WELLHOPE。应该说，禾丰公司的创业过程是一个放弃与选择的过程。1995年6月18日，公司正式注册成立，最早的一批创业者付出了常人难以想象的艰辛。我们的对手是有着百年历史的跨国公司，他们几乎垄断了中国预混料的市场，但在当时我们的共矧愿望是打破外资企业的垄断，创立中国人自己的名牌预混料。正是当时的形势激发我们产生了奋起直追的豪壮胆气。但创业之艰超出了我们的想象，各种困难像大山一样压在我们的头顶；5个月没有发工资；用十几万元的流动资金做百万元经营；竞争对手散布谣言，造谣中伤；客户对我们持怀疑态度；银行将我们拒之门外；管理部门经常接到举报；为了买齐近百种原料，不得不去赊货。供应商一次次拒绝……那段时间里，我们呕心沥血，克勤克俭，可喜的是公司当年就有了突飞猛进的发展，半年之内我们完成了外资企业一年半到两年才能达到的销量，在9月份就超越了盈亏平衡点。

论k阶最长路

论ｋ阶最长路秦裕瑗（武汉钢铁学院管理工程系４３００８１）ＯｎＬｏｎｇｅｓｔＰａｔｈｓｏｆｔｈｅｋ－ｔｈＯｒｄｅｒＱｉｎＹｕｙｕａｎ（ＷｕｈａｎＩｒｏｎａｎｄＳｔｅｅｌＵｎｉｖｅｒｓｉｔｙ４３００８１）ＡｂｓｔｒａｃｔＴｈｅ［１］ｇｉｖｅｓａｎａｌｇｏ...

赋权图中重路的隐赋权度条件

对 2 -连通非Hamilton赋权图G ,本文给出了重路存在的隐赋权度条件 :若G满足文中描述的条件C1 、C2 ,且max{idw(u) ,idw(v) |d(u ,v) =2 }≥ m2 ,则当G中存在y -最长路时 ,存在一最重的y-最长路P(x ,y)满足dw(x)≥ m2 .

网络优化的最大利润问题及其增广路算法

仿照最小费用最大流问题的物理意义,将网络上的费用参数转化成为一种利润参数,提出一个最大利润流问题,并建立了该问题的数学规划模型;给出一个求解该问题的最大利润增广路算法,该算法能快速有效地求得该问题的最优解及目标函数值。用示例对算法的求解过程进行了演示,结果表明该算法比一般的线性规划方法更加的方便,且直观得多。

关于最长圈交Grotschel猜想的证明

讨论了最长路的交及性质 .证明了Grotschel猜想 :C1和C2 是k 连通图G的两个最长圈 ,则 ｜V(C1)∩V(C2 ) ｜≥k;且公共点V(C1) ∩V(C2 )形成G的一个顶点割 .

二部图是哈密顿的一个充分条件

使范氏条件在二部图上得到更具体的刻画，得到以下结果：设Ｇ ＝ （ Ｘ，Ｙ；Ｅ） 是２—连通的二部图，｜ Ｘ｜ ＝｜ Ｙ｜ ＝ ｎ ≥２，ｕ，ｖ 是Ｇ中不同两顶点，当ｄ（ｕ，ｖ） ＝ ２ 时，有ｍａｘ（ｄ（ｕ） ，ｄ（ｖ）） ＞ ｎ／２，则二部图Ｇ为哈密顿图．并说明该结果是最好的可能．

关于3-连通图的一个猜测的反例

1978年,Dirac 给出了从2-连通图 G 中的最长路判断 G 的周长下界的一个定理.在1983年的西安图论讲习班上,朱永津提出了一个与 Difac 定理形式相似但条件较强结论也较强的猜测.通过发现一个反例,本文得到了这一猜测的否定解答。

一类Hamilton图

若P[u ,v]是 2连通无爪图G的最长路 ,设dp(xβ,xα) =︱P[xβ,xα]︱ -1 (xβ<xα) ,d P(xα,xβ) =|P[xα,xβ]|-1 (xα≤xβ) ,其中xα∈N(u) ,xβ∈N(v) ·dP=min{d(xβ,xα)︱xα∈N(u) ,xβ∈N(v) } ·d P =min{d(xα,xβ)︱xα∈N(u) ,xβ∈N(v) } ·设P[u,v]是具有最小dP 的G的最长路·采用反证法 ,将图G分为若干情况 ,利用P[u ,v]的定义 ,证明了 :若G是 2连通无爪图 ,且G的每个导出子图A ,A1都满足 φ(a1,a2 ) 。