ACM图论算法选讲.pdfVIP

ACM 图论算法选讲 张子臻 香港城市大学管理科学系博士研究生 2011年8月10日 欢迎大家联系我，我的QQ:，Email: zzzhang@cityu.edu.hk 大纲  最小生成树（略）  最短路（略）  传递闭包  最大流  最小费用最大流  二部图最大匹配  最大权匹配  与二部图相关的一些定理  差分约束系统 (大多材料来源于网上) 如何学习图论  由浅入深的学习图论的相关知识点。  多练经典常用的算法，对每个算法打上 十到二十遍，同时自己精简代码，偶尔 做做简单题培养感觉。  看到问题时首先建立相关的图论模型， 然后用相关的算法去求解。  要结合其他知识来学习图论，懂得变通。  开始可以用模板，但要学习算法的原理， 再慢慢抛开模板。 传递闭包  传递闭包主要用于判断图的连通性和图 中满足条件的连通分支。  输入一个图G=(V,E) ，G可以是有向图也 可以是无向图。  输出该图中哪些顶点对之间有路。 传递闭包  可以采用宽度优先或深度优先遍历来解 决。从任意一个顶点出发，进行一次遍 历，就可以求出此顶点和其它各个顶点 的连通状况。所以只要把每个顶点作为 出发点都进行一次遍历，就能知道任意 两个顶点之间是否有路存在。一次遍历 的时间复杂度为O(e)，要穷举每个顶点， 所以总的时间复杂度为O(n*e)。 传递闭包  Warshall算法：Floyd算法思想求图中每 一对顶点的最短路。  link[i][j]与longlink[i][j]分别表示图G的边 (i,j)是否有direct路径和indirect路径。  每次利用顶点k来更新(i,j)之间的关系 传递闭包  算法框架 longlink的初值赋为link； for k:=1 to n do for i:=1 to n do for j:=1 to n do longlink[i,j]= longlink[i,j] or (longlink[i,k] and longlink[k,j]); 3  时间复杂度O(n ) 传递闭包  Q ：求任意两点(i,j) 间长度为L的路径有多 少条  A ：longlink (L) = Σ longlink (1) * longlink (L- 1) ij k ik kj = … = Σ longlink (s) * longlink (L-s) = … = k ik kj Σ longlink (L- 1) * longlink ( 1) k ik kj  Q ：求任意两点(i,j) 间长度不超过L的路径 有多少条  A ：Σl=1..L longlinkij(l)  定义 ◦ 矩阵M ：图G的邻接矩阵 ◦ 矩阵M* ：图G的连通矩阵 传递闭包 2  M =M*M  M2 ＝∑ M ×M 表示从节点i到节点j ij k=1..n ik kj 有一条长度为2的路径。  如果认为每个节点与其本身邻接，即 M =1 ，M2 表示从节点i到节点j有一条 ii ij 长度不超过2的路径。  为计算传递闭包矩阵只须计算M矩阵的 n一1次幂Mn- 1即可，其中的矩阵乘法、 加法分别是逻辑乘(AND)，逻辑加(OR) 。 传递闭包 3  矩阵平方运算的时间复杂度为0(n ) ，从