Iterative Improvement for Domain-Specific Problems Lecturer:Jing Liu Email:neouma@mail.xidian.edu.cn Homepage:http://see.xidian.edu.cn/faculty/liujing
Iterative Improvement for Domain-Specific Problems Lecturer: Jing Liu Email: neouma@mail.xidian.edu.cn Homepage: http://see.xidian.edu.cn/faculty/liujing
Iterative Improvement for Domain-Specific Problems In this part,we will study an algorithm design technique that we will refer to as iterative improvement. In its simplest form,this technique starts with a simple-minded (usually a greedy)solution and continues to improve on that solution in stages until an optimal solution is found. Finding a maximum flow in a network >Finding a maximum matching in undirected graphs
Iterative Improvement for Domain-Specific Problems ◼ In this part, we will study an algorithm design technique that we will refer to as iterative improvement. ◼ In its simplest form, this technique starts with a simple-minded (usually a greedy) solution and continues to improve on that solution in stages until an optimal solution is found. ➢ Finding a maximum flow in a network ➢ Finding a maximum matching in undirected graphs
Network Fow A network is a 4-tuple (G,s,t,c),where G=(,E)is a directed graph,s and tare two distinguished vertices called,respectively,the source and sink,and du,is a capacity function defined on all pairs of vertices with du,v)>0 if (u,veFand du,v)=0 otherwise.=n,=m. Next,we consider the problem of finding a maximum flow in a given network (G,s,t,c)from sto t,which is named as the max-flow problem
Network Flow ◼ A network is a 4-tuple (G, s, t, c), where G=(V, E) is a directed graph, s and t are two distinguished vertices called, respectively, the source and sink, and c(u, v) is a capacity function defined on all pairs of vertices with c(u, v)>0 if (u, v)E and c(u, v)=0 otherwise. |V|=n, |E|=m. ◼ Next, we consider the problem of finding a maximum flow in a given network (G, s, t, c) from s to t, which is named as the max-flow problem
Network Flow A fow in Gis a real-valued function fon vertex pairs having the following four conditions: (1)Skew symmetry.vu,velu,=-v).We say there is a flow from uto vif,>0. (2)Capacity constraints.Vu,veV,u,vsdu,v. We say edge (u,v)is saturated if u,=du,v). (3)Flow conservation.Vue s,veu,v)=0.In other words,the net fow(total flow out minus total flow in)at any interior vertex is 0. (4)廿vEVy)=0
Network Flow A flow in G is a real-valued function f on vertex pairs having the following four conditions: (1) Skew symmetry. u, vV, f(u, v)=-f(v, u). We say there is a flow from u to v if f(u, v)>0. (2) Capacity constraints. u, vV, f(u, v)c(u, v). We say edge (u, v) is saturated if f(u, v)=c(u, v). (3) Flow conservation. uV-{s, t}, vV f(u, v)=0. In other words, the net flow (total flow out minus total flow in) at any interior vertex is 0. (4) vV, f(v, v)=0
Network Fow A cut is,n is a partition of the vertex set Vinto two subsets Sand Tsuch that seS and te 7.The capacity of the cut{S,乃，denoted by d(S,T),is c(S,T)=∑c(4,) UES,VET The flow across the cut{S,刀，denoted by(S,刀，is f(S,T)=∑f(u,) 1l∈S,veT Thus,the flow across the cut is,n is the sum of the positive flow on edges from Sto Tminus the sum of the positive flow on edges from Tto S
Network Flow ◼ A cut {S, T} is a partition of the vertex set V into two subsets S and T such that sS and tT. The capacity of the cut {S, T}, denoted by c(S, T), is , ( , ) ( , ) u S v T c S T c u v = ◼ The flow across the cut {S, T}, denoted by f(S, T), is , ( , ) ( , ) u S v T f S T f u v = ◼ Thus, the flow across the cut {S, T} is the sum of the positive flow on edges from S to T minus the sum of the positive flow on edges from T to S