网站建设要多少费用,商标注册查询官方网站,网页设计规划书模板,国内外公司网站差异CSDN 有字数限制#xff0c;因此笔记分别发布#xff0c;目前#xff1a;
【笔记1】概念与计算、树及其算法【笔记2】容量网络模型 4 最大流及其算法
4.1 容量网络模型
4.1.1 容量网络
容量网络#xff1a;如果一个加权有向网络 D D D 满足如下三个条件#xff1a;①…CSDN 有字数限制因此笔记分别发布目前
【笔记1】概念与计算、树及其算法【笔记2】容量网络模型 4 最大流及其算法
4.1 容量网络模型
4.1.1 容量网络
容量网络如果一个加权有向网络 D D D 满足如下三个条件①存在唯一一个入度为 0 0 0 的顶点称为源②存在唯一一个出度为 0 0 0 的顶点称为汇③每条弧 ( v i , v j ) (v_i,v_j) (vi,vj) 赋权 c i j c_{ij} cij 是一个非负数称为弧 ( v i , v j ) (v_i,v_j) (vi,vj) 的容量则把这个加权有向网络 D D D 称为容量网络。 4.1.2 流
流设 D D D 是一个容量网络令 c i j c_{ij} cij 表示弧 ( v i , v j ) (v_i,v_j) (vi,vj) 的容量。设 f f f 是定义在 D D D 的弧集上的一个函数它赋予每条弧 ( v i , v j ) (v_i,v_j) (vi,vj) 一个非负实数 f i j f_{ij} fij若 f f f 满足① f i j ≤ c i j f_{ij} \leq c_{ij} fij≤cij② ∀ v j ∈ V ( D ) \forall v_j \in V(D) ∀vj∈V(D) \ { v s , v t } \{v_s,v_t\} {vs,vt} 有 ∑ ( v i , v j ) ∈ E ( D ) f i j ∑ ( v j , v i ) ∈ E ( D ) f j i \sum_{(v_i,v_j)\in E(D)} f_{ij} \sum_{(v_j,v_i)\in E(D)} f_{ji} ∑(vi,vj)∈E(D)fij∑(vj,vi)∈E(D)fji则称 f f f 为容量网络 D D D 的一个流称 f i j f_{ij} fij 为弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上的流量。 (非)饱和弧弧上的流量(未)达到弧的容量。 4.1.3 流值
定理设 f f f 是容量网络 D D D 的一个流其中源为 v s v_s vs汇为 v t v_t vt由源的流出量等于汇的流入量即 ∑ ( v s , v j ) ∈ E ( D ) f s i ∑ ( v i , v t ) ∈ E ( D ) f i t \sum_{(v_s,v_j)\in E(D)}f_{si}\sum_{(v_i,v_t)\in E(D)}f_{it} ∑(vs,vj)∈E(D)fsi∑(vi,vt)∈E(D)fit 证明注意到每条弧上的流量既是其头顶点的流入量也是其尾顶点的流出量因此所有弧上的流量之和、所有顶顶啊的流入量之和、所有顶点的流出量之和这三者相等。 流值设 f f f 是容量网络 D D D 的一个流其源为 v s v_s vs汇为 v t v_t vt称源的流出量为流 f f f 的流值记作 v a l ( f ) val(f) val(f)。 4.1.4 最大流
最大流设 D D D 是一个容量网络若 f f f 是 D D D 上流值最大的流则把 f f f 称为 D D D 的最大流。 截设 D D D 是一个容量网络源为 v s v_s vs汇为 v t v_t vt。设顶点子集 S ⊂ V ( D ) , S ‾ V ( D ) S \subset V(D),\overline{S}V(D) S⊂V(D),SV(D) \ S S S且 v s ∈ S , v t ∈ S ‾ v_s\in S, v_t \in \overline{S} vs∈S,vt∈S则称弧集 { ( v i , v j ) ∈ E ( D ) ∣ v i ∈ S , v j ∈ S ‾ } \{(v_i,v_j)\in E(D)|v_i \in S, v_j \in \overline{S}\} {(vi,vj)∈E(D)∣vi∈S,vj∈S} 为容量网络 D D D 的截记作 ( S , S ‾ ) (S,\overline{S}) (S,S)。 截的容量 ∑ ( v i , v j ) ∈ ( S , S ‾ ) c i j \sum_{(v_i,v_j)\in(S,\overline{S})}c_{ij} ∑(vi,vj)∈(S,S)cij记作 c ( S , S ‾ ) c_(S,\overline{S}) c(S,S)。 最小截容量达最小的截为最小截。 定理设 D D D 是一个容量网络源为 v s v_s vs汇为 v t v_t vt。设 f f f 是容量网络 D D D 的一个流 ( S , S ‾ ) (S,\overline{S}) (S,S) 是 D D D 的一个截则有 v a l ( f ) ≤ c ( S , S ‾ ) val(f) \leq c(S,\overline{S}) val(f)≤c(S,S)。 证明… 流值与截容量相等当且仅当每条弧都是饱和弧且无逆流的时候。 若容量网络的一个流 f f f 的流值等于某个截 ( S , S ‾ ) (S,\overline{S}) (S,S)的容量即 c ( S , S ‾ ) v a l ( f ) c(S,\overline{S})val(f) c(S,S)val(f)则 f f f 为最大流 ( S , S ‾ ) (S,\overline{S}) (S,S) 为最小截。 4.2 最大流算法
4.2.1 可增路
可增路设 P P P 是一条 ( v s , v j ) (v_s,v_j) (vs,vj) 路如果①对 P P P 中每条正向弧 ( v i , v j ) , f i j c i j (v_i,v_j),f_{ij} c_{ij} (vi,vj),fijcij②对 P P P 中每条反向弧 ( v i , v j ) , f i j 0 (v_i,v_j),f_{ij} 0 (vi,vj),fij0则称 ( v s , v j ) (v_s,v_j) (vs,vj) 为 f f f 非饱和路否则为饱和路。从源到汇的 f f f 非饱和路称为 f f f 可增路。 4.2.2 最大流算法
定理设容量网络 D D D 的源为 v s v_s vs汇为 v t v_t vt f f f 为 D D D 的一个流则 f f f 为最大流当且仅当 D D D 中不存在 f f f 可增路。 证明只需证明充分性。只需证明存在截 ( S , S ‾ ) (S,\overline{S}) (S,S) 满足 ( S , S ‾ ) (S,\overline{S}) (S,S) 中的每条弧都是饱和弧 ( S ‾ , S ) (\overline{S}, S) (S,S) 中的每条弧都是零弧。 将顶点分类令 S { v s } ∪ { v j ∣ 存在一条 f 非饱和路 ( v s , v j ) } S\{v_s\} \cup \{v_j|存在一条 f 非饱和路 (v_s,v_j)\} S{vs}∪{vj∣存在一条f非饱和路(vs,vj)}故有 v t ∈ S ‾ v_t \in \overline{S} vt∈S 。 则 S S S 与 S ‾ \overline S S 之间假设 f i j c i j f_{ij} c_{ij} fijcij易见 P ( v i , v j ) P(v_i,v_j) P(vi,vj) 亦为 f f f 非饱和路与 v j ∈ S ‾ v_j \in \overline{S} vj∈S 矛盾。同理可以证明 f i j 0 f_{ij}0 fij0。 标号法能求解可增路 4.2.3 最大流最小截定理
最大流算法结束时最大流流值等于最小截容量。 定理在任何容量网络 D D D 中最大流的流值等于最小截的容量。 证明(大致思路)设 S S S 为能用标号法能够获得标号的顶点集合则 ( S , S ‾ ) (S,\overline{S}) (S,S) 之间的弧的值必定为 0 0 0。 4.3 最小费用最大流
4.3.1 问题描述
流 f f f 的费用设容量网络 D D D 的源为 v s v_s vs汇为 v t v_t vt c i j c_{ij} cij 和 b i j b_{ij} bij 分别表示弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上的容量和单位流量费用设 f f f 是 G G G 的流则称 b ( f ) ∑ ( v i , v j ) ∈ E ( D ) f i j b i j b(f)\sum_{(v_i,v_j)\in E(D)}f_{ij}b_{ij} b(f)∑(vi,vj)∈E(D)fijbij 为流 f f f 的费用。在容量网络 D D D 的所有最大流中寻找费用最小的流这样的流称为最小费用最大流。 4.3.2 F增广圈
增广圈设 Q Q Q 是一个具有指定正向的圈 Q Q^ Q 为圈 Q Q Q 上正向弧的集合 Q − Q^- Q− 为圈 Q Q Q 上反向弧的集合。 δ i j c i j − f i j ( v i , v j ) ∈ Q \delta_{ij}c_{ij}-f_{ij}(v_i,v_j) \in Q^ δijcij−fij(vi,vj)∈Q δ i j f i j ( v i , v j ) ∈ Q − \delta_{ij}f_{ij}(v_i,v_j) \in Q^- δijfij(vi,vj)∈Q−。 δ ( Q ) m i n { δ i j ∣ ( v i , v j ) ∈ E ( Q ) } \delta(Q)min\{\delta_{ij}|(v_i,v_j) \in E(Q)\} δ(Q)min{δij∣(vi,vj)∈E(Q)}。 若 δ ( Q ) 0 \delta(Q)0 δ(Q)0则称 δ ( Q ) \delta(Q) δ(Q) 为允许修改流量称圈 Q Q Q 为容量网络 D D D 上关于流 f f f 的增广圈。 对于 f f f 增广圈 Q Q Q我们可以定义 f ′ f f′ f i j ′ f i j δ ( Q ) ( v i , v j ) ∈ Q f_{ij}^{}f_{ij} \delta(Q)(v_i,v_j)\in Q^ fij′fijδ(Q)(vi,vj)∈Q f i j ′ f i j − δ ( Q ) ( v i , v j ) ∈ Q − f_{ij}^{}f_{ij} - \delta(Q)(v_i,v_j)\in Q^- fij′fij−δ(Q)(vi,vj)∈Q− f i j ( v i , v j ) ∉ E ( Q ) f_{ij}(v_i,v_j) \notin E(Q) fij(vi,vj)∈/E(Q)
这样 f ′ f f′ 仍是 D D D 的流并且 v a l ( f ′ ) v a l ( f ) val(f)val(f) val(f′)val(f)称 f ′ f f′ 为基于 f f f 增广圈 Q Q Q 的修正流。
负圈设有容量网络 D D D f f f 是一个流 f i j , c i j , b i j f_{ij},c_{ij},b_{ij} fij,cij,bij 分别为弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上的流量、容量和单位费用设 Q Q Q 是关于流 f f f 的增广圈。称 b ( Q , f ) ∑ ( v i , v j ) ∈ Q b i j − ∑ ( v i , v j ) ∈ Q − b i j b(Q,f)\sum_{(v_i,v_j)\in Q^}b_{ij}-\sum_{(v_i,v_j)\in Q^-}b_{ij} b(Q,f)∑(vi,vj)∈Qbij−∑(vi,vj)∈Q−bij 为增广圈的费用若小于 0 0 0则称 Q Q Q 为负圈。负圈与流量、容量、费用、圈的指定方向有关。 4.3.3 Klein 算法
算法
求容量网络 D D D 的一个最大流。寻找网络中的负圈。若没有负圈算法结束若找到一个负圈转step 3修改负圈 Q Q Q 上各弧的流量得到修正流。在新修正流的基础上转step 2继续寻找负圈。
定理设有容量网络 D D D f f f 是一个流 f i j , c i j , b i j f_{ij},c_{ij},b_{ij} fij,cij,bij 分别为弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上的流量、容量和单位费用则 f f f 是最小费用最大流当且仅当任何 f f f 增广圈 Q Q Q 的费用 b ( Q , f ) ≥ 0 b(Q,f)\geq0 b(Q,f)≥0即无负圈。 5 遍历性及其算法
5.1 Euler图和有向Euler图
5.1.1 定义
Euler图如果图 G G G 中存在包含所有边的闭迹 W W W则称 G G G 为 E u l e r Euler Euler 图 W W W 称为 G G G 的 E u l e r Euler Euler 闭迹。 半Euler图如果图 G G G 中存在包含所有边的迹 P P P则称 G G G 为 半 E u l e r 半Euler 半Euler 图 P P P 称为 G G G 的 E u l e r Euler Euler 迹。 定理设 G G G 为非空连通图则下面三个命题等价 G G G 是 E u l e r Euler Euler 图 G G G 中不含奇点 G G G 可以表示为若干个没有公共边的圈的并。
证明
1-2:设 G G G 是连通的 E u l e r Euler Euler 图 W W W 是 G G G 的 E u l e r Euler Euler 闭迹则 ∀ v ∈ V ( G ) v \forall v \in V(G)v ∀v∈V(G)v 必定在 W W W 中出现当 v v v 作为内部点每出现一次必定与 G G G 中两条边关联当 v v v 作为 W W W 的起点则 v v v 也是重点从而它必与两条边关联因此 G G G 的每个顶点都是偶点。2-3:设 G G G 是非空连通图且不含奇点则 G G G 不是树从而 G G G 中含有圈不断取出圈来得到新图再取圈因此可以从第二个命题演变成第三个命题。3-1:由 E u l e r Euler Euler 图的定义结论显然。
有向Euler图若有向图 D D D 中存在包含所有弧的有向闭迹则称 D D D 为有向 E u l e r Euler Euler 图这样的有向闭迹称为 D D D 的有向 E u l e r Euler Euler 闭迹。 有向半Euler图若有向图 D D D 中存在包含所有弧的有向迹则称 D D D 为有向 E u l e r Euler Euler 图这样的有向迹称为 D D D 的有向 E u l e r Euler Euler 迹。 定理设 G G G 为非空连通有向图则下面三个命题等价 D D D 是有向 E u l e r Euler Euler 图 ∀ v ∈ V ( D ) \forall v \in V(D) ∀v∈V(D)有 d ( v ) d − ( v ) d^(v)d^-(v) d(v)d−(v) G G G 可以表示为弧不交的回路的并。 5.1.2 Fleury 算法
算法思想从任意顶点出发除非别无选择否则总是选择一条不是割边的且没走过的边直到获得 E u l e r Euler Euler 闭迹为止。 定理设 G G G 是 E u l e r Euler Euler 图 W v 0 e 1 v 1 . . . e n v n Wv_0e_1v_1...e_nv_n Wv0e1v1...envn 是 F l e u r y Fleury Fleury 算法结束时得到的迹则 W W W 一定是图 G G G 的 E u l e r Euler Euler 闭迹。 证明… 5.1.3 编码盘设计
例题16个二进制数应该如何排列使得圆盘沿顺时针旋转一部分恰好组成 0000 0000 0000 到 1111 1111 1111 的 16 16 16 组四位二进制输出同时旋转一周又返回到 0000 0000 0000 状态 答案定义一个有 8 8 8 个顶点的有向图 D D D其中顶点用 3 3 3 维 0 − 1 0-1 0−1 序列 x 1 x 2 x 3 x_1x_2x_3 x1x2x3 标记且顶点 x 1 x 2 x 3 x_1x_2x_3 x1x2x3 与顶点 x 2 x 3 0 , x 2 x 3 1 x_2x_30,x_2x_31 x2x30,x2x31 以出弧的形式相连这样得到的有向图 D D D 中每个顶点的入度和出度相等都等于 2 2 2。然后从 000 000 000 出发可以得到一个有向 E u l e r Euler Euler 闭迹为 …。注意起终点重复所以序列取末尾数字得… 该问题可以扩展得到的有向图为德布鲁英图 B ( 2 , n ) B(2,n) B(2,n)。每个顶点最后一位数字构成序列为 德布鲁英序列。 5.2 中国邮递员问题
5.2.1 问题描述
管梅谷教授提出并研究了中国邮递员问题。 问题内容在加权连通图 G G G 中寻找一条经过每条边至少一次且权和最小的闭迹即 G G G 的最优环游。 思考角度对于重复走的边可以看作为两点之间的重边(即重复走的边视为 k k k 重边)。 5.2.2 奇偶点图上作业法
最优环游的奇偶点图上作业法
把图 G G G 所有奇点配成对将每对奇点之间的一条链的每条边改为二重边得到一个新图 G 1 G_1 G1图中没有奇点在图 G 1 G_1 G1 中若顶点之间有 k ( k ≥ 3 ) k(k\geq3) k(k≥3) 重边则去掉其中偶数条只保留 1 / 2 1/2 1/2 条边得到图 G 2 G_2 G2。检查 G 2 G_2 G2 中的每一个圈 C C C若重复边的权和超过此圈权和的一半则重边变为单边单边变为二重边重复这一过程直到所有圈上重边的权和都不超过圈权和一半得到 G 3 G_3 G3。用 F l e u r y Fleury Fleury 算法求 G 3 G_3 G3 的 E u l e r Euler Euler 闭迹得到图 G G G 的最优环游
定理设 G G G 是加权连通图则奇偶点图上作业法得到的闭途径是最优环游。 证明… 例题
答案图 G G G 中有 6 6 6 个奇点 v 2 , v 3 , v 5 , v 8 , v 10 , v 11 v_2,v_3,v_5,v_8,v_{10},v_{11} v2,v3,v5,v8,v10,v11将它们搭配成三对因此添加 v 2 v 3 v 4 v 5 v 3 v 2 v 1 v 8 v 10 v 11 v_2v_3v_4v_5v_3v_2v_1v_8v_{10}v_{11} v2v3v4v5v3v2v1v8v10v11。注意 v 2 v 3 v_2v_3 v2v3 间有两条新添加的边删去得到新图。 v 1 v 2 v 7 v 8 v 1 v 3 v 4 v 5 v 6 v 3 v_1v_2v_7v_8v_1v_3v_4v_5v_6v_3 v1v2v7v8v1v3v4v5v6v3 中非最优添边因此重边变单边单边变重边再次得到新图 再检查圈 v 2 v 3 v 6 v 11 v 10 v 7 v 2 v_2v_3v_6v_{11}v_{10}v_7v_2 v2v3v6v11v10v7v2也非最优执行单重边置反得到新图。 检查通过执行 F l e u r y Fleury Fleury 算法得到最优环游为 v 1 v 2 v 3 v 2 v 7 v 8 v 7 v 6 v 5 v 6 v 11 v 12 v 5 v 4 v 3 v 6 v 11 v 10 v 7 v 10 v 9 v 8 v 1 v_1v_2v_3v_2v_7v_8v_7v_6v_5v_6v_{11}v_{12}v_5v_4v_3v_6v_{11}v_{10}v_7v_{10}v_9v_8v_1 v1v2v3v2v7v8v7v6v5v6v11v12v5v4v3v6v11v10v7v10v9v8v1环游总长度 109 109 109。
