| 摘要: |
| 分析由延长而形成哈密顿回路、欧拉回路的特点,得出求图G(n,m)的最大回路算法:给定始结点xi和始边ei(xj).采用最长路回延长法,对点xi和边ei(xj)分别求最长路回HE序列,在对点xi求最长路回HE序列中,当出现长度为n的点回路的最长项,边ei(xj)出现长度为m的边回路的最长项,或延长后所得路径中没有元素,便结束延长;如对点xi有长度为n的最大点回路最长项,则G(n,m)为哈密顿图;如对边ei(xj)有长度为m的最大边回路最长项,则G(n,m)为欧拉图. |
| 关键词: 哈密顿图 欧拉图 点回路 边回路 回路 |
| DOI： |
| 投稿时间：2005-04-05修订日期：2005-05-30 |
| 基金项目: |
|
| A Distinguishing Method of Hamilton Graphs and Euler Graphs |
|
ZHOU Bing-sheng1, GAO Xiang-yang2
|
| (1.Department of Information Management, Nanjing University, Nanjing, Jiangsu, 210008, China;2.Jiangsu Maritime Technical College, Nanjing, Jiangsu, 211170, China) |
| Abstract: |
| This paper puts forward the concepts of maximal node-cycle,maximal edge-cycle and maximal cycle.Hamilton cycle of graph G(n,m) is the maximal node-cycle,Euier cycle is the maximal edge-cycle.Analyzing the characteristic of the node cycle and edge cycle by extension,We get the algorithm of the maximal node-cycle of G(n,m).According to the gived initial node xi and initial edge ei(xj),Using the longest path-cycle extension algorithm,we get the relevant longest path-cycle HE sequence.If there is the maximal node-cycle item,G(n,m) is Hamilton cycle.If there is the maximal edge-cycle item,G(n,m) is Euier cycle.The distinguish between Hamilton graph and Euier graph can be generalized the question of maximal node-cycle. |
| Key words: Hamilton graph Euler graph node-cycle edge-cycle cycle |
