图结构

流网络1) 流网络是附加了条件的带权重(容量)的有向图\(G=(V,E)\)，其附加条件与附加定义如下： 源与汇：给定\(G\)的同时需给定源\(s\)与汇\(t\)两个特殊顶点； 边与容量：给定\(G\)的边\((u,v)\)的同时需给定边容量\(c(u,v) > 0\)，并且边集必须满足： i. 不允许反向边(若\((u,v)\in E\)则\((v,u)\notin E\))； ii. \(s\)仅有入边且\(t\)仅有出边； iii. 任意\(v \in V-\{s,t\}\)从\(s\)可达\(v\)且从\(v\)可达\(t\)； iv. 除\(s\)以外每个顶点至少有一条入边故\(|E| \geq |V| – 1\)； 2) 流是函数\(\{ f(u,v) | (u,v)\in E \}\)，流可定义于流网络与残存网络。其附加条件与附加定义如下：… 阅读全文

Ford-Fulkerson方法有流网络\(G=(V,E)\)，其容量\(c\)(默认整数)、流\(f\)、源点\(s\)与汇点\(t\)。\(G\)与\(f\)给定\(G_f\)与\(c_f\)。则有步骤： 1) 遍历\((u,v) \in E\)，初始化流变量\((u,v).f=0\)； 2) 若当前\(G_f\)中存在某个增广路\(p\)则继续迭代，否则停机； 3) 求出增广路容量\(c_f(p)=min\{c_f(u,v)|(u,v) \in p\}\)； 4) 遍历\((u,v) \in p\)，若\((u,v)\in E\)，\((u,v).f+=c_f(p)\)，否则\((v,u).f-=c_f(p)\)，返回(2)； 其之所以不称为算法是因为(2)未有细节，算法与代价无法确定，但可验证其正确性。设每次(2)结束后发现某个\(G_f\)的增广路\(p\)，\(f\)更新为\((f\uparrow… 阅读全文

Goldberg-Tarjan方法 Ford-Fulkerson方法是所有增广路算法的基础，Goldberg-Tarjan方法则是基于预流的算法的基础，定义了“推送”与“重贴高度标签”两个重要操作，故也称“推送-重贴标签”方法。下面给出需要的概念与定义： 1) 预流：流网络上的预流与流非常相似，其唯一区别在于任意顶点的总流入可大于等于总流出。所以流是预流的特例，任意顶点的总流入等于总流出的预流即是合法的流。算法将通过不断的调整预流使其变为合法的最大流； 2) 超额流：给定流网络与预流，任意顶点的超额流为总流入减总流出； 3) 溢出点：除了源与汇，总流入大于总流出的顶点称为溢出点； 4) 残存网络：流网络与其上的一个预流，可以和流一样的给定一个残存网络； 5) 高度函数：给定流网络\(G=(V,E)\)的源与汇为\(s\)与\(t\)，其上有预流为\(f\)，\(f\)给定了预流残存网络\(G_f=(V,E_f)\)。如果非负整数函数\(h\)满足\(h(s)=|V|,h(t)=0\)，且对于\((u,v)\in… 阅读全文

无向图的覆盖集 点覆盖：无向图的点覆盖是顶点集的子集，边集中的每个边都至少有1个端点位于点覆盖； 点覆盖数：点覆盖中的元素数目； 最小点覆盖：元素数目最小的点覆盖； 边覆盖：无向图的边覆盖是边集的子集，顶点集中的每个顶点都为边覆盖中至少1个边的端点； 边覆盖数：边覆盖中的元素数目； 极小边覆盖：若一个边覆盖的任何真子集都不是边覆盖，则称其为极小边覆盖。这里考虑关于无向图\(G=(V,E)\)的两种情况，一种是存在边集\(S_1 = \{ (u,v) ~|~ v\in V-\{u\}\}\)，其中\(|S_1|=|V|-1\)。另一种是存在边集\(S_2\)中每个边的每个端点只出现1次，其中\(|S_2|=\frac{|V|}{2}\)。这两种边集显然可以出现在同个无向图中，其都是极小边覆盖。 最小边覆盖：元素数目最小的边覆盖，根据极小边覆盖的定义，最小边覆盖一定属于极小边覆盖；… 阅读全文

基于最大流的算法定义\(G’=(V’,E’)\)为二分图\(G=(V,E)\)与其顶点划分\((L,R)\)所给定的流网络，其中\(V’=V\bigcup \{s,t\}\)，即源\(s\)与汇\(t\)是不属于\(V\)的新顶点。横跨\((L,R)\)的无向边(所有\(E\))是\(E’\)中\(L\)到\(R\)的有向边，\(E’\)需额外加入\(s\)到\(L\)所有节点的边，\(R\)所有节点到\(t\)的边。流网络的每个边的容量都是1，定义1值流\(f\in \{0,1\}\)，给出关于\(G\)与\(G’\)的关键引理： a) \(G\)存在匹配\(M\)，则\(G’\)存在1值流\(f\)，其中\(|f|=|M|\)；… 阅读全文