一种寻找有限代数系统同构变换的算法

肖奕鑫+郑伟珊

【摘 要】同构不仅在数学上有重要意义，在人工智能与机器学习等应用领域也有重要意义，但传统文献往往只给出同构的定义，故本文将给出一种快速寻找有限代数系统全部同构变换的算法，并且使用汇编语言实现该算法来检测其速度。

【关键词】有限代数系统；同构变换；汇编程序

一、引 言

关于两个代数系统同构[1，2]的定义：

二、算法分析

本文通过先把具有相同特征的元素归为同类，然后在每个类中配对的方法来降低检验次数，如果同类元素个数不一致则可直接判定不同构。

每个元素左乘或右乘代数系统中的所有元素等价于一个自变换，而有限的自变换可以用有限个可能带分支的循环来表示，这样就可以把循环结构一样的元素归为一类。我们把含有该元素的循环定义为该元素的主循环。把主循环上由该元素乘幂生成的元素称为主循环链，我们把每个元素主循环链中包含的元素个数称为该元素的特征，显然同类元素具有相同的特征（但特征相同不一定是同类元素），我们把各类按特征从大到小进行排列，如果每个类中的元素的对应在逐步排列过程被确定，则其主循环链的元素的对应也会被确定，从而可以先配对而跳过后边的排列，最终减少排列的次数。

（一）本文算法

通过上边的分析，我整理得出同构检测算法如下：

步骤1. 把第一个代数系统的乘法表中的元素字符串进行二进制编号后写入内存。

步骤2. 计算第一个代数系统各元素的特征和循环结构，并把元素乘法表按特征从大到小进行重新排列，特征相同按循环结构中其他循环个数大小排列，对具有相同循环结构的元素进行归类，由于按循环结构排列，所以同类元素是连续的，归类只需记录类的起始点和终止点，并保存其排列变换于A。

步骤3. 把第二个代数系统的乘法表中的元素字符串进行二进制编号后写入内存。

步骤4. 如果两个代数系统的元素个数不一样则显示元素个数不同而不同构然后退出程序。

步骤5. 计算第二个代数系统各元素的特征和循环结构，把循环结构和第一个代数系统一样的元素对应起来，如果有元素对应不上则显示该元素没有对应元而不同构然后退出程序。

步骤6. 保存第二个代数系统各元素的对应排列于B。

步骤7. 定义配对锁变量，并初始化为0。

步骤8. 如果存在只有一个元素的类，则将这些类的元素先固定对应（同时把各配对元素配对锁设为0），并把各元素主循环链中由该元素乘幂形成的元素固定对应（同时把各配对元素配对锁设为0），如果对应过程发现对应元素已配对且与先前配对不一致则显示固定配对冲突而不同构，然后退出程序。如果发现对应元素配对不同类则显示固定配对不同类而不同构，然后退出程序。

步骤9. 判断是不是所有元素都配对完毕，如果配对完毕则跳到步骤13，否则，锁变量加1，对下一类元素中从该类起始点开始寻找未被选取的元素。

步骤10. 配对并上锁（即记下锁变量），并把该元素主循环链中由该元素乘幂形成的元素固定对应，如果对应过程发现对应元素已配对且与先前配对不一致，则跳到步骤11，如果全部一致则跳到步骤9。

步骤11. 清除锁变量下对位的对应，并从选择同类中的下一元素，如果本类元素已选完（已到达终止点）则跳到步骤12，否则，跳到步骤10。

步骤12. 锁变量减1，如果锁变量为0则显示已不存在同构映射并退出程序，否则跳转到步骤11。

步骤13. 按照配对法则对全部元素的乘积进行同构检测，如果检测不一致则跳到步骤14，否则跳到步骤15。

步骤14. 判断锁变量是否为0，若是则显示已不存在同构映射并退出程序，否则跳到步骤11。

步骤15. 显示存在同构映射并根据配对法则和排列A，B把同构变换记录在变换文件中，并提示是否寻找下一个同构变换，如果用户点击是则跳到步骤11继续判断，否则退出程序。

（二）实例验证

26阶循环群自同构程序运行输出如下图：

第一列第二行到第十二行可以看到的元素都是与26互质的数，这些结果与数学上循环群的性质是完全一致的。

（三）算法评价

本文的算法对全部元素都是单一元或者单一元的幂元覆盖全部元素的代数系统只需要进行一次检验就可以知道是否同构，但对于只有一类元素且全部元素都是一阶元的代数系统这种极端情况就只能使用全排列检验。

作者简介：

肖奕鑫，讲师，理学硕士，应用数学。

郑伟珊，讲师，理学博士，应用数学。

参考文献：

[1]杨子胥.近世代数[M].北京：高等教育出版社，2000：22.

[2]熊全淹.近世代數[M].武昌：武汉大学出版社，1995：46-47.