图论初步 柏钧文.

Presentation on theme: "图论初步 柏钧文."— Presentation transcript:

1 图论初步 柏钧文

2 图论简介 图论是数学的一个分支 以图为研究对象 点代表事物 边代表关系

3 图论起源

4 七桥问题 哥尼斯堡的七座桥 欧拉（1736） 一笔画

5 图论基本术语 图 G=(V,E) V代表点集 E代表边集

6 图论基本术语 有向图和无向图 无向图 e={a,b} 有向图 e=<a,b>={{a,b},{b,a}}

7 图论基本术语 度（入度、出度） 路径 生成树 割

8 度 入度通常指有向图中某点作为图中边的终点的次数之和 出度通常指有向图中某点作为图中边的起点的次数之和 无向图是有向图的特例 无向图的度

9 度的一些定理 定理1：无向图中所有顶点的度之和等于边数的2倍，有向图中入度和等于出度和 定理2：任意一个无向图一定有偶数个奇点
定理3：无论无向图还是有向图 E=(d[v1]+...+d[vn])/2

10 图的分类 G=(V,E) 简单图 完全图 二分图 平面图

11 图的表示 邻接表

12 图的表示 邻接矩阵

13 生成树 通过删掉图中的边来得到一棵树 树：n个节点，n-1条边 删去m-(n-1)条边 最小生成树

14 kruskal 按边权从小到大排序 选择当前最小权值的边，将其所连接的两个点所在的并查集合并 知道合并了n-1条边

15

16 Prim 顶点集合S初始时仅一个元素x 每次选择权值最小的边<u,v>，u在S中，v不在S中 添加v进入S

17 Prim

18 Prim算法证明 简单思路： Prim算法得到G0
假设存在Gmin，s.t. cost(Gmin)<cost(G0)，则存在一条Gmin中的边(u,v)不在G0中 添加(u,v)进入G0形成环，(u,v)应不为环中最大边（否则存在更优解） 则与prim算法每次收录最小权值边矛盾 假设不成立

19 衍生问题 次小生成树 最小生成树个数 ……

20 次小生成树 将不在最小生成树上的边依次添加进入 形成一个环，找次大边， 得到次大边和最大边的差 找出最小的差值

21 次小生成树

22 最小生成树计数 简单思路： 引理：最小生成树中同一权值的边个数相同 状压枚举所有这种权值的边的选法，记录下合法方案数
各阶段的数目乘积即为答案

23 最短路 最短路问题一般求解从一点到另一点的最短距离 实际问题中经常要用到 根据不同的需求得到不同的算法

24 Floyd 枚举k，f[i,j]=min(f[i,k]+f[k,j],f[i,j]) 计算所有点对间的距离 时间复杂度O（n^3）
动规的思想

25 Dijkstra 单源最短路径 从起始节点出发，每次寻找距离最小的但仍未确定的点作为更新节点x x的最短确定 更新所有x的关联节点

26 Dijkstra+heap 优化复杂度至(m+n)logn 利用堆来优化dijkstra算法中找最小距离节点的需求 需维护堆
可以利用priority_queue这个STL模板

27 Bellman-Ford 单源最短路 每次遍历所有边(u,v)，更新dist[v]=min(dist[v],dist[u]+cost(u,v)) 如果一轮中没有任何更新，则算法结束，否则再来一次，最多n-1次

28 Bellman-Ford 时间复杂度O(nm) 优点：可以判断负权边（dijkstra做不到） 缺点：复杂度略高

29

30 SPFA Shortest Path Faster Algorithm 由西南交大段凡丁提出 期望时间复杂度O（ke）（k一般小于等于4）
Bellman-ford的改进版本

31

32 Bellman-Ford里面有许多操作是冗余的
每次更新所有节点没有利用好这个算法的性质 思路：用队列优化，每次只更新候选节点

33 SPFA 队列里面初始时有一个元素x 每次从队列里弹出队首元素h，更新其所有关联节点，如果被更新关联节点不在队列中，加入队列（不论之前它有没有加入过队列） 队列空的时候算法终止

34 SPFA 定理 只要最短路存在，SPFA算法就能求出结果（换言之，终止）
证明思路：每个节点经过每次松弛操作都会有dist[v]减小，dist[v]具有最小值，不会无限小下去，算法一定能终止。

35 SPFA 利用SPFA可以判断有无负环（但不能判断负权边） 如果某个点进入队列的次数超过N次，则存在负环

36 最短路 如果一条路径的长度定义为路径上边权的乘积？ 最短路径的个数？ ……

37 如果一条路径的长度定义为路径上边权的乘积？
每条边权值改为log(权值)，依然用和来计算

38 最短路径的个数？ 增加记录一项到这个节点最短路的条数，转移的时候更新这个信息 类似动态规划

39 欧拉回路 欧拉路：遍历所有边恰好一次的路径（七桥问题） 欧拉路径：首尾相同的欧拉路
定理1 一个无向图存在欧拉回路，当且仅当所有顶点度数为偶数 定理2 一个有向图存在欧拉回路，所有顶点的入度等于出度且连通

40 欧拉回路的求解 回溯 思路：找到一个圈就消去，直到消没了 Dfs求解

41 汉密尔顿回路 经过每个节点恰好一次的路径 NPC问题

42 汉密尔顿回路 虽然是NPC问题，但并不代表我们不能进一步思考这个问题 缩小规模

43 汉密尔顿回路 状态压缩DP f[011][2] 表示经过了2,3节点，并停在了2，是否合法 空间复杂度：O(2^n*n)
时间复杂度：O(2^n*n*n)

44 特殊图上的一些问题 二分图 完全图 树

45 二分图

46

47 男生占便宜呢？还是女生占便宜？ 女生撒谎的话，会不会有更优解？

48 ＴＨＡＮＫ　ＹＯＵ！