数学图论知识点笔记总结

定义9.2.3 设图G = lt;V, Egt;。设u, v∈V(u, v可能相邻，也可能不相邻)，用G∪(u, v)表示在u, v之间加一条边(u, v)，称为加新边。

定义9.2.3 设图G = lt;V, Egt;。设e = (u, v)∈E，用G\e表示从G中删除e，将e的两个端点u, v用一个新的结点w代替，使w作为除e外以u或v为端点的一切边的端点，称为边e的收缩。

定义9. 3 设图G = lt;V, Egt;。设e∈E，用G-e表示从G中去掉边e得到的图，称为删除边e。又设Eapos;⊆E，用G-E表示从G中删除Eapos;中所有边得到的图，称为删除E。

定义9.2.2 设图G = lt;V, Egt;，其中V = {v1, v2, …, vn}，并假定结点已经有了从v1到vn的次序，则n阶方阵AG = (aij)n×n称为G的邻接矩阵(Adjacency Matrix)，其中

（1）在G中选取最小权边e1，置i = 1。（2）当i = n-1时，结束，否则转(3)。（3）设已选取的边为e1, e2, …, ei，在G中选取不同于e1, e2, …, ei的边ei+1，使{e1, e2, …, ei, ei+1}中无回路且ei+1是满足此条件的最小权边。（4）置i = i+1，转(2)。

（1）在G中任意选取一个结点v1，置VT = {v1}, ET = Φ，k = 1；（2）在V-VT中选取与某个vi∈VT邻接的结点vj，使得边(vi, vj)的权最小，置VT = VT∪{vj}, ET = ET∪{(vi, vj)}，k = k+1；（3）重复步骤(2)，直到k = |V|。

Tremaux探索迷宫就是一种DFS；只不过：用一个堆栈代替线绳记录走过来的路径；用一个顶点数组代替交叉点的灯，以记住访问过的顶点。

对不连通图，一次调用DFS算法只可以遍历一个连通分量。

有一个数组用于标志已访问与否，还用一个工作队列。

最小生成树（Minimum Spanning Tree，简记为MST）

克鲁斯卡尔算法的基本工作有3点：1、选择一条权重最小的边；2、判定一条边的两端是否属于同一棵树；3、合并两棵树。

重复执行迪杰斯特拉(Dijkstra)算法|V|次。这样，便可求得每一对顶点的最短路径。总的执行时间为O(|V|3)。

弗洛伊德（Floyd）提出的另一个算法。这个算法的时间复杂度也是O(|V|3)，但形式上非常简洁优雅，而且对于比较稠密的图，实际运行效率更快。

拓扑排序是指有向无环图中各顶点构成的有序序列。该序列满足如下条件：如果图中一顶点vi到另一顶点vj存在一条路径，那么vj在此图的拓扑排序序列中位于vi之后。

 Delayv,w = Latest[w] - Earlieat[v] - Cv,w Delayv,w = 0 活动就是关键活动,

由关键活动构成的最长路径叫关键路径.

你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。故又称为“小世界现象 (small world phenomenon）”。

定义11.2.1 设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。规定：平凡图为欧拉图。以上定义既适合无向图，又适合有向图。

欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路；欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路。如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。

定理11.2.1 无向图G =lt;V, Egt;具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。

推论11.2.1 无向图G = lt;V, Egt;具有欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。定理11.2.2 有向图G具有欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。推论11.2.2 有向图G具有欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。

对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对任意给定的有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。 利用这项准则，很容易判断出哥尼斯堡七桥问题是无解的，因为它所对应的图中所有4个结点的度数均为奇数；也很容易得到例11.2.1的结论。

推论11.3.2 设G = lt;V, Egt;是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, v∈V，均有deg(u) + deg(v) ≥ n则G中存在哈密顿回路。推论11.3.3 设G = lt;V, Egt;是具有n个结点的简单无向图，n ≥ 3。如果对任意v∈V，均有deg(v) ≥ n/2，则G是哈密顿图。

定理11.3.2及其推论给出的是哈密顿图的充分条件，而不是必要条件 在六边形中，任两个不相邻的结点的度数之和都是4＜6，但六边形是哈密顿图。

动态

效率

当线性表中数据元素是按大小排列存放时，可以改进顺序查找算法，以得到更高效率的新算法----二分法 (折半查找)。

 二分查找算法具有对数的时间复杂度O(logN)

 树（Tree）是n（n≥0）个结点构成的有限集合。当n=0时，称为空树；

一棵二叉树T是一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。可见左子树和右子树还是二叉树。

性质：

“斜二叉树(Skewed Binary Tree)”（也称为退化二叉树）

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1 ≤ i ≤ n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为“完全二叉树(Complete Binary Tree)”。

2、结点（序号为 i ）的左孩子结点的序号是 2i， （若2 i lt;= n，否则没有左孩子）;

3、结点（序号为 i ）的右孩子结点的序号是 2i+1， （若2 i +1lt;= n，否则没有右孩子）;

假设有n个权值{w1 ,w2 , …… , wn} ，构造有n个叶子的二叉树，每个叶子的权值是n个权值之一。这样的二叉树也许可以构造多个，其中必有一个（或几个）是带权路径长度WPL最小的。达到WPL最小的二叉树就称为最优二叉树或哈夫曼树。

特点