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