哈密尔顿图的判定及应用

哈密尔顿图在安排多项任务的解决顺序或其相关领域的应用越来越广泛。哈密尔顿图判别方法多种多样,大约有6种方法可应用。应用哈密尔顿图解决货车送货行走路线问题有较强的实用价值,使用两种选择边的方法求出最短路线。

树枝型专用线取送车问题的哈密尔顿图解法

运用图论中的哈密尔顿图,可以将树枝型专用线取送车问题,转化为求哈密尔顿图中权值最小的哈密尔顿回路问题。以6个节点的树枝型专用线为例,将其转化为哈密尔顿图,运用近似计算法,求得最小哈密尔顿回路8个,每一个回路对应2个机车走行方案。对于有较多节点的树枝型专用线,运用计算机进行计算,可以得到全部最优解。

树枝形专用线取送车问题哈密尔顿图模型及算法

合理安排铁路专用线取送车顺序,对提高调车机车作业效率、加速货车周转具有重要的意义.在已知条件下,以机车在装卸点间走行时间为权,把树枝形专用线取(送)车作业优化问题转换成哈密尔顿图最短路问题,并松弛为指派问题,采用匈牙利算法求出指派问题的最优解,可得到最短回路路长的下界或最优解.若未得到最优解,再利用破圈连接法求出满意的取(送)车顺序,此算法的复杂度为O(n2).同时对送兼调移、取兼调移、取送结合、送调取结合作业形式进行了深入地讨论.最后举例说明了模型的构造及求解过程.大量小规模案例表明,该算法的平均复杂度及性能是比较优越的.

哈密尔顿图的一个充分条件的注记

Faudree等在 1991年得到 N C≥ n -δ条件下熟知的哈密尔顿性结果 ,其后 ,一些论文研究 N C2 ≥ n -δ的哈密尔顿图性 .本文进一步研究更好条件 N C≥ n -δ - 1下的情况 ,所得结论仅比 Faudree等的结论多

也谈用矩阵判断哈密尔顿图的一个充要条件

指出了文 [1]结论及证明中值得商榷的地方并给予了改进 ,在此基础上得到了几个推论 .

邻接树图是哈密尔顿图猜想的一个等价命题(英文)

本文给出了“简单图的邻接树图是哈密尔顿图”猜想的等价命题 ,阐明只需证明该猜想对 2 -连通图成立即可 .另外 。

哈密尔顿图教学中的几个问题

针对离散数学课程教学面临的一些问题,以哈密尔顿图教学内容为例,讨论了教学中的三个问题,以达到理解教学内容、引发思考、提高自主探索能力的目的。

哈密尔顿图的一个充分条件的新注记

记NC=min{|N(x)∪N(y)|:x,y∈V(G),xy E(G)},这里得到:若2连通n≥3阶图G,NC≥(2n-4)/3,则G是H图或G∈G2*3K(n-2)/3.此结果推广以前的一些已知结果.

哈密尔顿图和邻域并

邻域并条件是近十年来研究哈密尔顿图的得力工具之一。本文得到距离是2的点对的邻域并条件 下的哈密尔顿图结果:若2连通 n ≥ 3 阶图 G 距离是2的任意两点 x,y 均有 |N(x) ∪ N(y)| ≥ (2n ? 4)/3,则 G 是哈密尔顿图或 G ∈ {G2 : 3K( n?2)/3,K(n?2)/3: K(n+1)/3: K(n+1)/3,Kn/ 3 Kn/ : Kn/ }。此结果改进一些已知结果。 3

哈密尔顿图的局部化临域并条件(英文)

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li- <G ,i=1,2 (L1≠L2或L1=L2 )且对任意顶点xi,yi∈V(Li) ,i=1,2和 {x1,y1}≠ {x2 ,y2 } ,dLi(xi,yi) =2 ,有下列不等式(D) 3|N(x1)∪N(y1) |+3|N(x2 )∪N(y2 ) |≥ 4p - 2 ,(1)若Li≌K1.3 或K1.3 +e ,i=1,2 ,则G为哈密尔顿图 .(2 )若Li≌K1.3 +e或P4 ,i=1,2 ,则除非G中有一个强D1-圈 ,G一定是哈密尔顿图t这一结果推广了Lindquester的结果 :每个p阶 2 -连通图G ,若有NC2≥ (2p - 1) /3,则一定是哈密尔顿图 .

新的充分条件和哈密尔顿图

