问题求解3复习提纲

本文章只是个提纲,含有大量的资料链接。

3-1 动态规划

  • Link: lem的整理
  • 动态规划的4步骤
    • 找到最优解的结构
    • 递归定义最优解
    • 计算最优解的值
    • 构造最优解
  • 递归与记忆化搜索
  • 最优子结构与证明
    • 问题包含一个选择
    • 当前问题的最优解依赖于子问题的最优解
    • 子问题必须相互独立
  • 自下而上/自上而下
  • OJ:设计动态规划

3-2 贪心

  • Link: lem的整理
  • 最优子结构?
    • 证明最优解:替换法
  • 贪心性质?
    • 证明选择当前最优的步骤后只有一个子问题
    • 证明选择当前最优的步骤是对的(替换,证明这个步骤总是在某一个最优解里)
  • Huffman编码/树?
  • OJ:设计贪心算法

3-3 图的基本概念

  • 直径:最远的距离
  • $G+H$:点集合为$G \cup U$,把$G$和$U$的所有点连起来。
  • $G \times H$:把$G$里的所有点替换成$H$。
  • 超立方体:$Q_{n} = Q_{n-1} \times K_2$。注意超立方体的色数是2。
  • 度数$0 \leqslant \delta(G) \leqslant \deg v \leqslant \Delta(G) \leqslant n - 1$。
  • 图论第一定理:$\sum \deg v = 2m$。推论:每个图都有偶数个奇点。
  • 若对于任意两个不相连的定点都有$\deg u + \deg v \geqslant n-1$,则$G$是联通的,且直径不超过2。
  • 若$\delta(G) \geqslant \dfrac{n-1}{2}$,则$G$是联通的。
  • 3正则图被称为立方图(cubic graph)。
  • 若把图$G$的所有顶点的度排成一个序列$s$,称$s$是$G$的度序列。如果$s$是某个图的度序列,称$s$是可图的。$s: d_1, \dots, d_n$是可图的当且仅当$s_1: d_2 - 1, d_3 - 1, \dots, d_{d_1 + 1} - 1, d_{d_1+2}, \dots, d_n$是可图的(删除首项,对其后相同的个数的项每个项减一,此步骤是等价的,可以重复操作)。

3-4 动态等价关系

  • Link: lem的整理
  • 并查集
    • Make-Set
    • Find-Set
    • Union
  • OJ:union find set
  • 时间复杂度
  • 路径压缩

3-5 树

  • Link: lem的整理
  • 割边?
  • 树的相关定理
    • $G$是树当且仅当$G$的任意两个顶点都被w唯一的路连接。
    • 每个树至少有两个端点(因为存在一条最长的路)。
    • 每个$n$阶树的边数是$n-1$。
  • OJ:最小生成树
    • Kruskal:不断选择最小的且不构成环的边;
    • Prim:从两个集合中顶点相连的边中选择最小的边。

3-6 图的计算机表示及其遍历

  • 邻接矩阵(稠密)与邻接表(稀疏)
  • 广度优先搜索
  • 深度优先搜索
  • SCC算法
    • Kosaraju
    • Tarjan

3-7 单源最短路

  • Link: lem的整理
  • 最优子结构性质
  • 三角不等式、松弛等性质
  • Bellman-Ford算法(每次对所有边松弛,$O(VE)$),可以检测负环。
  • Dijkstra算法(每次找最小点,对所有点松弛,$O(V^2+E)$)
  • 时间复杂度

3-8 多源最短路

  • Link: lem的整理
  • Floyd算法($k, i, j$,$O(V^3)$)
  • Johnson算法(添加一个假的源点,然后用Bellman-Ford和Dijkstra,$O(VE\lg V)$)
  • 时间复杂度

3-9 图的联通度

  • Link: lem的整理
  • 割点、割边
  • 联通度
    • 点联通度$\kappa$:最小顶点割的基数
    • 边联通度$\lambda$:最小边割的基数
    • $\kappa(G) \leqslant \lambda(G) \leqslant \delta(G)$
    • $\kappa(G) \leqslant \lfloor \dfrac{2m}{n} \rfloor$
  • Menger定理
    • 设$u$和$v$不邻接,则$u-v$分离集(分离$u$和$v$的顶点集合)中顶点的最小个数等于$G$中内部不相交的$u-v$路的最大个数。
  • Whitney定理
    • 一个非平凡图是$k$联通的当且仅当对于$G$的任意两个顶点$u$,$v$,$G$至少有$k$条内部不相交的$u-v$路。
  • 若$G$为$k$联通,则$G$中任意$k$个顶点位于某一个圈上。

3-10 旅行问题

  • Link: lem的整理
  • 欧拉回路与欧拉图
    • 图是欧拉的当且仅当每个顶点的度数都是偶数。
    • 图含有一条欧拉迹当且仅当图含有两个度数为奇数的顶点。
  • OJ:Fleury算法
  • 邮递员问题?
  • 哈密顿回路和哈密顿图
    • 设$k(G)$是$G$的连通分支数。如果$G$是哈密顿图,那么对于任意一个非空子集$S$,$k(G-S) \leqslant |S|$。
    • 如果对于$G (n \geqslant 3)$的每一对不相邻的顶点都有$\deg u + \deg v \geqslant n$,则$G$是哈密顿图。

3-11 匹配与因子分解

  • Link: lem的整理
  • 二分匹配、完美匹配
  • 边独立集和点独立集
  • 完美匹配的条件
    • $|N(X)| \geqslant |X|$
  • Konig定理

3-12 最大流

  • Link: lem的整理
  • 增广路和剩余网络
  • 最小割
  • Hall's Theorem (奶茶题)
  • OJ?

3-13 平面图与着色

  • Link: ksl的整理
  • 平面图的条件
    • 图不包含$K_{3, 3}$或$K_5$。
  • 色数
    • 四色定理:每个平面图的色数最多是4。

3-14 线性代数

不考,滚。

发布于2019-01-06 08:47

学习