离散

1.1

无序对

无序积 &

多重集

重复度

无向图G

顶点集V 无序积

边集E

有向图D 多重子集

n个定点的图被称为n阶图

无边为零图

平凡图： 1阶0图

空图：无顶点

环：两端点重合

关联，关联次数：与边相接的边数

相邻：共同点或共同边

有向图始点，终点

相邻也要遵从有向

孤立点：没边

1.2

度d：连接的边数，环算2

握手定理：度和为2*边

有向图出就是出度，如就是入度

悬挂顶点：度1，悬挂边

最大(小)(入/出)度△/δ

度数为奇数的顶点为偶数个

有向图入度=出度=边数

度数列：每个节点的度的数组

1.3

平行边：关联同一对顶点

重数：平行边的数量

有向平行边：简称平行边

多重图：有平行边

简单图：无环无平行边

无Kn_n(有)向完全图：m=n(n-1)(/2)

k-正则图：无向图且度都为k

无≥3(有≥2)向圈图，无向的简称圈图

轮图：≥4无向圈图加一点全连

n方体图：以2进制记录每一个点，只与其只有一位不同的点相连

1.4

(真)子图，母图：V和E都(或真)包含于

生成子图：只去边

导出子图G[V’/E’]：根据选择的V’或E‘将相关的另一个集合中的元素全部保留

补图：对于无向图，补成完全图的边集所得图

1.5

同构：完全一致，可以通过调整边和点的位置来使其相同

2.1

通路：a→b的一条路

长度：边的数量

回路：a=b

简单通/回路：边异

初级通/回路(路径/圈)：边异且点异

奇/偶圈

复杂通/回路：一条边多次出现

表示：v0e0v1⋯vn−1en−1vnv_0e_0v_1\cdots v_{n-1}e_{n-1}v_n

若u能到v，那么存在通路，那么必有≤n-1

若u存在简单回路，那么必有≤n

2.2

连通的：存在通路

连通图：平凡图/任意两点都连通

连通分支：互相能到的一个部分，其R={<x,y>}为等价关系，即自反，对称，传递

p(G)：连通分支的数量，=1时为连通图

短程线d(a,b)：最短路

距离：短程线长度

删除：G-V’或G-E’

点(边)割集：这些点(边)删除正好使连通分支增加

割点(边)(桥)：只有一个点(边)的点割集

完全图无点割集

0图都无

边割集最多增加1个，而点割集≥1

点(边)连通度κ(G)/λ(G):最小的点(边)割集大小或者（或者让点数只剩1个）

平凡图，都0

完全图，点 n-1

κ≤λ≤δ

2.3

可达：a→b

相互可达：a→b，b→a

短程线d<a,b>

弱连通图：去掉方向为连通图

单向连通图：任意两个顶点一个可达另一个 存在经过每个点的一条通路

强联通：互相可达 存在经过每个点的一条回路

3.1

关联矩阵M(G)n×m_{n×m}：点和边的关联次数

每列和2，每行和度，总和握手

3.2

有向关联矩阵M(D)n×m_{n×m}：始点1，终点-1

可算入度出度，列和0

3.3

有向邻接矩阵A(D)n×n_{n×n}：i到j的边数

Aijl^l_{ij}：i到j长度为l的通路数

Bijl^l_{ij}：i到j长度≤l的通路数

3.4

有向可达矩阵P(D)n×n_{n×n}：i能不能到j iff Bijn−1^{n-1}_{ij}>0

无向图的可达和邻接类似

4.1

二部图：将图中的顶点分为两个点集，任意一条边的两个端点各属于一个点集

完全二部图Kr,sK_{r,s}：两个点集两两互联

两个点集被称为互补顶点子集

判定：无奇数长度回路

一般判定：直接分类标记

匹配：指二部图的一个子图，一个顶点的边数≤1

极大匹配：多一条边就不是匹配了

完备匹配：一个点集都配备了一条边

完美匹配：双方都完备匹配

hall定理(相异性条件)(充要)：v1中的任意k各顶点至少与v2中的任意k各顶点相邻

t条件(充分)：存在整数t，使v1中每个顶点的度≥t，且v2中每个顶点的度≤t

4.2

欧拉通路：经过每条边=1的通路

欧拉回路：是回路的欧拉通路

欧拉图：有欧拉回路

无向图判定条件：连通图且无奇度顶点

有向图判定条件：连通图且所有顶点入度=出度

有向图欧拉通路非回路判定条件：连通图且有2个不满足，一个差值为1，一个为-1

4.3

哈密顿通路：经过每个点=1的通路

哈密顿回路(必为初级)：是回路的哈密顿通路

哈密顿图：有哈密顿回路

删除v1个顶点，p≤v1

有割点的不是哈密顿图

因为是回路

(充分)：n≥3无向简单图，任意一对不相邻顶点度和≥n-1存在通路，≥n为哈密顿图

最小度≥n2\frac{n}{2}也是哈密顿图

n≥2有向图，略去方向存在Kn_n，则存在哈密顿通路

4.4

平面图仅讨论无向图

平面嵌入：画在平面上无交叉边

平面图：有平面嵌入的图

面Ri_i：平面图的一个区域

无限面：最外侧的无线区域

内部面：除无限面的其他面

边界：一个面的边界

次数deg(Ri_i)：边界的长度，即边界的边数

面的次数之和*2=边数，即握手定理

极大平面图：加入一条边就不是平面图了

