关于哈密顿轨问题最小流模型的讨论 |
| |
作者姓名: | 宁宣熙 |
| |
作者单位: | 南京航空航天大学经济管理学院 南京,210016,中国 |
| |
摘 要: | MasonIri论证了网络最小流问题可以在多项式时间内转换为哈密顿问题的模型与方法。本文利用一个反例指出了在该证明中使用的模型存在有不严格的地方。在此基础上,利用网络最小生成流的概念提出了一个修正模型,并证明了无环最小生成流问题可以在多项式时间内转换为哈密顿圈问题。文中最后指出,这一新的模型为解决在有向图内构造哈密顿轨的有效算法提供了一个新的思路和方法
|
关 键 词: | 图论 哈密顿轨 生成流 |
DISCUSSION ON MINIMUM FLOW MODEL FOR ITS RELATIONSHIP WITH HAMILTONIAN PATH PROBLEM |
| |
Authors: | NING Xuan-xi |
| |
Abstract: | A negative example shows that the model given by Mason Iri is used to prove that the relationship between the minimum flow problem and the Hamiltonian path problem in a (directed) network, is not rigorous. A new model called minimum spanning flow in a network is established to revise the old one. It is proved that the problem of determining whether there is a Hamiltonian path from a specified vertex s to another t on a given digraph can be reducible at polynomial time to the problem of constructing a minimum spanning flow in a two-terminal extended network s,t , with the unit capacity for all arcs. |
| |
Keywords: | graph theory Hamiltonian path spanning flow |
|
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |