Network OptimizationThe initial flowFind a Path or Cycle WUpdatesFind a path or cycle WSlide 6Find a path or cycle using dfsSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Updates and the final flow decompositionSlide 15Network Optimization Flow Decomposition2The initial flow 12 4536234734 4859A deficit node (more flow leaving than entering).An excess node (more flow entering than leaving)A balanced node (flow in = flow out)2 -23Find a Path or Cycle W12 4536234734 48592 -21Carry out a depth first search. Stop when a node with excess is reached or when there is a cycle.Select a node with deficit if there is one.Determine the capacity of the walk W.The capacity of 1-2-4-5-3-1 is 2.2 45314Updates12 4536234734 48592 -21Subtract the flow in W from the current flow.Add the flow in W to the decomposition.02567cycle flowspath flows2 units around 1-2-4-5-3-15Find a path or cycle W12 453632534 46572-21Carry out a dfs. Select a node with deficit if there is one.Determine the capacity of W.2 453The capacity of 2-4-5-3-2 is 3.6UpdatesAdd the cycle flow to the decompositionupdate the current flowcycle flowspath flows2 units around 1-2-4-5-3-13 units around 2-4-5-3-21 632534 4657-21202342 4537Find a path or cycle using dfs1 62234 4354-2122 453Carry out a dfs. Select a node with deficit if there is one.Determine the capacity of W.6223-2122 4capacity of a path = min {arc capacity, excess, deficit} = 28Updates2234 4354-2253Add the path flow to the decompositionupdate the current flowcycle flowspath flows2 units around 1-2-4-5-3-13 units around 2-4-5-3-22 units in 1-2-4-6001001 62 41 69Find a path or cycle using dfs14 4354531 62 41 6Carry out a dfs. Select a node with deficit if there is one. Otherwise, select any node with flow leaving.Determine the capacity of W.35463The capacity is 110Updates14 4354531 62 41 6Add the cycle flow to the decompositionupdate the current flow2 units around 1-2-4-5-3-13 units around 2-4-5-3-22 units in 1-2-4-61 unit around 3-4-6-5-30343cycle flowspath flows11Find a path or cycle using dfs3 4343531 62 41 6Carry out a dfs. Select a node with deficit if there is one. Otherwise, select any node with flow leaving.Determine the capacity of W.3The capacity of 3-4-5-3 is 312Updates3 4343531 62 41 6Add the cycle flow to the decompositionupdate the current flow2 units around 1-2-4-5-3-13 units around 2-4-5-3-22 units in 1-2-4-61 unit around 3-4-6-5-33 units around 3-4-5-3cycle flows path flows13Find a path or cycle using dfs44531 62 41 6Carry out a dfs. Select a node with deficit if there is one. Otherwise, select any node with flow leaving.Determine the capacity of W.514Updates and the final flow decomposition531 62 41 6442 units around 1-2-4-5-3-13 units around 2-4-5-3-2 2 units in 1-2-4-61 unit around 3-4-6-5-33 units around 3-4-5-3Add the cycle flow to the decompositionupdate the current flow4 units around 5-6-5cycle flowspath flowsMITOpenCourseWarehttp://ocw.mit.edu15.082J / 6.855J / ESD.78J Network OptimizationFall 2010 For information about citing these materials or our Terms of Use, visit: