代数结构与图论

图的基本概念

• 图的阶：图中的顶点数 ，n 个顶点被称为 n 阶图
• 零图：一条边都没有 平凡图：一阶零图
• 基图：将有向图的各条有向边改成无向边所得到的无向图称为该有向图的基图
• 关联次数：可能取值为0，1，2 （分别是边与顶点没有关联，vi !=vj , 环）
• 孤立点：图中没有边关联的顶点
• 区分邻域，闭邻域等相关概念
  
  也就是对于无向图来说，邻域就是与v 相邻的顶点，闭邻域就是邻域加上顶点本身，关联集就是与顶点关联的边的合集
  对于有向图来说，后继元素就是看v 的出度的元素的合集，先驱元素就是看 v 的入度的元素的合集，邻域就是二者的并，加上顶点本身就是闭邻域
• 平行边：对于无向图：两个顶点之间的无向边多于1条，平行边的条数被称为重数；对于有向图：两个顶点之间的有向边同起点同终点的边多于1条
• 多重图与简单图：含有平行边的图是多重图，不含平行边以及环的图是简单图
• 度数：对于无向图就是顶点相邻的边的个数，一个环算2度；对于有向图，分为出度d+(v),入度d-(v)
  出度加入度 是该顶点的度，一个环有一个入度和一个出度
• 认识最大度与最小度的符号
• 度数为1的顶点是悬挂顶点，与它相关联的边是悬挂边
• 度为偶（奇）数的为偶（奇）度顶点
• 握手定理：无向图中，所有的顶点的度数之和为边数的2倍；有向图中，所有的顶点的度数之和为边数的2倍，所有顶点的入度等于出度
• 可图化：度数列之和为偶数
• 可简单图化：至少每个顶点的度数小于 n-1 ,但是具体的情况还是要画图才知道
• 图的同构：阶数相同，边数相同，度数列相同也只是必要条件
• n阶无向完全图（n(n-1)/2条边)，n 阶有向完全图（n(n-1) 条边） ，n 阶竞赛图（n(n-1)/2条边)：n 阶竞赛图的基图是无向完全图
• k-正则图：无向图中，每个顶点的度数为 k (n 阶 k - 正则图的边数 = kn/2 ,当 k 为奇数，n 一定为偶数）
• 了解子图，生成子图以及导出的子图（子图的顶点和边都可以在母图中任意找，而生成子图的顶点为全部的顶点，导出的子图的顶点可以随便找，但是边的话要按照母图的来选取）
• 补图：对于无向简单图来说，补图就是无向完全图减去原来的图中相对应的边，但是顶点数不变，补图与自身同构的图称为互补图
• 删除边，删除顶点，边的收缩，加新边：
  
• 通路与回路：
  
• 在n 阶图中，如果从顶点 u 到 v 存在通路，则 u 到 v 一定存在长度小于等于 n- 1 的通路，回路的话就是 n 的回路
• 简单不一定初级，但是初级一定简单，（顶点不同的图，边一定不会重复）
• 图的连通于连通度：
• 
• 点割集与割点，边割集与桥（割边）（分别在原来的图中减去点，边，图的连通度增加）
  
• 点连通度：点割集的最小的元素的个数--》就是改变原来的图（从连通到非连通）最少要减少的顶点数，完全图的点连通度为n-1. k-连通图
• 边连通度：同理，就是要将一个图从连通图变成非连通图所最少减少的边数， r 边 - 连通图
• 对于任意的无向完全图 ： 点连通度 < 边连通度 < 最小度
• 可达：
• 弱连通图，单向连通图，强连通图
  
• 单向连通图的判定：存在过每个顶点的通路
• 强连通图的判定：存在过每个顶点的回路
• 二部图：
  
• n 阶零图（n>=2) 是二部图
• 二部图的判定：无向图是二部图当且仅当 G 中没有奇数圈
• 关联矩阵，邻接矩阵，可达矩阵：
  
• 对于无向图的关联矩阵：
  （1）每列之和为2
  （2）每行之和为对应的顶点的度数
  （3）相同列的是平行边
  （4）某一行和为0，表示该点为孤立点
  （5）全部数加起来是边数的两倍
