《高级算法设计》课件 第2章 高级图算法.pptx

高级算法设计与分析高级图算法林海lin.hai@whu.edu.cnB站：foretmer

主要内容最大流最小割图的中心性算法社群发现算法

流网络找到一个从s出发，到t的流量最大的流，这就是最大流问题

网络的流网络的流需要满足的两个条件：

网络的流如何找到最大流从流量为0开始，逐步增加流量，直到达到最大流量为止从s出发，找到一条到t的可行路径，并将流增加到这个路径能够支持的最大流量在剩余的流网络（残存网络）中再找一条可行的路径，增加相应的流重复以上步骤

网络的流原始流网络找到一条路径残存网络？

残存网络

网络的流残存网络新的路径：新的流网络

网络的流残存网络此时已无法在此残存网络中再找到一条从s到t的路径，前面的流为最大流

Ford-Fulkerson算法

Ford-Fulkerson算法Ford-Fulkerson算法的两个问题当在残存网络中无法再找出一条从s到t的路径时，那么得到的流一定是最大流吗？最大流最小割定理在残存网络中如何找到一条从s到t的路径？Edmonds-Karp算法

最大流最小割定理

最大流最小割定理

最大流最小割定理

最大流最小割定理

最大流最小割定理设f是最大流，其所对应的残存网络Gf还存在一条从s到t的路径p，在残存网络Gf上可以找到一个流f′

最大流最小割定理

最大流最小割定理结论1:也就是由最大流最小割陈述2得出的(S,T)割上，(S,T)的流量(从S到T的流量)等于(S,T)的容量

最大流最小割定理(S′,T′)是任意s-t割,根据能量守恒来证明，即从源节点s来的流f等于从集合S流到T的流结论2:是s?t流f等于任意(S′,T′)割

最大流最小割定理(S′,T′)是任意s-t割结论3:f小于等于任意(S′,T′)割的容量

最大流最小割定理由结论1和结论2，可知s?t流f等于(S,T)割的容量，即f=C(S,T)结合结论3，可知(S,T)割的容量小于等于任意割，即C(S,T)≤C(S′,T′)，即C(S,T)是最小割

最大流最小割定理

Edmonds-Karp算法在残存网络中如何找到一条从s到t的路径?图的深度优先遍历方法？

Edmonds-Karp算法最短路径算法Dijsktra算法(复杂度O(mlogn))广度优先有哪些信誉好的足球投注网站（O(m)）短路径为vs→v2→vt或者vs→v3→vt，所以通过两次增广路径即可找到网络的最大流

Edmonds-Karp算法：复杂度基于最短路径算法证明：设在残存网络G中找到流f，形成新的残存网络G’。从G到G’，增加了指向上一层级的边，并删除了指向下一层级的关键边增加的边并不会减少从s到其他节点的距离，但减少的边有可能会增加s到其他节点的距离，所以引理得证

Edmonds-Karp算法：复杂度基于最短路径算法

Edmonds-Karp算法：复杂度边ei→j再次成为关键边时，源节点到vi的距离至少增加了2跳

Edmonds-Karp算法：复杂度可以得出边ei→j最多(n?2)/2次成为关键边总的关键边的次数为O(m?(n?2)/2)=O(mn)

Edmonds-Karp算法最大容量路径也为vs→v2→vt或者vs→v3→vt，所以也通过两次增广路径即可找到网络的最大流最大容量路径算法Dijsktra算法

Edmonds-Karp算法Dijkstra算法，对路径的边求最小容量，并最大化之，

Edmonds-Karp算法

Edmonds-Karp算法流量分解证明

Edmonds-Karp算法流量分解证明由流量守恒，可得：在每次容量更新中，路径中最小容量的边(至少一条)的容量会被置0，因图G边的条数是m

Edmonds-Karp算法流量分解定理说明了最大流fopt可以被分解为最多m个路径流{f1,f2,···,fm}，在这些路径流中，必然存在一个流fk≥fopt/m,1≤k≤m，而此流所在路径上所有边的容量必然≥fopt/m。引理得证。

Edmonds-Karp算法

Edmonds-Karp算法如果原始图G的边数为m，则在任意的残存图Gt中，其边的条数不会超过2m，所以对任意残存图Gt，剩余最大流为因为容量都为整型

主要内容最大流最小割图的中心性算法社群发现算法

图的中心性算法度中心性(DegreeCentrality):一个点与其他点直接连接的程度紧密中心性(ClosenessCentrality