2-阶邻域连通无爪图的Hamilton性

设Ｇ是无爪图．对ｘ∈Ｖ（Ｇ），若Ｇ［Ｎ（ｘ）］不连通，则存在ｙｉ∈Ｖ（Ｇ）－｛ｘ｝（ｉ－１，２），使｜Ｎ（ｙｉ）∩Ｋｉ（ｘ）｜≥２，且｜Ｎ（ｙｉ）∩Ｎ（Ｋｉ＋１（ｘ））｛ｘ｝｜≥２（ｉ模２），那么称无爪图Ｇ是强２－阶邻域连通的，其中Ｋ１（ｘ），Ｋ２（ｘ）分别表示Ｇ［Ｎ（ｘ）］的两个分支．本文证明了：连通且强２－阶邻域连通的无爪图是Ｈａｍｉｌｔｏｎ图．     

3—连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ－４的３－连通ｋ－正则无爪图是Ｈａｍｉｔｏｎ的。     

组合最优化问题的近似算法(续)

<正> 3.装箱问题(B)有 n 个物体 e_1,e_2,…,e_n,设 e_i 的体积为 w_i.现在有一批相同的箱子 B_1,B_2,…,每只箱子的容量都为 C.我们要求把这 n 个物件都装入箱子里,使得每个箱子里的装入物件总体积不超过 C,并且用的箱子个数最小.装箱问题在运筹学和计算机科学中,都有较广泛的应用,如下料问题,计算机记忆单元的分配问题等.不难看出,装箱问题是集合划分问题的对偶.装箱问题有几个ε-近似算法,我们只介绍其中的三个,并且只对其中之一给予证明.(a)NF 算法.     

具有 Hamilton 性的次序列

朱永津、刘振宏在[1]中给出了两类次序列,它们不满足 Chvátal 条件,其中一类甚至不满足 Bondy 和 Chvátal 的 n-闭包是完全图的条件,但它们却都保证了图的Hamilton 圈的存在.本文推广了[1]的结果,得到了更为广泛的两大类具有前述性质的次序列.     

最优消除顺序

本文从一个离散最优化问题的算法复杂性出发,提出了图论中一个新的而有趣的问题:图的节点最优消除顺序.这一问题不仅有实用价值,而且有理论意义.本文只得到该问题的部分结果,并提出了若干待解决的问题,供有兴趣的读者进行研究.     

过指定点的最小单圈图

本文提出并解决了在无向图上求过两个指定点的最小单圈图问题。它有一定的实际背景,反映了图论中某些结构的内在联系,同时,对Travelling salesman问题,提供了比1-树更好的下界估计。     

竞赛图具有弧泛回路性的一个充分条件

关于竞赛图的弧泛迴路性问题,Alspach证明了正则竞赛图具有此性质.朱永津、田丰证明了若竞赛图 T 中任意一个弧(v,v_0)都满足条件 d~+(v_0)+d~-(v)≥p-2,这里 p 为 T 的顶点数,则当 p≥7时,T 中过任一弧存在迴路系列 C_4,C_5,…,C_p.本文提出并证明了若 T 满足以下条件:当 d~+(v)<1/2(p-1)时,在 v 的外邻集 O(v)中有一点 u,d~+(u)≥1/2(p-1);当 d~+(v_1),d~+(v_2)<1/2(p-1)时,有 u_1,u_2∈O(v_1)∪O(v_2),d~+(u_1),d~+(u_2)≥1/2(p-1),且对入次亦满足相应的条件,则当 p≥9和最小次数δ≥4时,过 T 的每一个弧存在迴路系列 c_6,c_7,…,c_p.此充分条件不要求顶点次数的正则性和几乎正则性,对 T 的不正则度 q=(?)|d~+(v)-d~-(v)|一般来说也没有限制.     

两类 Hamilton 次序列

无向图中 Hamilton 圈存在的充分条件,虽有一些,但几乎都包含在 Chvátal 的次序列条件和 Bondy 与 Chvátal 的 n-稳定闭包是完全图的条件里.本文提出两类次序列,虽然它们都不满足 Chvátal 条件,并且也有一个不满足闭包是完全图的条件,但是却都保证了图的 Hamilton 圈的存在性.从而为进一步从次序列方面研究图的 Hamilton 性,提供了新的依据.     

有趣的图论

近二十年来,在数学论坛上出现了一门十分活跃的学科—图论。无论从它的文章数量、杂志种类、应用广泛程度以及每年国际性学术会议的数量上,都显示了图论的发达兴旺景象。本文试图尽量多用一些简单有趣的例子,对图论的部分内容给以简单介绍。     

有趣的图论(续)

5.点染色问题 设G是一个平面图,由G我们可以按下述方式构造出G的一个对偶图G~*,G~*中的点对应于G的面,G~*中两个点i和j有边相连,当且仅当G中对应的面i和j相邻,另外G~*的边与G的边是一一对应的。例如图2.11中的实线图为G而虚线图为G~*