代数结构与图论

图的基本概念

代数系统

• 单位元和零元如果存在，则是唯一的
• 当代数系统的元素大于1时，单位元与零元不相等
• 对于可结合的二元运算，可逆元素的逆元唯一
• 同类型的代数系统：运算个数相同，对应运算的元数相同，代数常数的个数相同 同种代数系统：在同类型代数系统基础上，运算的性质相同
• 子代数证明：元素是S 子集，且满足运算封闭
• 任何的代数系统都有子代数，子代数与本身是同种的代数系统
• 平凡子代数：最小子代数（代数常数）与最大子代数（自己）
• 积代数的形式：<a1,b1> ·<a2,b2> = <a1oa2,b1*b2>
• 代数系统的同态与同构：f:V1–>V2 ,有f(xoy) = f(x)*f(y) ,则称是从v1 到v2 的同态映射（同态），当 f 是单射时（单同态），满射（满同态），双射（同构）

群与环

• 半群：代数系统<S,o> ,o 可结合（可结合）
• 独异点：在半群的基础上，存在单位元（可结合，单位元）
• 群：在独异点的基础上，每个元素有逆元（可结合，单位元，逆元）
• 偶阶群（群中的元素的个数为偶数）一定含有二阶元：单位元的阶为1，大于2 的阶的元素由于本身加上逆元，个数的和为偶数，对于由于二阶元的逆元为自己，在群众也是占据一个位置，刚好补上单位元的1
  群其实是可以直接写出来
  

• 注意元素的幂运算：0次幂为单位元，正数幂直接算，负数幂就用逆元的正数幂
• 元素的阶：使得a^k = e 的最小的k ，一个元素的阶与逆元的阶相等
• 对于群的运算只用留意：（a b）^-1 = b^-1 a^-1
• 群是满足消去律的：消去律的前提就是满足结合律，以及排除零元，而群自身就满足结合律，以及没有零元
• 如何证明子群：在H 非空的前提下
  （1）满足封闭性，满足逆元
  （2）将封闭性与逆元结合：ab^-1 属于H
  （3）H 为非空的有限子集，只用证明封闭即可
• 子群的交仍然是子群，子群的并不一定是子群
• 元素a 的生成子群：< a >
• 陪集：Ha 为H 在G 中的右陪集
• 陪集的性质：
  （1）He = H
  （2）a 属于 Ha (至少有个单位元）
  （3）a 属于 Hb <=> ab^-1 <=> Ha = Hb （证明陪集的相等）
  （4）H 的所有的右陪集集合构成G 的一个划分
  （5）Ha 与 H 是等势的
• 拉格朗日定理：G 为有限群，H 为 子群 ，G 的阶 = 子群的阶 * 陪集的个数 （陪集之间是相互独立的，且与子群等势，广义并就是G)
  重要推论：
  （1）n 阶群的元素的阶是n 的正因子，即 a^n =e
  （2）阶为素数的群一定是循环群
• 循环群：（简单来说就是，由生成元生成的群）
  （1）无限循环群G只有两个生成元，a 和 a^-1
  （2）n 阶循环群G，有从0到n-1 与n 互素的数的个数个生成元（这个是G 的生成元的个数），G 的生成元：对于任何小于n 且与 n 互质的自然数 r,a^r 是G 的生成元，且每一个正因子 d ,都有一个 d 阶子群（<a ^(n/d)> 为相对应子群的生成元）
• 区别求生成元以及子群：
  结合子群的阶以及相对应的生成元来求即可
• 环：<S,+,*> :<S,+> 满足交换群（交换律，结合律，单位元，逆元）
  <S, * > 满足半群（结合律，单位元） ， * 对 + 满足分配律
• 相关性质：
  （1）加法中的单位元为乘法中的零元
  （2）a(b-c) = ab -ac (分配律）
• 交换环：乘法* 满足交换律
• 含幺环：乘法* 存在单位元
• 无零因子环： ab= 0=> a=0 或者 b = 0 (a,b 至少其中一个为加法中的单位元
• 整环：满足交换环，含幺环，无零因子环
• 域：整环的基础上，去除加法的单位元，每个元素都有逆元
• 模n 的整数环，如果n 为素数，那么为域
• 整数环是整环，但是不是域（元素的逆不一定是整数）

格与布尔代数

• 格：偏序关系<x,y> 存在最小上界与最大下界
• 如何证明一个代数系统是格？证明封闭性，证明^,V 成立
• 对偶原理：将<= 换成>= ,^ 换成 v ，那么称为相对应的对偶命题，原命题与对偶命题的真值相同
• 格的性质，v,^ 是满足交换律，结合律，幂等律，吸收律，注意不满足分配律
• 注意偏序与运算的关系，以及相对应的保序关系
• 子格：S非空，S 在 父格中，关于运算^ 和v 封闭
  对于下面左上角的题目，对于{a,b,d,f} 来说，b,d 的最大下界是c ,但是c 不在{a,b,d,f}中，所以不是子格
• 分配格：满足分配律
• 分配格的判定：
  （1）满足相对应的定义，但是只用证明一个式子（对偶）
  （2）判断不是分配格，不含钻石格与五角格同构的子格
  （3）小于5元的格都是分配格
  （4）任何一条链都是分配格
• 有补格：补元：对于a , b 与a 的最大下界是0，最小上界是1，（补元不唯一）
• 有界格：每个元素大于0，小于1
• 无限格也可能是有界格，例如幂集格小于自己，大于空集
• 有界分配格，如果元素存在补元，则补元唯一存在
• 有补分配格（布尔代数）：
  
• 任何等势的布尔代数都同构于某一幂集格，任何有限的布尔代数的基数为 2^n,布尔代数中的元素的补元是唯一的
• 布尔代数与原子