代数系统
tips:
R是实数集合 ,I为整数集合
1.代数系统的基本性质
代数系统:一个非空集合A连同若干个定义在该集合上的运算所组成的系统称为代数系统 ,例如 <Z,+>
- 封闭性 : *是A上的二元运算,对于A中的任意元素x,y都有 x*y∈A,则称*上是封闭的.(减在自然数集合上不是封闭的)
- 可交换性 : 对于任意元素 x y 都满足 x * y = y * x
- 可结合性 : 对于任意元素 x y 都满足 (x * y) * z = x * (y * z)
- 分配律
- 吸收律
- 等幂性
- 幺元(单位元)<A,>,若有$e_$ ∈A 对于 $ \forall$x∈A,有 $e_$ * x =x,则称$e_$为A中关于的左幺元 同理可得右幺元 如果 e ∈A,且e是左幺元和右幺元,那么惟一的。
- 零元:<A,>,若有$e_$ ∈A 对于 $ \forall$x∈A,有 $e_$ * x =$e_$,e称为的左零元,唯一
- 逆元:e是幺元,如果对某个a∈A,$\exists $b∈A,使得 b * a = e,则称b是a的左逆元
2.群
广群:封闭为广群
半群:封闭可结合为半群
独异点: 存在幺元的半群为独异点(封闭、可结合、存在幺元)
==群==:满足 1.独异点 2,每个元素都有逆元称作是群
有限群,无限群:若<A,*>是群,且A是有限集,则称其为有限群,|A|=n ,n称作是有限群的阶. 如果A是无限集那么其为无限群。
群的性质
- 群中不可能满足零元
- 群满足消去律
- 如果是循环群,那么必定是阿贝尔群
==阿贝尔群(交换群)==: <G,*>是群,若*在G中可交换,那么称为阿贝尔群
阿贝尔判定:对 $\forall$a,b∈G,当且仅当都有(a*b)*(a*b) = (a*a)*(b*b) ,才是阿贝尔群
==循环群==:在G中存在a,使得G中的任一元都可以写成a的幂,a称作生成元,(==生成元未必唯一==)
3.同构和同态
格与布尔代数
**格:是一种特殊的偏序集,但是==任两个元素均有最小上界和最大下界==**并且都是唯一的
格的基本性质:
- 自反性
- 反对称性
- 传递性
- 保序性
- ==交换性==
- ==结合性==
- ==吸收性==
子格: 如果A中这两个运算是封闭的,则称B是A的子格
分配格:任意两个元素满足
模格:
有界格:
有补格:任意一个元素都有 $\forall x,x∈A,\exists y,y∈A \Rightarrow x\bigwedge y=0 \bigcap x \bigvee y =1 $
布尔格:有补分配格
图
图的基本概念
V表示节点集合 E表示路的集合
-
节点的度数 deg(v),是出度与入度的和 最小度 $\delta(G)$ 最大度 $\Delta(G)$
节点度数的三个定理:
- 节点度数总和等于边数的两倍
- 度数为奇数的节点必定是偶数个
- 入度之和等于出度之和
-
图的同构满足的关系:(必要条件)
- 节点数目一一对应
- 边数相等
- 度数相同的节点数目相同
路与回路
通路:若一路上的所有节点都不相同,称作通路
迹:若一路上的所有边都不相同,那么称作是迹
连通:若节点u 和 v存在一条路,则称两节点互通
- 点割集:当一个图删除一个$V_{1}$所有的节点之后,所得的子图为非连通图,但是删除$V_{1}$的任何真子集后,所得的图都为连通图,称作这个集合为G的一个点割集
- 割点:若点割集中只有一个节点,那么这个结点称为割点.
- 点连通度:产生一个非连通图所需要删除的点的最少个数 记作$K(G)$
- 非连通图的点连通度为0
- 存在割点的连通图的点连通度为1
- 完全图$K_$的点连通度为p-1
- 边割集,同点割集,集合为$E_{1}$
- 割桥(桥):同割点
- 边连 和v之间的最短路的长度, 记作$d<u,v>$ 如果不可达,记作$d<u,v> = \infty$
- 连通性:
- 强连通:任意两个节 n
- 弱连通:略去边的方向,得到的无向图是连通的
图的矩阵表示
邻接矩阵: 在G中 , n阶方阵$A(G) = (a_)$称为G的邻接矩阵
可达性矩阵:定义 n阶方阵 $P=(p_)$为可达性矩阵
可达性矩阵计算公式:
$B_ = A + A{2}+A{3}+...+A^$
欧拉图和汉密尔顿图
欧拉图(边的遍历问题)
欧拉路:通过每边一次并且仅一次的==路==
欧拉回路:通过每边一次并且仅一次的==回路==
半欧拉图:存在欧拉路的图
欧拉图:存在欧拉回路的图
==无向图半欧拉图判定方法==:无向图G具有一条欧拉路,当且仅当G是连通的,且只有零个或者两个奇数度节点.
==无向图欧拉图判定方法==:无向图G具有一条欧拉路,当且仅当G是连通的,只有零个奇数度节点.
==有向图欧拉图判定方法==:当且仅当G是连通的,且每个节点的入度等于出度
汉密尔顿图(点的遍历问题)
==汉密尔顿图==:经过每个节点恰好一次的==回路==