• 有向图的关联矩阵：
  （1）出度标1，入度标-1
  （2）每一列刚好一个1，一个-1
  （3）每一行中，出度为1 的个数，入度为-1 的个数
  （4）平行边的列是相同的
  （5）1 的个数等于 -1 的个数
• 邻接矩阵(有向图是有方向的）
  
• 可以用邻接矩阵的幂次相加，就可以得到从 vi 到 vj 的通路（可知长度）
• 有向图的可达矩阵：自身可以可达自身
  （1）对角线为1，可达的就是1，否则为0

欧拉图与哈密顿图

• 欧拉图与半欧拉图：都是经过所有的边一次仅仅一次，一个是回路一个是通路
• 平凡图是欧拉图
• 欧拉图的判定：无向图G 是欧拉图当且仅当G 是连通图且没有奇数度顶点；有向图是欧拉图当且仅当D 是强连通的且每个顶点的入度等于出度`
• 半欧拉图的判定：无向图G 是连通的且恰有两个奇数度的顶点；有向图D 是半欧拉图当且仅当 D 是单向连通的且恰有两个奇数度的顶点，其中一个入度比出度大1，另外一个出度比入度大1 ，其余顶点的入度等于出度`
• G 是非平凡的欧拉图当且仅当 G 是连通的且为若干个边不重的圈的并（圈和环并不影响欧拉性）
• 哈密顿图和半哈密顿图：都是经过所有的顶点一次仅仅一次，前者是回路后者是通路
• 平凡图是哈密顿图
• 哈密顿图的性质： p(G-V) <= |V| 就是删去某些顶点后，G- V 的连通分支数小于删去的顶点数
• 半哈密顿图的性质： p(G-V) <= |V| + 1 就是删去某些顶点后，G- V 的连通分支数小于删去的顶点数 +1
• 存在哈密顿通路：在n 阶无向简单图中，任意不相邻的顶点 u,v , d(u) + d(V) >=n-1
• 存在哈密顿回路：在n 阶无向简单图中，任意不相邻的顶点 u,v , d(u) + d(V) >=n
• 在n 阶无向简单图G中，任意不相邻的顶点 u,v , d(u) + d(V) >=n，G 为哈密顿图当且仅当GU(u,v)为哈密顿图
• n 阶竞赛图都有哈密顿图

树

• 树（无向树）：连通无回路的无向图 ； 森林：每个连通分支都是树的无向图 ；平凡树：平凡图
• 树叶：悬挂顶点 ； 分支点：度数大于等于2的顶点
• n阶 m 条边的无向图：(等价条件）
  （1）G 是树
  （2）G中任意的两个顶点之间存在唯一的路径
  （3）G 中没有回路，且 m= n-1
  （4）G 是连通的，且m=n-1
  （5）G 是连通的，且任何的边都是桥
  （6）G 中没有回路，但是在任何不同的顶点之间加一条新边后可以得到唯一一条包含新边的圈
• n 阶非平凡的无向树中至少有两片树叶
• 对于树的相关的证明一定要利用 度数与边的关系，毕竟树是特殊的图
• 生成树：如果无向图G 的生成子图T是树，则称T 是 G 的生成树。T 是G 的生成树，G 在 T 中的边称为 T 的树枝，不在的称为 弦，T 的所有的弦的导出的子图称为 T 的余树 记作 T非
• 无向图的生成树存在当且仅当G 是连通图
• n 阶m 条边无向连通图，则m>=n-1
• 基本回路与基本回路系统的的求法：（G是n 阶m 条边）
  （1）对于G 的生成树T , G 中T 的弦的个数为 m-n+1,对于每个弦，与T 中的树枝结合，可以生成一个圈，称为基本回路或者基本圈，全部的圈的总集合被称为T 的基本回路系统，m-n+1 为G 的圈的秩
  
• 无向连通图的圈的秩与生成数的选取无关，都是 m-n+1,但是具体的基本回路系统可能不同
• 任意一简单回路都可以表示为基本回路的环和
• 割集：生成树的割集，只含某一树枝，其余都是弦。不同的树枝对应的割集不同
• 割集组成基本割集，基本割集组成基本割集系统，n-1 为 G 的割集的秩（连通图的秩确定，但是具体的基本割集系统不确定）
  
• 求最小生成树 避圈法（克鲁斯卡尔算法）：从圈出发，依次找边的权值最小的边，当该边的两个端点位于两个连通分支的时候就可以加入（和已有的不构成圈），否则就去下一条边
• 根树：一个顶点的入度为0，其余顶点的入度为1的有向树 有向树：有向图的基图是无向树
• 入度为0的顶点是树根，入度为1，出度为0的顶点是树叶，入度为1，出度不为0 的顶点是内点，内点和树根称为分支点
• 层数：从树根到任意顶点的路径的长度称为层数（区别于数据结构） 树高：所有顶点的最大的层数
  
• 区分 r 叉树，r 叉有序树 ，r 叉正则树 ，r 叉正则有序树，r 叉完全正则树 ，r 叉完全正则有序树
  （上面的区分分别是是否有序， 至多 r 个儿子， 每个分支点 r 个儿子 ，每个分支点 r 个儿子加上树叶的层数等于树高）
• 最优二叉树：赫夫曼算法
• 前缀码：任意两个符号都不互为前缀码
• 由一棵正则二叉树可以产生唯一的一个2元前缀码

平面图

• 平面图：将无向图G画在平面上，除了顶点以外没有边相交 （画出来的图称为G的平面嵌入）
• 非平面图：无平面嵌入的图
• K1（平凡图），K2,K3,K4 ,K5 - e (随便减去一条边） 都是平面图
• 平面图的子图都是平面图，非平面图的母图都是非平面图
  含K3,3 以及 K5 作为子图的图都是非平面图（Kn ,n>=5, Kr,s(r,s>=3) 都是非平面图）
• 设G 是平面图，则在G 中加平行边和环之后，还是平面图
• 面：平凡图划分的每一个区域称为G 的一个面：其中有一个无限面（外部面），其余是有限面（内部面） ；包围每个面的边的回路称为面的边界， 边界的长度称为该面的次数
  
• 边界都是回路！
• 平面图所有的面的次数之和为边数的两倍（通一条边被两个面共享）
• 极大平面图：G 为简单平面图，若在G 中任意两个不相邻的顶点之间加上一条边，所得的图为非平面图K1（平凡图），K2,K3,K4 ,K5 - e (随便减去一条边）都是极大平面图
• 极大平面图是连通的，当且仅当阶数大于等于3时没有割点和桥
• 设G 是n(n>=3) 阶简单连通的平面图，G 为极大平面图当且仅当G 的每个面的次数均为3
• 极小非平面图：若在非平面图中，任意删除一条边，所得的图是平面图K5 ， K3，3
• 欧拉公式：连通平面图G 的顶点数、边数、面数 分别为 n,m,r ,则有 n-m+r =2
• 欧拉公式的推广：
  （1）对于含有 k 个连通分支的平面图G ,有 n-m+r = k+1
• 设G 是连通的平面图，且每一个面的次数最少是 L ,则 G 的边数m 和顶点数 n ,有 m<=L(n-2)/(L-2)
• 当G 为 k 个连通分支的平面图的时候，m<=L(n-k-1)/(L-2)
• 设G 是 n 阶 m 条边的 极大平面图，则 m= 3n-6
• 设G 是 n 阶 m 条边的 简单平面图，则 m<=3n-6
• 设G 是 简答平面图，则G 的最小度 小于等于 5
• 同胚：如果两个图同构或者通过反复的插入，删除2度顶点后同构，则两个图同构
• 平面图的判断：
  （1）图是平面图当且仅当 G 中不含与 K5 同胚的子图，也不含与 K3,3 同胚的子图
  （2）图是平面图当且仅当 G 中不含收缩于K5的子图,也不含能收缩于 K3,3的子图
• 平面图的对偶：
  
• 平面图的对偶图G*：
  (1)G* 是平面图，而且是平面嵌入
  (2)G* 是连通图
  (3)若e 为 G 中的环，则G* 对应 e 为桥；若 e 为桥，则 G* 对应为 环
  (4)大多数情况下，G* 为多重图
  (5)同一个平面的不同平面的嵌入的对偶图不一定同构
• 相对应的数量关系：
  
• 自对偶图：G* 与 G 同构 轮图是自对偶图

代数系统

• 单位元和零元如果存在，则是唯一的
• 当代数系统的元素大于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,布尔代数中的元素的补元是唯一的
• 布尔代数与原子