置換群與Cayley圖.pdf

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

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