~离散数学狗都不学~
第8章 高级计数技术
8.1 递推关系的应用
8.1.1 引言
- 从某些前项求后项的规则就叫做递推关系,如果一个序列的项满足递推关系,则这个序列就叫做递推关系的解。
8.1.2 用递推关系构造模型
屁都没有,例题倒是有,但狗都不写。
8.1.3 算法与递推关系
8.2 求解线性递推关系
8.2.1 引言
- 定义一:一个常系数的k阶线性齐次递推关系是形如
的递推关系,其中c1,c2,…,ck是实数
8.2.2 求解常系数线性齐次递推关系
看到这我只能说离散书上讲这破方程比高数书明白,焯
顺带一提,这B定理手敲是真的麻(我还是乖乖截图去吧,蛤蛤
定理一:$设c1和c_2是实数。假设r^2-c_1r-c_2=0有两个不相等的根r_1和r_2,那么序列{a_n}是递推关系a_n=c_1a{n-1}+c2a{n-2}的解,当且仅当a_n=a_1r^n_1+a_2r_2^n$
定理二:
- 定理三:
- 定理四:
8.2.3 求解常系数非齐次线性递推关系
- 定理五
- 定理六
8.3 分治算法和递推关系
8.3.1 引言
- 分治算法:将一个问题划分为许多规模较小的同一问题
8.3.2 分治递推关系
下图估计满足分治关系的函数的阶
8.4 生成函数
8.4.1 引言
第10章 图
10.1 图和图模型
顶点和边集有限的图称为有限图,否则称为无限图
每条边的两个顶点不同且两个点之间只有一条连线的图称为简单图,多条边连接相同的两个顶点的图称为多重图,把一个顶点连接到自身的边是环,包含环或者多重边的图称为伪图
不含环和多重有向边的有向图叫简单有向图
多重度是描述从一个点到另一个点有向边条数的概念
啥也不是的图就叫混合图
10.2 图的术语和几种特殊的图
10.2.2 基本术语
- 定义一:无向图中若两个端点之间有边则这两个端点邻接,这条边称为关联两个顶点。
定义三:无向图中,顶点的度是与该顶点关联的边数,记作deg(v),环为顶点的度做出双倍贡献。
度为0则称点是孤立的,如度为1则称点是悬挂的。
定理1:握手定理,顶点的度的和是边数的2倍。
定理2:无向图有偶数个度为奇数的顶点。
有向图的边(u,v)中u是起点,v是终点,环的起点和终点相同。
定义五:deg-(v)表示以v为终点的边数,称为入度,deg+(v)表示以v为起点的边数,称为出度。
定理3:入度=出度=边数。
10.2.3 一些特殊的简单图
完全图:每对不同顶点之间都只有一条边的简单图,至少有一对顶点不存在边相连的简单图称为非完全图。
圈图 n个顶点围成圈构成的图。
轮图:圈图里加一个与所有其他点相连的点。
n立方体图:n立方体图就是n立方体图。
10.2.4 二分图
- 完全二分图:可以有边的地方全都有边。
10.2.5 二分图的匹配
10.2.7 从旧图构造新图
图边的删除和增加、收缩及顶点的删除
图的并集
10.3 图的表示和图的同构
10.3.2 图的表示
- 邻接表
10.3.3 邻接矩阵
稀疏图选择邻接表,否则选择邻接矩阵
10.3.4 关联矩阵
用边和定点表示的矩阵
10.3.5 图的同构
10.3.6 判断两个简单图是否同构
10.4 连通性
10.4.2 通路
通路(路径)是边的序列,它从一个顶点开始沿着边行径相邻顶点
- 路线:没有重复边的路径,使用路线这一术语时,通常使用通路表示没有重复顶点的路线。
10.4.3 无向图的连通性
定理1:在连通无向图的每一对不同顶点之间都存在简单通路。
连通分支:图的连通分支是图的一个极大连通子图,不连通的图G具有2个或以上的不相交的连通子图,并且G是这些连通子图的并。
10.4.4 图是如何连通的
如果删除一个点及其关联的边,就产生比原图具有更多连通分支的子图,把这样的顶点称为割点(关节点),同理如果删除一条边,则称为割边或桥。
不含割点的连通图称为不可分割图,它比有割点的连通图具有更好的连通性。
点连通度:非完全图的点割集中最小的定点数,记作k(G)。
k(G)越大,则图的连通性越好。
边连通度:定义类似于点连通度。记作$\lambda()$
这里存在一个不等式$k(G)\leq\lambda(G)\leqmin deg(v)$
10.4.5 有向图的连通性
定义4:若对于有向图中任意顶点a和b,都有从a到b和从b到a的通路,则该图是强连通的。
定义5:若在有向图的基本无向图中,任意两个顶点之间都有通路,则该有向图是弱连通的。
有向图的强连通分支:极大强连通子图可称为G的强连通分支或强分支。
10.4.6 通路与同构
10.4.7 计算顶点之间的通路数
10.5 欧拉通路与哈密顿通路
- 定义1:图G的欧拉回路是包含G的每一条边的简单贿赂。图G的欧拉通路是包含G的每一条边的简单通路。
欧拉回路和欧拉通路的充要条件:
定理1:含有至少2个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都是偶数。
定理2:连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有2个度为奇数的点。
10.5.3 哈密顿通路和哈密顿回路
定理3(狄拉克定理):如果G是由N个顶点的简单图,并且G中每个顶点的度至少为n/2,则G有哈密顿回路。
定理4(欧尔定理):如果G是由n个顶点的简单图,其中$n\geq3$,并且对于G中每一对不相邻的顶点来说都有deg(u)+deg(v)$\geq$n,则G有哈密顿回路。
10.6 最短通路问题
10.6.2 最短通路算法
定理1:狄克斯特拉算法求出连通无向加权图两个顶点之间最短通路的长度
定理2:迪克斯特拉算法使用O(n^2)次运算求出含有n个顶点的连通简单无向加权图中两个顶点之间最短通路的长度。
10.7 平面图
10.7.1 引言
- 定义1:若可以在平面中画出一个图而边没有任何交叉(其中边的交叉表示边的直线或弧线在他们的公共端点以外的地方相交),则这个图是平面图。这种画法称为这个图的平面表示。
10.7.2 欧拉公式
- 定理1:欧拉公式,设G是带e条边和v个顶点的连通平面简单图。设e是G的平面图表示中的面数。则r = e-v+2
- 推论3:若联通平面简单图有e条边和b个顶点,v>=3并且没有长度为3的回路,则e<=2v-4
10.7.3 库拉图斯基定理
- 定理2:一个图是非平民图当且仅当它包含一个同胚于K3.3或K5的子图。
10.8 图着色
10.8.1 引言
定义1:简单图的着色是对改图的每个顶点都指定一种颜色,使得没有两个相邻的顶点颜色相同。
定义2:图的着色数是着色这个图需要的最少颜色数,记作$\chi(G)$,希腊字母chi。
四色定理:平面图的着色数不超过4
关键术语和结论(带英文)
未完待续
更新日期: 2021/12/14