简单无向图中H回路搜索的避圈算法

本文提出一个在简单无向图中搜索H回路的新算法,我们称之为避圈算法。我们分析的算法对于n阶简单无向图的时间复杂性亦为O(n^2·2~n),但VAX机上的程序实现和对2000例以上的64阶图的运行表明。只要G是H图,算法就可以立即找到一条H回路。而其它算法对于同样图例在10小时的连续运行时间里未能找到一条H回路。据此,我们猜测,本算法(或其改进)的时空复杂性远比我们分析的保守结果好得多,或者至少本算法也象著名的单纯形算法那样。理论复杂性很高但实际复杂性很低,因为很少出现最坏情况。本文是[1]中结论的直接结果。