无向图同构的快速算法

规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断;要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使用高效的必要条件筛选同构函数候选集,采用基于子图同构判断超图同构的策略,提出一种新的无需回溯的快速算法,用于降低时间开销,保证判断正确.通过理论论证和实际案例测试,验证了该算法的有效性.