性质：连通且当n≥3时每个面的次数都为3

n-m+r=k+1 k为连通分支数

若为连通平面图，且min次数≥l，则m≤ll−2(n−2)m\le \frac{l}{l-2}(n-2)

同胚：同构或反复插入或消去2度顶点后同构

收缩：重合两点，删除关联边，剩下保留

库拉图斯基定理(判定)：iff不含与k5或k33同胚的子图

                                   iff不含可收缩到k5或k33的子图

对偶图：面作点，若有共边，则相连，经过这条边，为连通平面图

点面数互换，边数不变

对偶图vi的度=ri的次数

点着色：对每个顶点涂色，要求相邻颜色不同

k-可着色的：能用k中颜色点着色

任何平面图都是4-可着色的

1.1

无向树(树)：连通不含回路的图

森林：每个连通分支都是树

平凡树：平凡图

树叶：d=1

分支点：d≥2

非平凡树的叶子数≥2

不同度数列对应的树必不同构，但同度数列对应的树也可能不同构

1.2

生成树：是树的生成子图

树枝：在生成树中的边

弦：非树枝

余树：弦的导出子图

无向连通图都存在生成树

权：边上的实数

带权图

kruskal(避圈法)

2

有向树：略去方向为树的有向图

根树：一个顶点入度=0，其他入度=1

树根

树叶

内点：除去树根和树叶的点

分支点：内点和树根

层数：树根到该点的通路长度，即树根为0层

树高：max层

根子树：其实就是子树

有序树：将每一层的顶点都规定次序

r元树：每个节点的孩子≤r

r元正则树：每个节点的孩子=r

完全的：树叶的层数相同

最优二叉树(哈夫曼树)：选最小的合并

最佳前缀码：根据频率生成哈夫曼树

前中后遍历

周游/行遍：每个顶点访问次数=1

前缀表示法：从右到左每个运算符对后面紧挨的两个数运算

后缀：从左到右~对前面~

1.1

S上的二元运算：S运算S→S

封闭：S上的二元运算对S封闭

S上的一元运算：运算S→S

1.2

交换律

结合律

幂等律x2=xx^2=x

分配律

吸收律：在交换律的基础上，x*(x+y)=x且x+(x*y)=x

代数常数：单位元，零元，可逆元，逆元

(左/右)单位元：ex=x

(左/右)零元：θx=θ

(左/右)逆元：yx=e

可逆：存在逆元

若存在左右单位元，则相等且为单位元

若存在左右逆元，则相等且为逆元

消去律

2.1

代数系统(代数)V：非空集合S和其上的k个1/2元运算，

<S,f1,f2,…>一般二元运算写在前，S被称为载体，还可写上代数常数

2.2

同类型的代数系统：运算个数，对应的元数，代数常数个数都相同

同种的代数系统：对应运算性质相同的同类型的代数系统

2.3

(真)子代数(同种)：S中的一个(真)子集S‘，对所有运算封闭且代数常数相同

平凡子代数：V自身，其代数常数若封闭则为最小平凡子代数

积代数：两个同类型代数系统<A,+>,<B,>，<a1,b1>- <a2,b2>=<a1+a2,b1b2>，则<A×B,->为两代数系统的积代数，反之两者为其因子代数

特性：同类型，保留除消去律以外的所有运算性质，且保留代数常数

2.4

同态映射(同态)：f:V1→V2(同类型)，f(x+y)=f(x)*f(y)

单同态：单射

满同态(同态像)：满射

同构≌：双射

自同态：到自身的同态

零同态：f(x)=0x，x∈Z

同态：能够保留除消去律以外的大多性质和代数常数

同构：拥有完全相同的性质，被认为是同一代数系统

3.1

半群：<S,+>，+可结合

含幺半群(独异点)：有单位元的半群

若可结合，x0=ex^0=e

子半群，子独异点(要求e要保留)

独异点的同态要求f(e1)=e2f(e_1)=e_2

3.2

群：每个元素都有逆元的独异点

有限群：有限元素群

无限群：无限元素群

阶|G|：元素的个数

平凡群：只有单位元

交换群(阿贝尔群)：二元运算还是可交换的群

有负次方：即(-1)*n

元素的阶|a|：min k,ak=emin\ k,a^k=e

无限阶元：不存在阶

像矩阵一样,(a1⋯an)−1=an−1⋯a1−1(a_1\cdots a_n)^{-1}=a_n^{-1}\cdots a_1^{-1}

ax=b和ya=b都有唯一解，a−1b和ba−1a^{-1}b和ba^{-1}

群可以使用消去律

iff k是阶的整数倍的时候时ak=ea^k=e

逆元的阶相同

∣b−1ab∣=∣a∣|b^{-1}ab|=|a|

∣ab∣=∣ba∣|ab|=|ba|

(真)子群

平凡子群：G和{e}

判定定理1：ab∈G且a−1a^{-1}∈G

判定定理2：ab−1^{-1}∈G

由a生成的子群：{ak∣k是整数^k|k是整数}

群的中心：{a|对任意x，ax=xa}

交换群的中心就是自身

子群格

零同态：G1→G2,f(x)=e2f(x)=e_2

内自同构：G→G,f(x)=axa−1f(x)=axa^{-1}

循环群

a为生成元

无限循环群，只有两个生成元，生成元和它的逆元

n阶循环群，与n互质的a^k

n元置换σ(i)