刘汝佳黑书学习指导

《刘汝佳黑书学习指导》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法艺术与信息学竞赛》教学幻灯片算法图论学习指导声明本系列教学幻灯片属于刘汝佳、黄亮著《算法艺术与信息学竞赛》配套幻灯片本幻灯片可从本书blog上免费下载，即使您并未购买本书.若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用有任何意见，欢迎在blog上评论Blog地址：http://artofalgo.blogchina.com内容介绍一、基本概念二、图搜索(重点)三、DAG四、连通性问题(重点,中难)五、道路和回路六、最短路(重点,中难)七、最小生成树(重点)八、最大流问题(重点,

2、偏难)九、最小费用流(重点,偏难)十、匹配(重点,偏难)十一、图论难解问题(偏难)一、基本概念图的基本概念(1)图、简单图、图形表示结点、弧、邻接、关联、度数子图、导出子图平面图、欧几里得图、三角形不等式同构路径、圈、不相交路、边不相交路连通、连通分量★树和森林完全图和补图、团★稀疏图和稠密图图的基本概念(2)★二分图(二部图)△相交图、区间图有向图、DAG带权图、网络△图的ADT,图IO的ADT※邻接矩阵、邻接表和前向星表示图例△:了解即可★:需要深入理解※:需要非常熟悉,能写出程序二、图搜索图搜索宽度优先遍历:全部内容应熟练掌

3、握.深度优先遍历基本的DFS-VISIT:颜色和时间戳嵌套区间定理:推导+直观理解(重点)白色路径定理:直观理解(可选,较难)边分类规则:直观理解边分类算法:程序实现和复杂度分析(重点)无向图只有T边和B边:证明和分类算法使用pre和post数组的DFS实现(重点)三、DAG的算法DAG的算法DAG的充要条件:无B边(证明和直观理解)拓扑排序(熟练掌握)基于DFS的算法基于队列的算法关键路径PT图PERT图本讲内容比较简单,建议全部理解四、连通性问题连通性问题提醒:本讲比较难,但算法非常巧妙SCC划分G和GT的SCC相同:证明和直

4、观理解SCC构成DAG:证明和直观理解Kosaraju算法:按f递减顺序DFS转置图(重点)Tarjan/Gabow:用栈保留结点,延迟输出(难)Tarjan算法:用LOW测试输出条件Gabow算法:用栈保留当前路径连通性问题割顶和桥的判定(重点)无向图的LOW函数割顶条件和割顶判定算法桥条件和桥判定算法BCC划分五、道路和回路道路和回路欧拉回路和道路充要条件套圈算法及其简洁实现中国邮路问题主算法:倍边+欧拉回路权值:SSSP预处理配对:二分图最佳匹配预处理六、最短路最短路SSSP问题一般SSSP算法,包括正确性证明(重难点)di

5、jkstra算法的堆实现(重点)Bellman-ford算法和差分约束系统(重点)Gabow的变尺度算法(了解即可)APSP问题矩阵乘法算法floyd-warshall算法,包括路径输出(重点)Johnson算法,包括正确性证明(重点)七、最小生成树最小生成树一般MST算法:正确性证明经典MST算法Boruvka算法Prim算法Kruskal算法其他问题(了解)MST唯一性判定瓶颈生成树八、最大流问题最大流问题基本概念流网络定义、流的三个性质结点集的流记号、运算和凸性相反方向的流取消操作、循环流、流分解定理Ford-Fulkers

6、on方法残量网络、增广路、切割与流的关系最大流的两个等价条件和证明基本的Ford-Fulkerson方法和复杂度分析Edmond-Karp算法(重点)关于d值的单调性引理、关键弧引理及其证明(难点)Edmond-Karp算法的时间复杂度及其证明最大流问题预流推进算法预流的定义,push和relabel过程高度函数中st的值和性质:起点不能太高(重点)push、relabel和初始化的算法步骤正确性证明引理1:两个操作至少一个能执行引理2、3:h函数维持性质且每次relabel至少增加1引理4:残量网络中s到t始终不存在通路时间复杂

7、度分析(难)discharge操作和relabel-to-front算法(难)最高标号预流推进算法最大流问题应用举例多源多汇问题顶点容量有环转无环无向变有向可行流二分图最大匹配九、最小费用流问题最小费用流问题最小费用流问题分布网络、残量网络负圈定理及其证明消圈算法基本的消圈算法最小费用路算法复杂度分析最小费用流问题网络单纯形法可行树可行树构造法有效顶点势及其计算合格弧定理可行树的维护