置換群與Cayley圖.pdf

1、眾所周知，好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是任何一個(gè)完整的分布式計(jì)算系統(tǒng)或通信網(wǎng)絡(luò)的必備因素，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)經(jīng)常被抽象為一個(gè)對(duì)稱(chēng)(無(wú)向)圖，點(diǎn)表示處理器或其他組件，邊(弧)表示兩處理器或組件之間相互通信，好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)一般具備的因素有：較少的點(diǎn)度，小的直徑，高容錯(cuò)性，小容錯(cuò)直徑等. 在已有的最有效的通信網(wǎng)絡(luò)中，最著名的是超立方體網(wǎng)絡(luò)，它已經(jīng)被廣泛應(yīng)用和深入研究，且被證明是Cayley圖的一類(lèi)。現(xiàn)在，Cayley圖在設(shè)計(jì)和分析各類(lèi)通信網(wǎng)絡(luò)中起著重要的作用

2、已成為不爭(zhēng)的事實(shí)。但是另一類(lèi)Cayley圖，置換群上的Cayley圖，如星圖，bubble-sort圖以及交錯(cuò)群圖，被證明比超立方體具有許多更好的性質(zhì)，并且許多算法被證明能有效地用于這些網(wǎng)絡(luò)。本文共分四章，圍繞對(duì)稱(chēng)群和交錯(cuò)群上Cayley圖兩個(gè)重要課題進(jìn)行討論：自同構(gòu)群和圈結(jié)構(gòu)。 設(shè)是對(duì)稱(chēng)群的一個(gè)極小對(duì)換生成集，作用在上，而作用在上，本文首先證明了，是交錯(cuò)群的極小生成集，給出了Cayley圖的自同構(gòu)群，并證明對(duì)稱(chēng)群上基于極小對(duì)換