哈密顿圈的H-变换

对求解流动售货员问题,S.Lin 设计了二线和三线调整法,在计算机上试算得到较好结果(见1]).事实上,这种调整可以说是哈密顿圈的一种变换.本文研究哈密顿图中一切可能的变换,给出它的一般模式——哈密顿圈的 H- 变换,从而证明了哈密顿图中任一对哈密顿圈均可由 H-变换互相转化,并进而得到哈密顿图具有唯一哈密顿圈的充要条件。关于唯一哈密顿圈问题在国内外受到人们的一定注意,见2],其极图性质见3]、4]。本文结果平行于 J.Abrham and A.Kotzig 关于欧拉迹的变换的工作(见5])。