数学图论知识点笔记总结

（1）考虑一张航线地图，图中用点表示城市，当两个城市间有直达航班时，就用一条线将相应的点连接起来。

图的操作

图的定义

Kruskal算法

Prim算法

树的定义

常有的方法是先序创建和层序创建两种。

二叉树的创建

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

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

深度优先搜索（Depth First Search，简称DFS

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

广度优先搜索（Breadth First Search，简称BFS ）

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

 生成树（Spanning Tree）

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

最小生成树

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

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

每一对顶点之间的最短路径（ All-Pairs Shortest Path）问题：

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

有向无环图”（Directed Acyclic Graph，简称DAG）

关于AOE 网图意义

子主题

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

几个重要值的意义与计算方法：

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

六度空间理论（Six Degrees of Separation）

树的应用

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

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

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

欧拉图

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

哈密顿图

特俗图

所谓动态查找，是指集合中的记录是动态变化的，即记录可能要发生插入和删除操作。

动态

主要用“平均查找长度”（ASL，Average Search Length）来衡量。

效率

查找

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

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

二分查找

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

树

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

一个二叉树第 i 层的最大结点数为：2 i-1，i ≥1

对任何非空的二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 +1。

性质：

二叉树

“斜二叉树(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，否则没有右孩子）;

二叉树的存储结构

平衡二叉树：对于二叉树中任一结点T，其“平衡因子（Balance Factor，简称BF）”定义为BF(T) = hL-hR，其中hL和hR分别为T的左、右子树的高度。

哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树；

也就是说，与一棵哈夫曼树同构的二叉树都是哈夫曼树；

特点

哈夫曼树

树和二叉树

数学图论知识点笔记总结