#离散数学复习
第一章
第二章
第三章
第四章
第五章 图论
5.1 图的概念与描述
基本概念：
三元组：
- V(G) ：点集 ,
- E(G) ：边集
- M(G) ：点与边的对应关系。三元组表示整个图
邻接矩阵：
其与关系矩阵在上形式一样，但邻接矩阵可以有权值
关联矩阵：
仅需关注对应数值关系即可
度：
其包括出度与入度
5.2 度的连通性
考点：通过Warshall算法判断连通性，通过图的邻接矩阵的幂次方来求连通路数目
判断是否为连通图
求连通路的数目
只需计算$\sum_{i=1}^{n} A^i$的结果矩阵
5.3 欧拉图
七桥问题
概念及定理一览：
中国邮路问题
邮递员问题就是：邮递员从邮局出发，走完所有街道，最后回到邮局，并且让重复走的路尽量短。
判断过程找含重边的回路即可
例题
eg 1
eg 2
5.4 哈密顿图
1. 哈密顿路与哈密顿回路
哈密顿问题研究的是“经过所有顶点”的路线。
- 哈密顿路：经过图中每个顶点一次且仅一次的路。
- 哈密顿回路：从某个顶点出发，经过每个顶点一次且仅一次，最后回到出发点。
- 哈密顿图：存在哈密顿回路的图。
注意区分：
欧拉问题：要求经过所有边。
哈密顿问题：要求经过所有点。
简单图：没有自环；任意两个顶点之间至多只有一条边。
对于有向图，如果 vi → vj 有边，同时 vj → vi 也有边，这是两条方向不同的边。但是也只有一条边。
2. 一个比较
| 类型 | 关注对象 | 要求 |
|---|---|---|
| 欧拉路 | 边 | 经过每条边一次 |
| 欧拉回路 | 边 | 经过每条边一次并回到起点 |
| 哈密顿路 | 点 | 经过每个顶点一次 |
| 哈密顿回路 | 点 | 经过每个顶点一次并回到起点 |
3. 一些定理
定理中的充分与必要关系尤其重要。
4. 例题
5.4附 旅行商问题（TSP）
最近插入法 求 TSP 的近似解，不是穷举所有哈密顿回路。
核心思路是：
- 先从起点 1 开始，集合 U={1}。
- 每次找一个 离当前集合 U 最近、但还没加入的点。
- 把这个新点插入当前回路中，使插入后回路长度增加最少。
- 重复直到所有点都加入。 断边原则：把新点插入每一条候选边，计算增加量，选增加最少的那条边断开。
例题
5.5 平面图与四色猜想
基本概念
平面图：
该图每条边除首尾两点再无交点（边可经过拉长或缩短）
极大平面图
见图
几个定理
见图
Welch Powell 算法
概念
核心目标是：
- 每次尽量让一种颜色覆盖尽可能多的互不相邻结点
- 从度数大的点开始，优先处理“限制更多”的结点
注意：
-
该算法通常能较快得到一个可行着色方案
-
但未必总是得到“最少颜色数”
例题
5.6 树与生成树
基本概念
- 如果连通图中没有任何回路，则称为一棵树
- 一棵树包括某个图的所有节点，则称为该图的生成树或支撑树
- 树的边数等于点数减一
- 赋权图中所有生成树中，边权和最小的生成树称为最小生成树
Kruskal算法及例题
Prim算法及例题
Huffman 树
两个原则：
左小右大 ：
组合优先 ：即相等时，组合出来的优先
5.7 最短路径
采用Dijkstra算法
5.8 网络流图
看书和看ppt，真写不来这个
第六章 组合数学
看书，懒得写了
