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