dBHz’s BlogdBHz’s Blog/
discrete mathematics
Search
discrete mathematics

discrete mathematics

时间
Mar 16, 2022 01:28 PM
Tags
notes
Brief Info
学得还行...考的一般

离散数学

第一章 图论基本概念

支撑子图与导出子图
图的对称差G_1 \oplus G_2 = (V_1 \cup V_2, E_1 \oplus E_2)
邻点集\Gamma(v) 外邻集\Gamma^+(v)（直接后继） 内邻集\Gamma^-(v)（直接前趋）
邻接矩阵：每行每列都是点，可表示自环不可表示重边 ->权矩阵
关联矩阵：行是边，列是点，可表示重边不可表示自环
边列表：两个m维数组，相当于关联矩阵的压缩
正向表：对结点编号，将每个点的直接后继集中存放
逆向表：对结点编号，将每个点的直接前趋集中存放
邻接表：基本单元是表结点，类似下图这种结构

第二章 道路与回路（1）

简单有向道路：没有重复边
初级有向道路：没有重复点
Warshall 算法
  • Begin
  • P \leftarrow A
    • for i = 1 to n
      • for j = 1 to n
        • for k = 1 to n
          • p_{jk}\leftarrow p_{jk} \vee(p_{ji}\wedge p_{ik})
  • end
Warshall 算法的结果是图G的道路矩阵
无向连通图欧拉回路充要条件：G中各结点的度都是偶数
哈密顿道路充分条件：简单图G中任意两结点v_i,v_j之间恒有d(v_i)+d(v_j)\ge n-1（先证连通性，再用极长初级道路找回路，再加点）
引理：若简单图G中存在H道路，但不存在H回路，不妨设H道路两端点为v_1和v_n，则：d(v_1)+d(v_n)\le n-1
哈密顿回路充分条件：简单图G中任意两结点v_i,v_j之间恒有d(v_1)+d(v_n)\ge n或每个结点的度都大于等于n/2
引理：v_i,v_j不相邻，且满足d(v_i)+d(v_j)\ge n，则G存在H回路的充要条件是G+(v_i,v_j)有H回路。
据此引理可以得到闭合图的概念，记做C(G)，是唯一的
简单图G存在哈密顿回路的充要条件：其闭合图存在哈密顿回路

第二章 道路与回路（2）

旅行商问题：分枝与界法（计算复杂度仍是n!）
  • 边按照权值排序
  • 搜索H回路
  • 搜索过程中记录最短回路，并随时更新界值
  • 搜索过程中如果路径长度超过界值，则剪枝
便宜算法
  • 条件：无向正权图，任意三结点之间权值符合三角不等式
  • 算法：
    • if w(j, t_1)-w(t, t_1) \le w(j, t_2)-w(t, t_2)
    • then\ j插入到t, t_1之间
    • else\ j插入到t, t_2之间
  • 最佳解O_n便宜算法解T_n则\frac{T_n}{O_n} < 2
Dijkstra（狄克斯特拉）算法
  • 初始时所有点都是临时性标注，标注值为无穷大
  • 将源节点标注为0，且为永久性标注，并令其为工作结点；
  • 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的临时标注，则用新计算得到的和重新标注该结点
  • 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；
  • 重复第四、五步，直到目的结点成为工作结点。
  • 算法复杂度为O(n^2)
Ford算法（解决负权边问题）
  • （1）\pi(i) = 0, \pi(i)=\infty,i=2,3,...,n
  • （2）i从2到n，令：
      • \pi(i)\leftarrow min[\pi(i),min(\mathop{\pi(j)}\limits_{j\in\Gamma_i^-}+w_{ji})]
  • （3）若全部\pi(i)都没有变化，结束。否则转（2）
PT图
  • 用结点表示工序
  • 用有向边表示工序间的次序关系
  • 用边权值表示工序所需要的时间
