第1章图论2.ppt

算法终止后，令已标号的点的集合为S， S S 则割 (S, ) 即为最小割，从而最大流量 fV = c(S, ) fV 也等于发点发出的总量或流进收点 t 的总量。 例2 求图1-50中网络G =〈V, E〉的最大流。 d a s b c t 3 4 1 2 3 5 5 3 5 图1-50 解（1） 对所有(x,y)∈E, 令 f(x,y) = 0，如图（a）的各边的第二位数，标 s 为（s+,∞）。 a(s+,3) s d b(s+,4) c t 5,0 5,0 5,0 3,0 1,0 3,0 4,0 3,0 （s+,∞） 2,0 （a） （2） 对s 的邻接点a ，标（s+,3）。这是因 s 指向a ，故 s 的上标为+，又 δa = min{∞, c(s,a)- f(s,a)} = min{∞, 3-0} = 3 同理，对s 的邻接点b，标（s+,4），如图（a）所示。 a(s+,3) s d b(s+,4) c(a+,3) t 5,0 5,0 5,0 3,0 1,0 3,0 4,0 3,0 （s+,∞） （c+,3） （b+,3） (b) 2,0 将边 s,a，a,c 和 c,t 各边的流量增加δt（即3），再去掉各点（除 s 点）的标号得图（c）。 （3） 对与a 相邻的点c标（a+,3）；与b 相邻的点d 标（b+,3）；与c 相邻的点t 标（c+,3）。此时δt =3，同时得可增路 sact（此路是自t 由其标号反向查找前一个点，直至 s 而得出），如图（b）。 （c）重新标号得 图（d）， 路Γ= sbdt 为可增路， δt =3 a s d b c t 5,3 5,0 5,0 3,3 1,0 3,0 4,0 3,3 （s+,∞） (c) 2,0 a(b+,4) s d(b+,3) b (s+,4) c t 5,3 5,0 5,0 3,3 1,0 3,0 4,0 3,3 （s+,∞） (d) 2,0 (d+,3) a s d b c t 5,3 5,0 5,3 3,3 1,0 3,3 4,3 3,3 （s+,∞） (e) 2,0 a(b+,1) s d(c+,1) b (s+,1) c(a+,1) t 5,3 5,0 5,3 3,3 1,0 3,3 4,3 3,3 （s+,∞） (f) 2,0 (d+,1) 由（e）继续 标号得（f） 将Γ中各边 的流量增加3 后删去标号 得图（e） a s d b c t 5,4 5,1 5,4 3,3 1,1 3,3 4,4 3,3 (g) 2,0 由（f）增流得（g），由（g）得最大流，其值为 7。 定理28 若运输网络G 中各边容量均为整数，则必存在整数最大流。 Thank you! 上图的 (a),(b) 表达了一个图的两个3-着色，其中(b)为正常的，易知该图有c＝3。 (a) (b) 定理 对任意的图G 均有： ≤Δ+1 c 证明 对图G 的点数n用归纳法。 当n＝1 时，c =1，Δ≥0，满足 c ≤Δ+1。 对n≥2 的图G , 取 u∈V(G), 设 G’＝G-u 。由归纳假设 c (G’)≤Δ(G’)+1，从而存在 G’ 的 (Δ(G’)+1)-着色φ 。因 Δ(G’)≤Δ(G), 所以 φ 也是 G’ 的(Δ(G)+1)-着色。 (G)≤Δ(G)+1 c 设 dG(u) = k, G 中与 u 相邻的点为 v1,v2,…,vk。因 | {φ(v1), …, φ(vk)} | ≤k ＜ Δ(G)+1, 所以存在 j ∈ {1,2,…,Δ(G)+1} 满足 j ?{φ(v1), …, φ(vk)}, 令φ (u)=j, 则 φ 被扩充为 G 的一个(Δ(G)+1)-着色，所以 定理 设G是连通图。假定G既不是完全图又不是奇圈，则 ≤Δ c 一个着色算法： 给定图G = (V，E)， 设V ={v1, v2,…, vn}，着色函数为 φ ，色集 C ={1, 2, …, Δ+1}。 (i) 令φ (v1)=1, i =1。 (ii) 若 i = n, 则停；否则令 C(vi＋1) = {φ (vj) | j ≤i 并且 vj 与 vi＋1 相邻} 设 k 为 C\C(v i ＋1) 中的最小正整数，令 φ (v i＋1) = k。 (iii) 令 i = i+1, 转(ii) 例 试用算法给图中的图着色。 解 设φ 为