记δ和α分别表示图G的最小度和独立数 ,1991年Faudree等人得到图G不相邻的任意 2点x ,y均有 |N (x)∪N (y) |≥n -δ的Hamiltonian结果。 1993年美国乔治亚州立大学的陈冠涛教授深化Fan条件并且得到满足 1≤ |N (x)∩N(y) |≤α -1的不相邻的任 2点x ,y均有max{d(x) ,d(y) }≥n/2的Hamiltonian结果。进一步改进Faudree等人的条件和综合陈冠涛教授的思路 ,研究满足 1≤ |N(x)∩N(y) |≤α -1的不相邻的任 2点x ,y均有 |N (x)∪N(y) |≥n -δ -1下的情况 ,并得到 :若 2连通n阶图G的满足 1≤ |N (x)∩N(y) |≤α -1的不相邻的任 2点x ,y均有 |N (x)∪N (y) |≥n -δ -1,则G是哈密尔顿图或G∈ {K(n - 1) / 2 ,(n + 1) / 2 ,K 2 ∨3K(n - 2 ) / 3}。

拟无爪哈密尔顿图的邻集条件(英文)

作为无爪图的一种推广,拟无爪图类由Ainouche引入.已经知道:如果阶数为n的3-连通无爪图G,对于每一对距离为2的点都有|N(x)∪N(y)|≥(2n-6)/3,那么图G是哈密尔顿的.在本文中,推广了上述的结论并且得到:如果阶数为n的3-连通拟无爪图G,对于每一对距离为2的点都有|N(x)∪N(y)|≥(2n-6)/3,那么图G是哈密尔顿的.

哈密尔顿图的一个充分条件

本文用NC2去研究哈密尔顿图，得到比文献［1」［2」［3」［4」的一些结果好的结果。

关于哈密尔顿图

利用邻接矩阵 。

哈密尔顿图的判定算法

提出了哈密尔顿图判定的一个充要条件 ,并给出了具体的实现算法。用C语言设计了相应的程序验证了此算法。

树枝形专用线取送车问题哈密尔顿图模型及算法

合理安排铁路专用线取送车作业，对提高调车机车作业效率、加速货车周转具有重要的意义。在已知条件下，以机车在专用线间走行时间为权，把树枝形专用线取送车作业转换成哈密尔顿图最短路问题，指出其松弛问题为指派问题，应用匈牙利算法求出指派问题的最优解，再设计破圈连接法求出最佳可行的取送车顺序，并举例说明了模型构造及求解过程。

带有最小度的哈密尔顿图的充分条件

由于图的谱能够很好地反映图的结构性质且便于计算,因而可以利用图谱理论来研究图的哈密尔顿性。主要研究哈密尔顿图的谱充分条件和无符号拉普拉斯谱充分条件。首先介绍图的闭包性质;然后对图的闭包结构进行分析、论证,利用度序列以及反证法找出带有最小度的图是哈密尔顿图的边数充分条件;最后根据图的边数与谱半径、无符号拉普拉斯谱半径的关系,分别给出G是哈密尔顿图的谱充分条件、无符号拉普拉斯谱充分条件。所得到的结论均优化已有结论。

哈密尔顿图的判定及在“旅行货郎问题”上的应用

伴随着数学和计算机科学的发展,图论的应用已经渗透到了各个领域;利用图的直观性和漂亮的表现特性可以使人们对现实的系统有更清晰的了解.在现实的世界当中许多问题的数学抽象形式都可以用图来描述,例如互联网、通讯网、交通网、分子结构、集成电路等.图论已经成为了人们研究自然科学和社会科学的重要工具,其中哈密尔顿图在其相关的领域的应用已经越来越广泛.大部分的图论书上都给出了哈密尔顿图的判别方法和相关的应用,本文在查阅大量相关的资料的基础上总结和概括哈密尔顿图的起源、判别方法及相关的应用.

哈密尔顿图的一些谱充分条件

图的邻接矩阵和无符号拉普拉斯矩阵的最大特征值分别称为谱半径和无符号拉普拉斯谱半径。由于图的谱容易计算,所以通过图的谱来研究图的结构性质。近年来,利用图的谱研究图的哈密尔顿性已经成为一个前沿热点问题。受此启发,利用图以及补图的谱半径和无符号拉普拉斯谱半径来刻画图的哈密尔顿性,进而得到更好的哈密尔顿图的谱充分条件。

树枝型专用线取送车问题的哈密尔顿图解法

为提高铁路运输过程中专用线取送车作业的工作效率,本文针对树枝型专用线取送车问题,结合铁路运输过程中的取车作业模式和作业流程等各项因素,对基于哈密尔顿图的相关解法进行了探讨,结合相关算例,说明了该算法模型的合理性和有效性。