COMP 360 Lecture Notes - Lecture 3: Flow Network, The Algorithm, Maximum Flow Problem
27 Mar 2018
School
Department
Course
Professor
Document Summary
We are dealing with a digraph - all edges are directed. A source - all edges leave this node. A sink - no edges are leaving this node. There is only one source and sink in each digraph. A cut is a partition of the vertices into a and b such that the source is in a and the sink is in b. The capacity of the cut is the capacity of the edges from a to b. Was during the cold war when they were trying to cut off the oil supply to the. Removal of each railroad had a cost attached to it. Hence they wanted to figure out the min-cost method of removing rail roads to achieve their goal. A flow is a function f that satisfies the following: - The flow of every edge should be less than its capacity. The total flow entering a node = the total flow leaving that node.
