(4)=(1) ●若G中有割点v,则存在顶点u和W,使v 在每一条u到W的路上,在该路上边{u,x 与W,y}(x,y可能为v)必定不在同一回 路上,与(4)假设矛盾
(4)(1) 若G中有割点v，则存在顶点u和w，使v 在每一条u到w的路上，在该路上边{u, x} 与{w, y}（x, y可能为v）必定不在同一回 路上，与（4）假设矛盾
●4,双连通分支 ●1)等价关系:对于E中任意两边e;和e2, e1和e有关系分→e=e2或者e1和e,在同 回路上。 ●2)等价类E1E2,…,E导出的子图G1 G2,…,Gk,每个子图称为G的一个块, 或称双连通分支
4，双连通分支 1) 等价关系：对于 E中任意两边 e 1 和 e 2 ， e 1 和 e 2有关系 e 1 = e 2或者 e 1 和 e 2在同一 回路上。 2) 等价类 E 1, E2, …, Ek导出的子图 G 1, G 2, …, G k，每个子图称为 G的一个块， 或称双连通分支
112网络最大流 基本概念 ●1,定义11.7(网络) 设连通无自环的带权有向图中 有两个不同顶点S和t,且在弧集E上定义 个非负整数值函数C=,称该有向图 为网经,记为NV,E,C。 称为S发点,t为点,除S和t 以外其他顶点称为中闳点。C称为空量 的数,弧(D上的容量为c
11.2 网络最大流 一、基本概念 1，定义11.7（网络） 设连通无自环的带权有向图中 有两个不同顶点 s 和 t，且在弧集 E上定义 一个非负整数值函数C={cij}，称该有向图 为网络，记为N(V, E, C) 。 称为 s发点， t 为收点，除 s 和 t 以外其他顶点称为中间点。 C称为容量 函数，弧(i, j)上的容量为 cij
●2,定义11.8(流量) 在网络N(vE,C)的弧集E上定义一个非负整数值函 数!,称网络N上的流,f称为弧(D上的流量 若无弧(),则定义为0。设流满足下列条件: (1)容量限制条件:对每一条弧(),有Cr° (2)平衡条件:除S和t外的每个中间点k,有 Eef=Se,对于s和t有 V.k= s ∑f-∑rfk V.k=t 则称为网络N的一个可行流,V为流值,或称f 流量。若№中无可行流f,使>V,则称f为最大流
2，定义11.8（流量） 在网络N(V, E, C)的弧集 E上定义一个非负整数值函 数f={fij}，称 f为网络 N上的流， fij称为弧(i, j)上的流量。 若无弧(i, j)，则 fij定义为 0。设流 f满足下列条件： （ 1）容量限制条件：对每一条弧(i, j)，有 fijcij 。 （ 2）平衡条件：除 s 和 t外的每个中间点 k，有 i Vfki = j Vfjk，对于 s 和 t有 则称 f为网络 N的一个可行流， Vf为流 f的值，或称 f的 流量。若 N中无可行流 f’，使 Vf’ >Vf，则称 f为最大流。 , , f i V ki j V jk f Vk s f f Vk t
●3,定义119(饱和的/未饱和的) 若f=cn,则称弧(,)是象和的 若fc则称弧(是未第和的
3，定义11.9（饱和的 /未饱和的） 若 fij=cij，则称弧(i, j) 是饱和的； 若 fij<cij，则称弧(i, j) 是未饱和的