引理2.7.1 不存在有向回路的图G中，一定存在负度及正度为零的结点。
引理2.7.2 设G不存在有向回路，可以将G的结点重新编号为v_1^{'},v_2^{'},...,v_n^{'}，使得对任意的边(v_i^{'},v_j^{'})\in E(G)，都有i<j（不断删去d^-(v_i)=0的点）
PT图中最长路径算法：
  • （1）对结点重新编号为v_1^{'},v_2^{'},...,v_n^{'}
  • （2）\pi(v_1^{'})\leftarrow0
  • （3）对于j从2到n，令
      • \pi(v_j^{'})=\mathop{max}\limits_{v_i^{'}\in\Gamma^-(v_j^{'}))}(\pi(v_i^{'})+w(v_i{'+v_j^{'})})
  • （4）End！
算法复杂性为O(m)
设\tau(v_i)为最晚启动时间，则\tau(v_i)=\pi(v_n)-\pi(v_i,v_n)，其中\pi(v_i,v_n)是工序i到完工最少需要的时间，也是v_i到v_n的最长路的长度。
允许延误时间为：t(v_i)=\pi(v_i)-\tau(v_i)

第三章 树（1）

一个不含任何回路的连通图称为树，用T表示，T中边称为树枝，度为1的结点称为树叶。
割边：
定理3.1.1 e=(u,v)是割边，当且仅当e不属于G的任何回路。
定理3.1.2设T是结点数为n\ge2的树，则下列性质等价：
  • （1）T连通且无回路
  • （2）T连通且每条边都是割边
  • （3）T连通且有n-1条边
  • （4）T有n-1条边且无回路
  • （5）T的任意两结点间有唯一道路
  • （6）T无回路，但在任意两结点间加上一条边后恰有一个回路
支撑树（生成树），余树
基本关联矩阵：关联矩阵划去任意结点v_k所对应的行，得到的(n-1)\times m的矩阵
关联矩阵B任一k阶子方阵的det为0,1或-1
有向连通图G关联矩阵的ran = n-1
设B_k为有向连通图G的基本关联矩阵，C为G中的一个回路，则C中各边所对应B_k各列线性相关。
推论：设H是连通图G的子图，如果H含有回路，则H的诸边对应的G的基本关联矩阵各列线性相关。
令B_k是有向连通图G的基本关联矩阵，那么B_k的任意n-1阶子阵行列式非零的充要条件是其各列对应的边构成G的一棵支撑树。

第三章 树（2）

（Binet-Cauchy定理）已知两个矩阵A=(a_{ij})_{m\times n}和B=(b_{ij})_{n\times m}，满足m\le n，则：
$$det(AB)=\sum_iA_iB_i$$
其中A_i，B_i都是m阶行列式
A_i是从A中取不同的m列所成的行列式；
B_i是从B中取相应的m行构成的行列式；
结果为全部组合求和
设B_k是有向连通图G的某一基本关联矩阵，则G的不同支撑树的数目是
$$det(B_kB_k^T)$$
计算不含特定边e的树的数目：无视它
计算必含特定边e的树的数目：两个点缩为一个
计算无向连通图的支撑树的数目：任意给定方向
𝑇为有向树，若𝑇中存在某结点v_0 的负度为0，其余结点负度为1，则称𝑇为以v_0为根的外向树，或称根树，用\overrightarrow{T}表示。
特点：除v_0外，每行只有一个-1
重新编号后，使每条边e=(v_i,v_j)都满足v_i的编号小于v_j的编号，同时e=(v_i,v_j)的编号为e_j
编号后为上三角矩阵（对角线均为-1）
非根树基本关联矩阵可调整为上三角矩阵且对角线上将出现“1”元素
令\overrightarrow{B_k}表示有向连通图G的基本关联矩阵B_k中全部1元素改为0后的矩阵。
  • 如果该树为非根树，则对角线将出现“0”元素（行列式为零）
  • 如果该树为根树，则对角线全部为“-1”元素（行列式绝对值为1）
有向连通图G中以v_k为根的根树数目是
$$det(\overrightarrow{B_k}B_k^T)$$
计算不含特定边e的根树的数目：无视它
计算必含特定边e的根树的数目：先计算全部根树，再减去不含e的（或者删去所有以e的终点为终点的边）
有向连通图G的全部初级回路构成的矩阵，称为G的完全回路矩阵，记为C_e：
$$c_{ij}=\left\{ \begin{aligned} 1 & , & e_j\in C_i且与回路C_i方向一致 \\ -1 & , & e_j\in C_i且与回路C_i方向相反 \\ 0 & , & 其他 \end{aligned} \right.$$
当有向图G=(V,E)的支撑树𝑇确定后，每条余树边𝒆所对应的回路称为基本回路，该回路的方向与𝒆的方向一致。由全部基本回路构成的矩阵称为G的基本回路矩阵，记为C_f
调整边的顺序后可以构成C_f=(I\ C_{f_{12}})。于是可知基本回路矩阵的秩为m-(n-1)
有向连通图G=(V,E)的关联矩阵𝐵和完全回路矩阵C_e的边次序一致时，恒有：
$$BC_e^T=0$$
推论：有向连通图的基本关联矩阵B_k，基本回路矩阵C_f，在边次序一致的情况下，有
$$B_kC_f^T=0$$
于是可由基本关联矩阵计算得到基本回路矩阵
有向连通图G完全回路矩阵的秩为m-(n - 1)
证明：由于基本回路矩阵秩为m-(n-1)，且为完全回路矩阵子阵，故完全回路矩阵秩\ge m-(n-1)
sylvester定理：设A,B分别为n×m与m×s的矩阵，则ran(AB)≥ran(A)＋ran(B)－m
A取关联矩阵B，B取完全回路矩阵C_e^T
回路矩阵：有向连通图G中m-(n-1)个互相独立的回路组成的矩阵，称为G的回路矩阵，记为C。
性质：
  • 基本回路矩阵C_f是回路矩阵
  • BC^T=0其中B与C的边次序一致
  • C=P*C_f，其P为非奇异方阵，C与C_f边次序一致
连通图G=(V,E)的回路矩阵𝐶的任一(𝑚－𝑛＋1)阶子阵行列式非零，当且仅当这些列对应于G的某一棵余树。
任意一个回路都可以由回路矩阵各行向量线性表示！
有向连通图G的全部割集构成的矩 阵，称为G的完全割集矩阵，记为S_e：
$$s_{ij}=\left\{\begin{aligned}1 & , & e_j\in S_i且与割集S_i方向一致 \\-1 & , & e_j\in S_i且与回路S_i方向相反 \\0 & , & 其他\end{aligned}\right.$$
完全割集矩阵规模为(2^{n-1}-1)\times m
设𝑇是连通图G的一棵树，e_i是树枝。对应e_i存在G的割集S_i，S_i只包括一条树枝e_i及某些余树枝，且与e_i的方向一致。 此时称S_i为G的对应树𝑇的一个基本割集.
给定有向连通图G的一棵树𝑇，由对应𝑇的全部基本割集组成的矩阵称为基本割集矩阵，记为S_f。其秩为n-1。
调换位置后可得：
$$S_f=(S_{f11}\ I)$$
当有向连通图G的完全回路矩阵C_e和完全割集矩阵S_ e的边次序一致时，有
$$S_eC_e^T=0$$
有向连通图G=(V,E)完全割集矩阵的秩为(𝑛－1) 。
证明：由于基本割集矩阵，完全割集矩阵的秩\ge(n-1)
进而根据sylvester定理
割集矩阵：有向连通图G中(𝑛－1)个互相独立的割集组成的矩阵，称为G的割集矩阵。
性质：
  • 基本割集矩阵S_ f是割集矩阵
  • SC^T=0其中S与C的边次序一致
  • S=P*S_f，其中P为非奇异方阵，S与S_f边次序一致
有向连通图G=(V,E)的割集矩阵S的任一(𝑛－1)阶子阵行列式非零，当且仅当这些列对应于G的某棵树。

第三章 树（3）

令 𝑡1和 𝑡2是G中距离为1的两棵树，且𝑡1 − 𝑡2 = (𝑒)，𝑡2 − 𝑡1 = (𝑏)，则𝑏 ∈ 𝑆𝑒(𝑡1)；反之，若𝑏 ∈ 𝑆𝑒(𝑡1)，则𝑡2 = 𝑡1 ⊕ (𝑒,𝑏)是树。
给定G的一棵树t_0，令t_1,t_2,...,t_p是G中全部满足\left\{\begin{aligned}t_0-t_i=(e)\\t_i-t_0=(b_i)\end{aligned}\right.
(i=1,2,...,p)的树，则s_e(t_0)=(e,b_1,b_2,...,b_p)。
反之。若b_i\in s_e(t_0)，则t_i=t_0\oplus(e,b_i)是树
令T^e=\left\{t_0\oplus (e,b)|b\in s_e(t_0),b\ne e\right\}
即为用e的基本割集每条边逐一替代e后生成的新树集合。
对于根结点为v_ 0的完全二叉树𝑇，如果每个树叶结点𝑣𝑖都赋予一个正实数𝑤𝑖，则称之为赋权二叉树。 从根到树叶的路径P(v_0,v_i)所包含的边数记为该路径的长度l_i，这样二叉树T带权的路径总长为WPL=\sum_iw_il_i。
带权总长度即为计算机中的存储长度。
Huffman树构造算法：
  1. 对权序列中的权值进行排序，满足：
      2. $$w_{i_1}\le w_{i_2}\le ...\le w_{i_n}$$
  1. 计算w_i=w_{i_1}+w_{i_2}作为中间结点v_i的权，其左儿子是v_{i_1}，右儿子是v_{i_2}。在权序列中删去w_{i_1},w_{i_2}，加入w_i，同时n\leftarrow n-1。
      2. 若n=1，结束，否则转（1）
最小生成树问题
Kruskal算法：（适用于稀疏图）
  • 将边权值从小到大排序
  • 将边从小到大逐一加入T中，如果出现回路，则跳过当前边，知道出现树为止
T=(V,E')是赋权连通图G=(V,E)的最短树，当且仅当对任意的余树边e\in E-E'， 回路C^e(C^e\subseteq E'+e)满足其边权：
$$w(e)\ge w(a),a\in C^e(a\ne e)$$
Prim算法：（适用于稠密图）
  • 选取初始结点v，构成集合U，其余结点为V-U
  • 选取V-U中距离U最近的结点u，并入集合U，并将相应的边并入树T
  • 直到所有结点都进入U
设U是赋权连通图G=(V,E)的结点真子集，e为二端点分跨在U与V－U的最短边， 则G中最短树T一定包含e
破圈法：（适用于手工计算）
  • 见到回路就去掉最长边
第四章 平面图与图的着色
面（域），边界，无限域，内部域，相邻
欧拉公式：设G是平面连通图，则G的域的数目是d=m-n+2
推论：
  • 若k个连通支，则n-m+d=k+1
  • 对一般平面图G，恒有n-m+d\ge 2
极大平面图性质
  • G是连通的
  • G不存在割边
  • G的每个域的边界数都是3
  • 3d=2m
极大平面图G中，有m=3n-6\ \ \ d=2n-4
简单平面图G满足：m\le3n-6 \ \ d\le2n-4（可知K_5是非平面图）
简单平面图G中存在度小于6的结点（于是K_7不是平面图）
二部图（二分图）
K_5和K_{3,3}是非平面图，分别记为K^{(1)}和K^{(2)}图
如果图结点数小于5或边数小于9，则可平面
在K^{(1)}和K^{(2)}图上增加一些度为2的结点得到K^{(1)}型和K^{(2)}型图，统称K型图。（库拉图斯基定理）
G是可平面图的充要条件是G不存在K型子图。
实际操作中如何判断平面性？
  1. 非连通则检查每个连通支
  1. 存在自环则移去自环
  1. 存在割点则分离
  1. 移去度为2的结点和其关联的边，在原来两邻点间加入边
  1. 移去重边
  1. 反复运用4,5，最后如果：
      • m<9或n<5可平面
      • m>3n-6非平面
      • 不满足上述，进一步测试
对偶图
  • 平面图有唯一对偶图G^*（有对偶图的充要条件是平面图（利用库拉图斯基定理））
  • 对偶图G^*是连通图
  • 若G是平面连通图，那么(G^*)^*=G
平面连通图与对偶图之间满足：
$$m=m^*\ \ \ d=n^* \ \ \ n = d^*$$
初级回路对应对偶图中割集
四色猜想（注意一下五色的证明，化为对偶图）
色数（相邻结点不同色，\gamma(G)）与边色数（相邻边不同色\beta(G)）
边着色可以转化为点着色
常见色数：
  • K_n-e：n-1
  • 二分图：2
  • 偶结点数回路：2
  • 奇结点数回路：3
  • 树：2
  • 连通图：\ge2
非空图G，\gamma(G)=2当且仅当它没有奇回路
对于任意一个图G，设d_0=maxd(v_i)，则：
$$\gamma(G)\le d_0+1$$
对任意图G，色数小于等于G的导出子图𝐺’中最小的结点度的最大值（找满足\gamma(H)=k的最小导出子图）
求色数：连接or合并的min
常见色数多项式
  • 空图：f(G,t)=t^n
  • 完全图：f(K_n,t)=f(K_{n-1},t)(t-n+1)
求色数多项式：连接and合并的和

第五章 匹配与网络流（1）

每个点最多与一条着色边相关联——匹配
与边相关联——饱和点
最大匹配 交互道路 可增广道路
M是G的最大匹配当且仅当G中不存在关于M的可增广道路（每个结点度不超过2（匹配））
匈牙利算法：
  • 输入为二分图；初始匹配
  • 结点标记为0，尚未搜索
  • 结点标记为1，饱和结点
  • 结点标记为2，无法扩大匹配的结点
  1. 给定任意初始匹配M，给饱和点标记1
  1. 判断X中各结点是否都有非零标记
      2. 2.1 是，M为最大匹配，结束
      2.2 否，找一个“0”标记结点x_0\in X,U\leftarrow \left\{x_0\right\},V\leftarrow\phi
  1. 判断集合U的邻点集\Tau(U)=V？
      2. 3.1 是，给x_0标记“2”，转2
      3.2 否，在\Gamma(U)-V中找一点y_i,检查其是否标“1”
      3.2.1 是，则说明有边(y_i,z)\in M令U\leftarrow U\bigcup \left\{z\right\},V\rightarrow V\bigcup \left\{y_i\right\}，转3
      3.2.2 否，则说明找到了从x_0到y_i的增广路P，令M\leftarrow M\oplus P，给x_0,y_i标“1”，转2
完全匹配与完美匹配
（Hall定理）二分图中X到Y存在完全匹配的充要条件是：对于X的任意子集A，恒有\Gamma(A)\ge A。
推论：若d(x_i)\ge k \ \ d(y_i)\le k那么X到Y存在完全匹配
X到Y的最大匹配的边数是X-\delta(G)，其中\delta(G)为A-\Gamma(A)的最大值
覆盖与最小覆盖数
最大匹配数r等于最小覆盖数s
边权值为非负实数时，存在多个完全匹配时，权值最大或最小的叫做最佳匹配。
最大权匹配算法
  1. 在矩阵C的每行选一最大值作为本行的界值l(x_i)
      2. 每列的界值初值定为0
      构造矩阵B，B=(b_{ij})_{n\times n}\ \ b_{ij}=l(x_i)+l(y_j)-c_{ij}
  1. 在B中对0元素进行最小覆盖，覆盖数为r
      2. 2.1 若覆盖数r=n，则\sum(l(x_i)+l(y_j))即为最大值，结束
      2.2 在未覆盖的元素中选取最小非零元\delta
      对于双重覆盖元，b_{ij}=b_{ij}+\delta
      对于未覆盖元，b_{ij}=b_{ij}-\delta
  1. 修改界值
      2. 若x_i行没被覆盖，则l(x_i)=l(x_i)-\delta
      若y_i列已被覆盖，则l(y_j)=l(y_j)+\delta
      删除覆盖标记，转2
最小成本算法（转化为最大权匹配算法）

第五章 匹配与网络流（2）

网络流图：汇源，容量，允许流，流量，饱和边，非饱和边，最大流
最大流量等于最小切割容量
Ford和Fulkerson算法
  1. 任一容许流分布
  1. 给s标号(-,\infty)
  1. 若存在一个未标结点v，可通过正，反向标号得到标号，标之并转4，否则转7
  1. 若v=t，转5，否则转3
  1. 设v的标号是(d_v,\delta_v)，
    1. 若d_v=u^+，则令f(u,v)=f(u,v)+\delta_t
    2. 若d_v=u^-，则令f(u,v)=f(u,v)-\delta_t
  1. 若u=s，删去全部标号并转2，否则令v=u，转5
  1. 结束
Edmonds-Karp算法（每次沿最短路增流）
  1. 任一容许流分布
  1. 给s标号(-,\infty)
  1. 按照先标号先检查的原则，选择最早标号但尚未检查的结点u，检查其所有未标号的邻结点v，标之并转4，如果所有结点都已经检查，则转7（算法结束）
  1. 若t得到了标号，则令v＝t，转5，否则转3
  1. 设v的标号是(d_v,\delta_v)，
    1. 若d_v=u^+，则令f(u,v)=f(u,v)+\delta_t
    2. 若d_v=u^-，则令f(u,v)=f(u,v)-\delta_t
  1. 若u=s，删去全部标号并转2，否则令v=u，转5
  1. 结束
增流路不超过m(n+2)/2条
瓶颈

第七章 代数结构基本知识

左可逆充要条件：f为单射
右可逆充要条件：f为满射
同构：f为双射
同态：f为映射（不一定满） 同态象
单一同态 满同态（~）

第八章 群（1）

半群（满足结合律的二元运算）也适用广义结合律
幺群（有单位元e）
交换幺群
循环幺群（生成元）
循环幺群是可交换幺群
子半群 子幺群
同态 单同态 满同态 同构
设 𝑓 是从代数系统 （𝐴, •） 到（ 𝐵, ∗） 的满同态，S 是 A 的非空子集。𝑓（𝑆） 表示 𝑆中的元素在𝑓 下的象的集合，那么：
  1. 若（S，•）是半群，则（f（S），∗）也是半群
  1. 若（S，•）是幺群，则（f（S），∗）也是幺群
阿贝尔群
半群+左单位元+左逆元=群
半群+对任意a，b，ax=b和ya=b在G中都有解=群
阶r\le|G|
子群充要条件：
  1. 对原有运算封闭
  1. 相同单位元
  1. 相同逆元
或者：\forall a,b\in H都有ab^{-1}\in H

第八章 群（2）

循环群G=<a>，a称作生成元
  1. 若O<a>=\infty则G中只有生成元a或a^{-1}
  1. 若O<a>=n则G中有\phi(n)个生成元
无限循环群的子群也是无限循环群
n阶循环群的子群生成元阶数是n的因数
对n的每个正因子d，G有且只有一个d阶子群
循环群同构
  1. 无限阶都与(Z，+)同构
  1. n阶都与（Z_n,+）同构
  1. 任意两个阶相同的循环群同构
变换（A到A）
全部变换记为M(A)，若|A|=n，则M(A)=n^n
一一变换群E(A)（所有一一变换关于乘法构成的群），其子群叫做变换群
n元置换 置换群
S_n表示n!个n元置换的集合
S_n对于置换乘法构成群，称为n次对称群。
S_n子群称为n元置换群
轮换 恒等置换 对换
S_n中任意一个n元置换，一定可以表示成不相交轮换的乘积的形式，并且表示法是唯一的。
对换个数的奇偶性与逆序数相同，记做N(\sigma)，奇置换，偶置换
S_n中的所有偶置换的集合构成子群，记做A_n，称为交错群。若n\ge 2则|A_n|=\frac12n!
Cayley定理 任意群G与一个变换群同构（f_a）
推论 设G是n阶有限子群，则G与S_n的一个子群（置换群）同构
子群H在G中的一个左陪集：
$$aH=\left\{ah|h\in H\right\}$$
性质：
  1. H=eH,a\in aH
  1. |aH|=|H|
  1. a\in H \Leftrightarrow aH=H
  1. \forall x\in aH，都有xH=aH，并叫a是aH的一个陪集代表
  1. aH=bH\Leftrightarrow a\in bH或b\in aH\Leftrightarrow b^{-1}a\in H或a^{-1}b\in H
  1. \forall a,b\in G，若非aH=bH，必有aH\bigcap bH =\emptyset
群G关于其子群H的左陪集的个数，称为H在G中的指数，记作[G:H]。
lagrange定理
$$[G:1]=[G:H][H:1]$$
推论：
  1. 设有限群G的阶为m，则G中任意元素的阶都是n的因子，且适合x^n=e
  1. 阶为素数p的群G是循环群
  1. 设A,B是群G的两个有限子群，则：
      2. $$|AB|=\frac{|A||B|}{|A\cap B|}$$
      其中AB=\left\{ab|a\in A,b\in B\right\}

第八章 群（3）

正规子群：左右陪集不区分
H是G的子群，则以下条件等价：
  1. H\lhd G（H是G的正规子群or不变子群）
  1. \forall g\in G,gHg^{-1}=H
  1. \forall g\in G,gHg^{-1} \subseteq H
  1. \forall g\in G,h\in H,ghg^{-1}\in H
设A,B是G的两个子群，则：
  1. 若A\lhd G,B\lhd G，则A\cap B\lhd G, AB\lhd G
  1. 若A\lhd G,B\le G，则A\cap B\lhd B,AB\le G
设H是G的一个正规子群，G/H表示H的所有陪集构成的集合即
$$G/H=\left\{gH|g\in G\right\}$$
关于陪集乘法成群，称为G关于H的商群
陪集乘法对于G/H是一个二元运算（aHbH=abH\in G/H）
同态映射 单一同态 满同态 同构
群G和任意一个商群构成满同态
同态的叠加
与群同构的是群 群的同态象也是群
同态保持单位元、逆元
Ker是正规子群
f(a)=f(b)的充要条件是b\in aK
同态核的同一陪集所有元素映射到一个象！！！
单同态\Leftrightarrow Kerf=e
同态基本定理：G的任一商群都是G的同态象；反之，若G‘是G的同态象，f是G到G’的满同态，则G'\cong G/K

Loading Comments...

Copyright 2021 dBHz