《noip知识点串讲 图论(一)》由会员分享，可在线阅读，更多相关《noip知识点串讲 图论(一)（86页珍藏版）》请在金锄头文库上搜索。
1、NOIP知识点串讲 图论（一）,Colin,NOIP中涉及的数学知识,图论 组合数学 ,道路与回路,基本概念 图的代数表示 道路矩阵与Warshall算法 BFS、DFS 欧拉回路 哈密顿回路 旅行商问题 最短路 差分约束 关键路径,树,树的等价定义 DFS序 最近公共祖先 哈夫曼树 最小生成树 生成树计数 prufer序列,NOIP知识点串讲 图论（一）,一些概念,一些概念,道路（链）、回路 有向道路（回路） 无向道路（回路） 简单道路（回路） 初级道路（回路） 简单图 连通图 连通支 二分图 DAG（有向无环图）,二分图,DAG（有向无环图）,可以在线性复杂度内拓扑排序 通常可以按照拓扑序
2、进行DP,NOIP知识点串讲 图论（一）,图的代数表示,图的代数表示,邻接矩阵 权矩阵 关联矩阵 边列表 邻接表,NOIP知识点串讲 图论（一）,连通性判断,例1.,如何计算点对之间的路径条数,例1.解,例2.,只想知道点对之间是否连通？,Warshall算法,Warshall算法,Warshall算法,BFS & DFS,常用的对图进行遍历的方法 广度（宽度）优先搜索算法 深度优先搜索算法 复杂度均为O(m) 区别在于访问顶点的顺序不同 常用部分分算法,BFS,1,2,6,3,5,4,DFS,1,2,6,3,5,4,NOIP知识点串讲 图论（一）,欧拉回路,欧拉回路与道路,七桥问题 一笔画问
3、题 欧拉回路（道路）定义,欧拉回路的判定,一些推论,NOIP知识点串讲 图论（一）,哈密顿回路,哈密顿回路与道路,与欧拉回路（道路）问题非常类似的是哈密顿回路（道路）问题。该问题起源于英国数学家威廉哈密顿于1857 年提出的一个关于正十二面体的有数学游戏：他把12 面体的20 个顶点比作世界上的20 个城市，30 条棱比作表示这些城市之间的交通路线。哈密顿提出能否周游世界，即从某个城市出发，经过每个城市一次且一次最后返回出发地。,哈密顿回路（道路）,H回路存在的一个必要条件,二分图存在H回路（道路）的一个必要条件,H道路存在的一个充分条件,H道路存在的一个充分条件,H道路存在的一个充分条件,一
4、个推论,H回路存在的一个充分条件,H回路存在的充要条件,闭合图与哈密顿回路,哈密顿回路(道路),NOIP知识点串讲 图论（一）,旅行商问题,旅行商问题,分支与界法,便宜算法,便宜算法,NOIP知识点串讲 图论（一）,最短路,最短路,按照实际问题的模型可分为三类： (1) 某两结点之间的最短路径 (2) 某结点到其他各结点的最短路径 (3) 任意两结点之间的最短路径 模型(2)如果能够解决，模型(1)和(3)自然可以解决,最短路,依据边权值的特点，有以下几种情况： (1) 均大于零（正权图） (2) 均等于1 (3) 为任意实数,最短路,例3.,BFS,边权为1 距离源点近的点先被访问 用近的点
5、去更新远的点,例4.,Dijkstra算法,Dijkstra算法思想是由近及远扩展 得到某点的最短路径后不会再变 但有负权边时（不一定存在负长回路），Dijkstra算法可能会失效 Dijkstra算法只适用于正权图,Dijkstra算法,Dijkstra算法,Dijkstra算法,Dijkstra算法,Ford算法,Ford算法,SPFA算法,Ford 算法的迭代过程中有许多边的枚举是无意义的 只有在前一次迭代时被更新过的点才有更新其他点的可能 对Ford算法进行优化，得到SPFA算法,SPFA算法,对于特殊的稠密图,若为正权图 进行Dijkstra算法 若为负权图 可先删去负边，进行Dij
6、kstra算法 再加上负边，进行SPFA算法,最短路,最长路？小于等于变大于等于，负环变正环 最短路问题难点不在于算法本身，而是在于建图,例5.,例5.解,NOIP知识点串讲 图论（一）,差分约束,差分约束,解的特点,有无数组解 已知一组解，每个变量加上同一个数也是一组可行解 因此，我们一般是求最小的非负解,观察不等式,解法,解法,例6.,例6.解法,例7.,例7.解法,例8,例8.解,例8.解,例9.,例9.解,差分约束,差分约束系统的概念其实十分简单，解法也只是最短路算法而已 重点在于建模，以及对于模型性质的深入分析 拿不准的时候可以猜性质然后暴力对拍检验,NOIP知识点串讲 图论（一）,关键路径,关键路径,在规划一个工程的时候，常有若干工序需要考虑 每道工序有各自的预期完成时间 工序之间也会有依赖关系 想知道完成工程的最少时间 每项工序的最早开始时间、最晚开始时间,PT图,用点表示工序 边表示依赖关系 边权表示工序的完成时间,PT图,一定是DAG 可以进行拓扑排序 完成工程的最少时间：最长路 每项工序的最早开始时间：到每个点的最长路 最晚开始时间：源点到终点的最长路减去到终点的最长路 复杂度：线性,参考资料,刘明华、朱佳豪、沈子翔，图论改编教材 胡泽聪，差分约束,ThanKS for your listening,
