离散数学.md

离散数学.md

Tans 1,078 2020-03-20

代数系统

tips:

R是实数集合 ,I为整数集合

1.代数系统的基本性质

代数系统:一个非空集合A连同若干个定义在该集合上的运算所组成的系统称为代数系统 ,例如 <Z,+>

  1. 封闭性 : *是A上的二元运算,对于A中的任意元素x,y都有 x*y∈A,则称*上是封闭的.(减在自然数集合上不是封闭的)
  2. 可交换性 : 对于任意元素 x y 都满足 x * y = y * x
  3. 可结合性 : 对于任意元素 x y 都满足 (x * y) * z = x * (y * z)
  4. 分配律
  5. 吸收律
  6. 等幂性
  7. 幺元(单位元)<A,>,若有$e_$ ∈A 对于 $ \forall$x∈A,有 $e_$ * x =x,则称$e_$为A中关于的左幺元 同理可得右幺元 如果 e ∈A,且e是左幺元和右幺元,那么惟一的。
  8. 零元:<A,>,若有$e_$ ∈A 对于 $ \forall$x∈A,有 $e_$ * x =$e_$,e称为的左零元,唯一
  9. 逆元:e是幺元,如果对某个a∈A,$\exists $b∈A,使得 b * a = e,则称b是a的左逆元

2.群

广群:封闭为广群

半群:封闭可结合为半群

独异点: 存在幺元的半群为独异点(封闭、可结合、存在幺元)

==群==:满足 1.独异点 2,每个元素都有逆元称作是群

有限群,无限群:若<A,*>是群,且A是有限集,则称其为有限群,|A|=n ,n称作是有限群的阶. 如果A是无限集那么其为无限群。

群的性质

  1. 群中不可能满足零元
  2. 群满足消去律
  3. 如果是循环群,那么必定是阿贝尔群

==阿贝尔群(交换群)==: <G,*>是群,若*在G中可交换,那么称为阿贝尔群

阿贝尔判定:对 $\forall$a,b∈G,当且仅当都有(a*b)*(a*b) = (a*a)*(b*b) ,才是阿贝尔群

==循环群==:在G中存在a,使得G中的任一元都可以写成a的幂,a称作生成元,(==生成元未必唯一==)

3.同构和同态


格与布尔代数

**格:是一种特殊的偏序集,但是==任两个元素均有最小上界和最大下界==**并且都是唯一的

格的基本性质:

  1. 自反性
  2. 反对称性
  3. 传递性
  4. 保序性
  5. ==交换性==
  6. ==结合性==
  7. ==吸收性==

子格: 如果A中这两个运算是封闭的,则称B是A的子格

分配格:任意两个元素满足

模格:

有界格:

有补格:任意一个元素都有 $\forall x,x∈A,\exists y,y∈A \Rightarrow x\bigwedge y=0 \bigcap x \bigvee y =1 $

布尔格:有补分配格

图的基本概念

V表示节点集合 E表示路的集合

  1. 节点的度数 deg(v),是出度与入度的和 最小度 $\delta(G)$ 最大度 $\Delta(G)$

    节点度数的三个定理:

    1. 节点度数总和等于边数的两倍
    2. 度数为奇数的节点必定是偶数个
    3. 入度之和等于出度之和
  2. 图的同构满足的关系:(必要条件)

    • 节点数目一一对应
    • 边数相等
    • 度数相同的节点数目相同

路与回路

通路:若一路上的所有节点都不相同,称作通路

迹:若一路上的所有边都不相同,那么称作是迹

连通:若节点u 和 v存在一条路,则称两节点互通

  1. 点割集:当一个图删除一个$V_{1}$所有的节点之后,所得的子图为非连通图,但是删除$V_{1}$的任何真子集后,所得的图都为连通图,称作这个集合为G的一个点割集
  2. 割点:若点割集中只有一个节点,那么这个结点称为割点.
  3. 点连通度:产生一个非连通图所需要删除的点的最少个数 记作$K(G)$
    • 非连通图的点连通度为0
    • 存在割点的连通图的点连通度为1
    • 完全图$K_$的点连通度为p-1
  4. 边割集,同点割集,集合为$E_{1}$
  5. 割桥(桥):同割点
  6. 边连 和v之间的最短路的长度, 记作$d<u,v>$ 如果不可达,记作$d<u,v> = \infty$
  7. 连通性:
    1. 强连通:任意两个节 n
    2. 弱连通:略去边的方向,得到的无向图是连通的

图的矩阵表示

邻接矩阵: 在G中 , n阶方阵$A(G) = (a_)$称为G的邻接矩阵

可达性矩阵:定义 n阶方阵 $P=(p_)$为可达性矩阵

可达性矩阵计算公式:

​ $B_ = A + A{2}+A{3}+...+A^$

欧拉图和汉密尔顿图

欧拉图(边的遍历问题)

欧拉路:通过每边一次并且仅一次的==路==

欧拉回路:通过每边一次并且仅一次的==回路==

半欧拉图:存在欧拉路的图

欧拉图:存在欧拉回路的图

==无向图半欧拉图判定方法==:无向图G具有一条欧拉路,当且仅当G是连通的,且只有零个或者两个奇数度节点.

==无向图欧拉图判定方法==:无向图G具有一条欧拉路,当且仅当G是连通的,只有零个奇数度节点.

==有向图欧拉图判定方法==:当且仅当G是连通的,且每个节点的入度等于出度

汉密尔顿图(点的遍历问题)

==汉密尔顿图==:经过每个节点恰好一次的==回路==