Introduction to NetworksNetwork ModelsNotation and TerminologyDirected and Undirected NetworksNetworks are EverywhereOverview:The Adjacency Matrix (for directed graphs)The Adjacency Matrix (for undirected graphs)The Node-Arc Incidence Matrix (for directed graphs)Representation of arc lists (for directed graphs)On network representationsPowerPoint PresentationWalksMore terminologyOn connectivityThe Bridges of Koenigsberg: Euler 1736Slide 17Slide 18Slide 19Slide 20Adding two bridges creates such a walkEulerian cycle: a closed walk that passes through each arc exactly onceEulerian cyclesMore on cyclesHamilton’s Around the World GameSlide 26The knight’s tour problemMore DefinitionsMore on TreesThe Shortest Path ProblemShortest Path ProblemDijkstra’s Algorithm for the Shortest Path ProblemA Key Step in Shortest Path AlgorithmsDijkstra’s AlgorithmAn ExampleThe Output from Dijkstra’s AlgorithmComments on Dijkstra’s AlgorithmRepresentation as an integer programConstraintsSlide 40On Incidence MatricesThe string solutionSlide 43SummarySome final commentsMIT and James Orlin © 20031Introduction to NetworksEulerian ToursHamiltonian ToursThe Shortest Path ProblemDijkstra’s Algorithm for Solving the Shortest Path ProblemMIT and James Orlin © 20032Network ModelsOptimization models that exhibit a very special structureFor special cases, this structure to dramatically reduce computational complexityFirst widespread application of LP to problems of industrial logisticsAddresses huge number of diverse applicationsToday’s lecture (first of 3): introductory material, Eulerian tours, Hamiltonian Tours, the Shortest Path ProblemMIT and James Orlin © 20033Notation and TerminologyNote: Network terminology is not (and never will be) standardized. The same concept may be denoted in many different ways.Called:• NETWORK• directed graph • digraph• graph21432143Class Handouts (Ahuja,Magnanti, Orlin)Node set N = {1, 2, 3, 4} Arc SetNetwork G = (N, A) {(1,2), (1,3), (3,2), (3,4), (2,4)}A={1-2,1-3,3-2,3-4,2-4} Graph G = (V,E) Edge set:Also SeenVertex set V = {1,2,3,4}MIT and James Orlin © 20034Directed and Undirected Networks2341abcdeAn Undirected Graph2341abcdeA Directed Graph -The field of Network Optimization concernsoptimization problems on networks-Networks are used to transport commodities• physical goods (products, liquids)• communication• electricity, etc.MIT and James Orlin © 20035Networks are EverywherePhysical Networks–Road Networks–Railway Networks–Airline traffic Networks–Electrical networks, e.g., the power gridAbstract networks–organizational charts–precedence relationships in projectsOthers?MIT and James Orlin © 20036Overview: Networks and graphs are powerful modeling tools.Most OR models have networks or graphs as a major aspectNext three lectures: we will develop models that are efficiently solvable. –Help form a toolkit for those problems that are harder to solveNext: representations of networks–A great insight from computer scientists: how data is represented is important to how it is usedMIT and James Orlin © 20037The Adjacency Matrix (for directed graphs)2341abcdeA Directed Graph0 1 0 10 0 1 00 0 0 00 1 1 0� �� �� �� �� �� �•Have a row for each node1 2 3 41234•Have a column for each node•Put a 1 in row i- column j if (i,j) is an arc What would happen if (4,2) became (2,4)?MIT and James Orlin © 20038The Adjacency Matrix (for undirected graphs)0 1 0 11 0 1 10 1 0 11 1 1 0� �� �� �� �� �� �•Have a row for each node1 2 3 41234•Have a column for each node•Put a 1 in row i- column j if (i,j) is an arc 2341abcdeAn Undirected GraphThe degree of a node is the number of incident arcsdegree 2323MIT and James Orlin © 20039The Node-Arc Incidence Matrix (for directed graphs)2341abcdeA Directed Graph1 1 0 0 00 1 1 0 10 0 0 1 11 0 1 1 0� �� �- -� �� �- -� �-� �•Have a row for each nodea b c d e1234•Have a column for each arc•Put a 1 in row i- column j if arc j starts at node i. •Put a -1 in row i- column j if arc j ends at node i. What would happen if arc (4,2) became arc (2,4)?MIT and James Orlin © 200310Representation of arc lists (for directed graphs)2341abcdeA Directed Graph•Create a list arcs for each node1: (1,2), (1,4)2: (2,3)3:  4: (4,2), (4,3)•There are lots of very similar variants of this type of representationMIT and James Orlin © 200311On network representationsEach representation has its advantages–Major purpose of a representation•efficiency in algorithms•ease of useNode arc incidence matrix shows up in Linear ProgramsNext: definitions for networksMIT and James Orlin © 200312Directed Path . Example: 1, 2, 5, 3, 4 (or 1, a, 2, c, 5, d, 3, e, 4)•No node is repeated.•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.Path: Example: 5, 2, 3, 4. (or 5, c, 2, b, 3, e, 4)•No node is repeated.•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.234a bc15de234 a bc d1e234a bc15de234 a bc d1eMIT and James Orlin © 200313Walks2341abcde52341abcde5Walks are paths that can repeat nodes and arcsExample of a directed walk: 1-2-3-5-4-2-3-5A walk is closed if its first and last nodes are the same.A closed walk is a cycle except that it can repeat nodes and arcs.MIT and James Orlin © 200314More terminologyAn undirected network is connected if every node can be reached from every other node by a path2143521435A directed network is connected if it’s undirected version is connected.This directed graph is connected, even though there is no directed path between 2 and 5.MIT and James Orlin © 200315On connectivity61437210895There are simple efficient procedures for determining if a graph is connected.Here is a graph with two components, that is maximally connected subgraphs.4710 9We will not describe these algorithms, but will do a more general algorithm later in this lectureMIT and James Orlin © 200316The Bridges of Koenigsberg: Euler 1736“Graph Theory” began in 1736Leonard Euler–Visited Koenigsberg–People wondered whether it is possible to take a walk, end up where