文献综述
信息与计算科学 哈密顿图的判定与应用
图论(graphic theory)是一门既古老又年轻的学科. 它诞生于18世纪上半叶. 到19世纪下半叶这个领域才发展成为数学的一个系统的分支, 直到20世纪上半叶, 这门学科才有自己的著作出现. 自20世纪下半叶开始, 随着计算机科学与技术的发展, 图的理论研究和应用研究才得到迅速广泛的重视, 图论作为一个数学的分支, 才真正确立了自己的地位.
哈密顿(爱尔兰科学家)在1859年提出一个名叫“周游世界”游戏问题是: 能否遍历正12面体的每个顶点一次且一次后回到原地. 由此引申出哈密顿图的定义: 如果图G上有一条经过图G所用顶点一次且仅一次的回路, 则称此回路为哈密顿回路, 具有哈密顿回路的图称为哈密顿图.
哈密顿图具有六个领域: 哈密顿圈, H连通, 泛圈, 点泛圈, 边泛圈, 泛连通. 哈密顿图是有哈密顿圈的图. 至今没有一个像欧拉图的充要条件那样的“非平凡的” (不是定义的同义反复)关于哈密顿图、哈密顿通路的充分必要条件, 但关于他们的充分性和必要性分别有一些研究成果. 而哈密顿图不光在金字塔图、扇面蜂巢图及马图上有体现它性质的研究, 且在四正则连环图和彼得森中有它独特的应用. 而且哈密顿图在哈密顿通路、哈密顿轨、多哈密顿轨问题上也有很多细致的研究和应用.
1984年时在连续10年排名加拿大第一大学的范更华教授得到名垂青史的“范定理”: 2连通n阶图G的距离是2的任意两点x,y均有max{d(x),d(y)}?c/2, 则G是有c圈, 当
c?n时是哈密顿图. 当然, 关于如此著名的范定理, 各国不少专家也对范定理企求做出改
进发展. 1987年Wojda院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人Benhocine教授2人合作仅局部推广上面范定理. 又如法国 Benhocine教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响, 但他至今仅有25篇数学论文且18篇是哈密顿图的, 他是排名哈密顿图研究前30名大师之一.
哈密顿图已经历了一个多世纪的跋涉, 容易攀登的时代已经过去了, 其进展已非常不容易, 如此即使是世界级的大师泰斗, 不论你多么聪明利害都好, 面对的下一个问题猜想都永远是相关学科的全世界的专家经过多年仍不能解决的, 就是想做点进展都非常不容易, 每
一篇论文都是超越最权威大师的成果. 哈密顿图的难如两个权威说“非常不容易”. 但它却具有重大历史意义以及广泛而重要的应用价值.
现国际数学联盟主席是哈密顿图权威, 并且琼州大学赵克文和美国权威等合作改进耶鲁大学Ore院士等大师权威的代表性结果已在“哈密顿图”居世界领先.
在国内, 宁宣熙和宁安琪提出了哈密顿圈自组织算法的实证研究结果和其在哈密顿图判定上的应用, 介绍了SOA算法在大约 12000个规模不同(n?10?4000,m?20?8000)的一般任意图中构造哈密顿圈的实证研究结果, 验证了SOA算法的可靠性和时间的多项式性. 在此基础上论证了SOA算法用于判断一般任意图是否为哈密顿图的可行性, 并用一些实例进行了实证研究. 在阻塞流理论的研究中, 利用网络最小阻塞流与哈密顿轨之间的关系建立了哈密顿轨问题的无环最小支撑流模型. 通过这个模型可以把一步内构造无环最小支撑流这一数学难题分解成分别在多项式时间内完成的两个阶段, 从而为解决这一数学难题找到了新的思路, 开发研制了在一般任意图中构造哈密顿圈的自组织算法(或SOA算法). 在文献[1?4], 全面详细地介绍了作者经过10多年潜心研究这一算法的理论及进行12000余例实证研究的结果. 到目前为止尚未遇到反例. 由于不少学者根据NPC理论认定这是绝对不可能的, 因此作者只好通过大量的实证研究来显示这一多项式算法存在的可能性. 况且, 作者进行这项研究的目的并不是为了解决计算复杂性理论中NP是否等于P的问题, 而是为学术研究和工程应用提供一种在一般图中构造哈密顿圈的实用有效工具. 即便有人能找到反例, 说明SOA算法只不过是像线性规划单纯形算法那样, 是一个实用的好算法, 应当说这也是一个很幸运的结果. 因为有了它, 不但可以在用相关定理(如范定理或者其它更新的定理)判定存在哈密顿圈的一般图中构造出至少一条具体的哈密顿圈, 也可以对超出这些定理范围之外的一般图进行是否是哈密顿图的判定, 这岂不也是一项有实用价值的成果. 如果这些研究结果还能对数学家们在解决哈密顿图判定的理论研究上有所启迪和帮助, 那么这项研究就更有意义了.
回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法, 该算法可以用来求出问题的全部解, 也可以在求出问题的一个解之后停止对问题的求解, 即只求该问题是否有解
[5]. 哈密顿通路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径. 宁
夏大学数学计算机学院的刘向娇博士在他的《用回溯法求哈密顿通路》论文中论述了用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题, 并用具体的算法来实现它. 算法搜索至解空间树的任一结点时, 总是先判断该结点是否肯定不包含问题的解. 如果肯定不包
含, 则跳过对以该结点为根的子树的系统搜索, 逐层向其祖先结点回溯. 否则, 进入该子树, 继续按深度优先的策略进行搜索. 回溯法在用来求问题的所有解时, 要回溯到根, 且根结点的所有子树都已被搜索遍才结束[6]. 而回溯法在用来求问题的任一解时, 只要搜索到问题的一个解就可以结束. 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法, 它适用于解一些组合数较大的问题.
在求解一些问题(如走迷宫、地图着色等问题)时, 题目的要求可能是求出原问题的一种或所有可能的解决方案. 这类问题的解往往是由一个一个的步骤或状态所构成的, 每一步骤又有若干种可能的决策方案; 由于没有固定、明确的数学解析方法, 往往要采用搜索的做法, 即从某一个初始状态出发, 不断地向前(即下一个状态)搜索, 以期最终达到目标状态, 从而得到原问题的一个解或所有的解. 在搜索的过程中, 由于问题本身及所采取的搜索方法的特点(如在缺乏全局及足够的前瞻信息的情况下进行搜索等)[7], 会导致走到某一状态就走不下去的情况, 这时, 就必须回头(即回到上一步, 而不是回到最初的状态), 再尝试其他的可能性, 换一个方向或方法再试试. 这样, 不断地向前探索、回溯, 再向前、再回溯, 直至最终得出问题的解, 或者一路回溯到出发点(出现这种情况即表示原问题无解)[8]. 注意, 这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径, 而是采用深度优先的方式, 沿着一条路径, 尽可能深入地向前探索.
用回溯法解哈密顿通路问题首先要画出问题的解空间树, 该解空间树是一棵最大度是
n的树(其中n为图中的顶点数), 树中只有第一个结点的度是n, 其余结点的度都为
n?1(该结点不用与其自身相连). 在编写算法时可以通过判断该边在图的邻接矩阵中的值
来剪枝, 如果其值不是1则说明该边不存在则剪枝不用搜索. 由于在求图的哈密顿通路时走过的顶点不能再重复走, 所以要对已经遍历过的顶点做一个标记, 如果在搜索时找到的是一个带有标记的顶点, 那么该路径也是不可行的, 应剪去.
参考文献
[1] 宁宣熙, 堵塞流理论及其应用[M]. 北京: 科学出版社, 2005.
[2] Xuanxi Ning and Angelika Ning, The Blocking Flow Theory and its Application to Hamiltonian Graph Problems[J]. Shaker Verlag. Aachen, 2006, 21(2): 286~318.
[3] Ning Xuanxi. The Minimum Spanning Flow in a Network and its Self-organization Principle[J]. The International Journal of Systems & Cybernetics, 2004, 33(2): 331~338. [4] Xuanxi Ning and Angelika Ning, The Minimum Spanning Flow Model of the Hamiltonian Path Problem in a Digraph and its Polynomial Algorithm[J]. Information Processing and Management, 2006, 38(3): 356~361.
[5] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003. [6] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003. [7] 王小东. 算法分析与设计[M]. 北京: 清华大学出版社, 1900.
[8] 付寒冰, 周恒为. 数据结构中常用的三类算法[J]. 伊犁师范学院学报, 1997, 17(2): 12~138.
[9] 宁安琪, 宁宣熙. 金字塔图的哈密顿图性质研究[J]. 南京航空航天大学经济与管理学院学报, 2006, 21(3): 17~23.
[10] 田媛, 刘铎. 金字塔图存在哈密顿回路的构造性证明[J]. 清华大学学报, 2007, 13(2): 38~52.
[11] 屈婉玲, 耿素云. 离散数学[M]. 北京: 高等教育出版社, 2008.
[12] J.邦詹森, G.古廷. 有向图的理论、算法及其应用[M]. 北京: 科学出版社, 2009. [13] 左孝凌. 离散数学[M]. 北京: 经济科学出版社, 2000.
哈密顿图的判定与应用【文献综述】
