15.082 and 6.855J Fall 2010 Network Optimization J.B. OrlinWELCOME!  Welcome to 15.082/6.855J  Introduction to Network Optimization  Instructor: James B. Orlin  TA: David Goldberg  Textbook: Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, and Orlin referred to as AMO 2Quick Overview  Next: The Koenigsberg Bridge Problem  Introduces Networks and Network Algorithms  Some subject management issues  Network flows and applications  Computational Complexity  Overall goal of today’s lecture: set the tone for the rest of the subject  provide background  provide motivation  handle some class logistics 3On the background of students  Requirement for this class  Either Linear Programming (15.081J)  or Data Structures  Mathematical proofs  The homework exercises usually call for proofs.  The midterms will not require proofs.  For those who have not done many proofs before, the TA will provide guidance 4Some aspects of the class  Fondness for Powerpoint animations  Cold-calling as a way to speed up learning of the algorithms  Talking with partners (the person next to you in in the classroom.)  Class time: used for presenting theory, algorithms, applications  mostly outlines of proofs illustrated by examples (not detailed proofs)  detailed proofs are in the text 5The Bridges of Koenigsberg: Euler 1736  “Graph Theory” began in 1736  Leonard Eüler  Visited Koenigsberg  People wondered whether it is possible to take a walk, end up where you started from, and cross each bridge in Koenigsberg exactly once  Generally it was believed to be impossible 6The Bridges of Koenigsberg: Euler 1736 A D C B 1 2 4 3 7 65 Is it possible to start in A, cross over each bridge exactly once, and end up back in A? 7The Bridges of Koenigsberg: Euler 1736 A D C B 1 2 4 3 7 65 Conceptualization: Land masses are “nodes”. 8The Bridges of Koenigsberg: Euler 1736 1 2 4 3 7 65 A C D B Conceptualization: Bridges are “arcs.” 9The Bridges of Koenigsberg: Euler 1736 1 2 4 3 7 65 A C D B Is there a “walk” starting at A and ending at A and passing through each arc exactly once? 10Notation and Terminology Network terminology as used in AMO. b b 234 1 c 234 1 ca a e e d d An Undirected Graph or A Directed Graph or Undirected Network Directed Network Network G = (N, A) Node set N = {1, 2, 3, 4} Arc Set A = {(1,2), (1,3), (3,2), (3,4), (2,4)} In an undirected graph, (i,j) = (j,i) 112 3 4a b c 1 5 d e Path: Example: 5, 2, 3, 4. (or 5, c, 2, b, 3, e, 4) •No node is repeated. •Directions are ignored. Directed Path . Example: 1, 2, 5, 3, 4 (or 1, a, 2, c, 5, d, 3, e, 4) •No node is repeated. 2 3 4a b c 1 5 d e •Directions are important. Cycle (or circuit or loop) 1, 2, 3, 1. (or 1, a, 2, b, 3, e) •A path with 2 or more nodes, except that the first node is the last node. •Directions are ignored. Directed Cycle: (1, 2, 3, 4, 1) or 1, a, 2, b, 3, c, 4, d, 1 •No node is repeated. •Directions are important. 2 3 4 a b cd 1 e 2 3 4 a b cd 1 esame.Walks 2 34 1 a b c d e 5 2 34 1 a b c d e 5 Walks are paths that can repeat nodes and arcs Example of a directed walk: 1-2-3-5-4-2-3-5 A walk is closed if its first and last nodes are the A closed walk is a cycle except that it can repeat nodes and arcs. 1314 The Bridges of Koenigsberg: Euler 1736 1 2 4 3 7 65 A C D B Is there a “walk” starting at A and ending at A and passing through each arc exactly once? Such a walk is called an eulerian cycle.Adding two bridges creates such a walk 1 2 4 3 7 65 A C D B 8 9 Here is the walk. A, 1, B, 5, D, 6, B, 4, C, 8, A, 3, C, 7, D, 9, B, 2, A Note: the number of arcs incident to B is twice the number of times that B appears on the walk. 15On Eulerian Cycles 1 2 4 3 7 65 A C D B 8 9 6 4 4 4 The degree of a node in an undirected graph is the number of incident arcs Theorem. An undirected graph has an eulerian cycle if and only if (1) every node degree is even and (2) the graph is connected (that is, there is a path from each node to each other node).4537More on Euler’s Theorem  Necessity of two conditions:  Any eulerian cycle “visits” each node an even number of times  Any eulerian cycle shows the network is connected  caveat: nodes of degree 0  Sufficiency of the condition  Assume the result is true for all graphs with fewer than |A| arcs.  Start at some node, and take a walk until a cycle C is found. 1 45 37 175More on Euler’s Theorem  Sufficiency of the condition  Start at some node, and take a walk until a cycle C is found.  Consider G’ = (N, A\C)  the degree of each node is even  each component is connected  So, G’ is the union of Eulerian cycles  Connect G’ into a single eulerian cycle by adding C. 18 4 37Comments on Euler’s theorem 1. It reflects how proofs are done in class, often in outline form, with key ideas illustrated. 2. However, this proof does not directly lead to an efficient algorithm. (More on this in two lectures.) 3. Usually we focus on efficient algorithms. 1915.082/6.855J Subject Goals: 1. To present students with a knowledge of the state-of-the art in the theory and practice of solving network flow problems.  A lot has happened since 1736 2. To provide students with a rigorous analysis of network flow algorithms.  computational complexity & worst case analysis 3. To help each student develop his or her own intuition about algorithm development and algorithm analysis. 20Homework Sets and Grading  Homework Sets  6 assignments  4 points per assignment  lots of practice problems with solutions  Grading  homework: 24 points  Project 16 points  Midterm 1: 30 points  Midterm 2: 30 points 21Class discussion  Have you seen network models elsewhere?  Do you have any specific goals in taking this subject? 22Mental break Which nation gave women the right to vote first? New Zealand. Which Ocean goes to the deepest depths? Pacific Ocean What is northernmost land on earth? Cape Morris Jessep in Greenland Where is the Worlds Largest Aquarium? Epcot Center in Orlando, FL 23Mental break What country has not fought in a war since 1815? Switzerland What does the term Prima Donna mean in Opera? The leading female singer What fruit were Hawaiian women once forbidden by law …