一種尋找有限代數系統(tǒng)同構變換的算法

肖奕鑫+鄭偉珊

【摘 要】同構不僅在數學上有重要意義，在人工智能與機器學習等應用領域也有重要意義，但傳統(tǒng)文獻往往只給出同構的定義，故本文將給出一種快速尋找有限代數系統(tǒng)全部同構變換的算法，并且使用匯編語言實現(xiàn)該算法來檢測其速度。

【關鍵詞】有限代數系統(tǒng)；同構變換；匯編程序

一、引 言

關于兩個代數系統(tǒng)同構[1，2]的定義：

二、算法分析

本文通過先把具有相同特征的元素歸為同類，然后在每個類中配對的方法來降低檢驗次數，如果同類元素個數不一致則可直接判定不同構。

每個元素左乘或右乘代數系統(tǒng)中的所有元素等價于一個自變換，而有限的自變換可以用有限個可能帶分支的循環(huán)來表示，這樣就可以把循環(huán)結構一樣的元素歸為一類。我們把含有該元素的循環(huán)定義為該元素的主循環(huán)。把主循環(huán)上由該元素乘冪生成的元素稱為主循環(huán)鏈，我們把每個元素主循環(huán)鏈中包含的元素個數稱為該元素的特征，顯然同類元素具有相同的特征（但特征相同不一定是同類元素），我們把各類按特征從大到小進行排列，如果每個類中的元素的對應在逐步排列過程被確定，則其主循環(huán)鏈的元素的對應也會被確定，從而可以先配對而跳過后邊的排列，最終減少排列的次數。

（一）本文算法

通過上邊的分析，我整理得出同構檢測算法如下：

步驟1. 把第一個代數系統(tǒng)的乘法表中的元素字符串進行二進制編號后寫入內存。

步驟2. 計算第一個代數系統(tǒng)各元素的特征和循環(huán)結構，并把元素乘法表按特征從大到小進行重新排列，特征相同按循環(huán)結構中其他循環(huán)個數大小排列，對具有相同循環(huán)結構的元素進行歸類，由于按循環(huán)結構排列，所以同類元素是連續(xù)的，歸類只需記錄類的起始點和終止點，并保存其排列變換于A。

步驟3. 把第二個代數系統(tǒng)的乘法表中的元素字符串進行二進制編號后寫入內存。

步驟4. 如果兩個代數系統(tǒng)的元素個數不一樣則顯示元素個數不同而不同構然后退出程序。

步驟5. 計算第二個代數系統(tǒng)各元素的特征和循環(huán)結構，把循環(huán)結構和第一個代數系統(tǒng)一樣的元素對應起來，如果有元素對應不上則顯示該元素沒有對應元而不同構然后退出程序。

步驟6. 保存第二個代數系統(tǒng)各元素的對應排列于B。

步驟7. 定義配對鎖變量，并初始化為0。

步驟8. 如果存在只有一個元素的類，則將這些類的元素先固定對應（同時把各配對元素配對鎖設為0），并把各元素主循環(huán)鏈中由該元素乘冪形成的元素固定對應（同時把各配對元素配對鎖設為0），如果對應過程發(fā)現(xiàn)對應元素已配對且與先前配對不一致則顯示固定配對沖突而不同構，然后退出程序。如果發(fā)現(xiàn)對應元素配對不同類則顯示固定配對不同類而不同構，然后退出程序。

步驟9. 判斷是不是所有元素都配對完畢，如果配對完畢則跳到步驟13，否則，鎖變量加1，對下一類元素中從該類起始點開始尋找未被選取的元素。

步驟10. 配對并上鎖（即記下鎖變量），并把該元素主循環(huán)鏈中由該元素乘冪形成的元素固定對應，如果對應過程發(fā)現(xiàn)對應元素已配對且與先前配對不一致，則跳到步驟11，如果全部一致則跳到步驟9。

步驟11. 清除鎖變量下對位的對應，并從選擇同類中的下一元素，如果本類元素已選完（已到達終止點）則跳到步驟12，否則，跳到步驟10。

步驟12. 鎖變量減1，如果鎖變量為0則顯示已不存在同構映射并退出程序，否則跳轉到步驟11。

步驟13. 按照配對法則對全部元素的乘積進行同構檢測，如果檢測不一致則跳到步驟14，否則跳到步驟15。

步驟14. 判斷鎖變量是否為0，若是則顯示已不存在同構映射并退出程序，否則跳到步驟11。

步驟15. 顯示存在同構映射并根據配對法則和排列A，B把同構變換記錄在變換文件中，并提示是否尋找下一個同構變換，如果用戶點擊是則跳到步驟11繼續(xù)判斷，否則退出程序。

（二）實例驗證

26階循環(huán)群自同構程序運行輸出如下圖：

第一列第二行到第十二行可以看到的元素都是與26互質的數，這些結果與數學上循環(huán)群的性質是完全一致的。

（三）算法評價

本文的算法對全部元素都是單一元或者單一元的冪元覆蓋全部元素的代數系統(tǒng)只需要進行一次檢驗就可以知道是否同構，但對于只有一類元素且全部元素都是一階元的代數系統(tǒng)這種極端情況就只能使用全排列檢驗。

作者簡介：

肖奕鑫，講師，理學碩士，應用數學。

鄭偉珊，講師，理學博士，應用數學。

參考文獻：

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

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