CISC320 Lecture Notes - Lecture 13: Distributed Computing, Flow Network, Directed Graph

• School: University of Delaware
• Department: Computer and Information Sciences
• Course: CISC320
• Professor: Mohamed Zakaria

Document Summary

Involve finding a feasible flow through a single-source, single-sink flow network (with a maximum flow. G = (v, e, s, t, u: (v,e) is a directed graph with no parallel arcs, there are two distinguished nodes: S = source t = sink: c(e) = capacity of edge e. An s-t flow is a function f: e r that satisfies: for each e e: The flow must be less than the capacity: for each v v {s, t}: F(e) (flow into v) = f(e) (flow out of v) The flow into a vertex must equal the flow leaving that vertex: max flow: find s-t flow that maximizes net flow out of the source. |f| = the sum of the flow out of s (also the sum of flow into t) A partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge that is minimal in some sense.