多哈密顿轨(圈)问题的支撑流模型和其构造算法研究.pdf

多哈密顿轨(圈) 问题的支撑流模型 及其构造算法研究 [1] [2] 宁宣熙 宁安琪 （南京航空航天大学经济与管理学院，南京210016 ） Email:[1] nhning@ [2] ningangie@163.com [摘要] 多哈密顿圈问题是指判断在给定图中，从某一点V 。出发是否存在多条只经过 每个顶点一次的巡回路线。它的研究不但在学术上具有重要价值，在解决具有实际意义的多 推销员问题上也有广泛应用前景。本文建立了有向图中多哈密轨(圈) 问题的支撑流模型，并 将已成功用于一般图中构造哈密顿轨的自组织算法（SOA 算法）推广应用于多哈密顿轨(圈) 的构造中。文中给出了两种解决方案，并用实例证明了算法的可行性及实用的有效性。 关键词：哈密顿圈，多哈密顿圈，图论 中图分类号：O157.5 Spanning Flow Model of Multi-Hamiltonian Circuit Problem and Its Construction Algorithm Xuanxi Ning and Angelika Ning ( College of Economy Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016) Abstract: The Multi-Hamiltonian problem(MHC) is to determine whether there are more than one circuits from some vertex v0 which passes every vertex once and only once in a given graph. It is a very important research topic not only for its value in theory and also for its valuable use in solving multi-traveling salesman problem. In this paper a spanning flow model is set up for the MHC in a digraph, and extends the self-organization algorithm which is used successfully In constructing the Hamiltonian path in direct network to constructing MHP. The two methods are presented and their effectiveness in use is proved by examples Key words: Hamiltonian Circuit, Multi-Hamiltonian Circuit, Graph Theory, 前言 哈密顿圈问题是图论中的一个经典问题，它是指在给定图中是否存在经过图中每一个点 一次,且仅一次的一条巡回路线。所谓多哈密圈问题是这一问题的扩展，它是指在给定图中， 从某一点V 。出发是否存在多条只经过每个顶点一次的巡回路线。众所周知，旅行推销员问 题（TSP 问题）是以单一哈密顿圈问题为基础模型的，而在实际生活中，往往都是多推销员 的巡回路线问题。因此为了解决具有实际意义的多推销员问题应当首先研究一般图中多哈密 顿圈问题。 基金项目：国家自然科学基金资助项目（N 和N）