[数据结构与算法]1 群的定义

定义

??群按照严格的定义是满足以下四个条件的一个集合加一个二元运算符，这个运算符，一般用乘法符号表示，但不一定是算术乘法哈。
??1. 封闭性closure,集合内任意两个元素和这个运算符运算的结果还在这个群内。
??2. 结合律associativity，也就是$(ab)c=a(bc)$
??3. 单位元identity存在，一般符号是e，也就是$?a:ae=e$，$?$是任意的意思。
??4. 逆元inverse element存在，$?a\in G,?b\in G:ab=e$，$?$这个符号表示存在，也就是对于任意a，存在b，使得ab进行乘法运算结果为单位元e。这个特性叫可逆性invertibility。
??如果符合交换律commutative，那么这个群就属于阿贝尔群。
??群的例子比较多哈。我随便写几个：
??1. 整数和加法组成一个阿贝尔群；
??2. 去掉0的有理数和乘法，组成一个阿贝尔群；
??3. N个元素的置换构成一个置换群；
??群论在物理学里应用比较多，比如经典力学的拉格朗日方程，量子力学里的薛丁格方程等等。

乘法表

??群中集合元素为有限个的群叫做有限群，对于有限群来说，群中元素的个数被称为群的阶。有限群可以将其所有的元素运算规则全部写在一张乘法表中。我举个例子，集合为复数 { 1 , ? 1 , i , ? i } \{1,-1,i,-i\} {1,?1,i,?i},运算符为乘法的群。毫无疑问，这个群的单位元为1，它的乘法表如下：

$$\begin{array}{ccccc}?& 1& ?1& i& ?i\\ 1& 1& ?1& i& ?i\\ ?1& ?1& 1& ?i& i\\ i& i& ?i& ?1& 1\\ ?i& ?i& i& 1& ?1\end{array}$$

凯莱图

??把上述的群，用红色线条代表-1，绿色线条代表i，蓝色线条代表-1，可以画出如下的图：

??但是这个图没必要画得这么复杂，因为只要蓝色线条或绿色线条，就可以连接所有元素。所以我只用绿色线条，也就是复数i来重新画这张图：

??这种图就是凯莱图Cayley graph，图中的绿色线条i也被称为生成元。当然也可以用-1做生成元，那么凯莱图如下：

生成元表达式

??上述群有单位元和生成元i生成，所以可以用单位元加生成元来表示一个群。数学符号是$1<i>$，所以上述群也可以写成$1<?i>$。