NETWORK MODELS A network consists of arcs and nodes. Arcs may be directed or undirected. A tree is a network without loops. A spanning tree is a tree connecting all nodes. Oliver Yu 2015 Network1 THE MINIMAL SPANNING TREE PROBLEM Minimal spanning tree: the spanning tree with the smallest sum of the branch lengths. Solution Algorithm: Start with any node and select the shortest branch connecting any connected node with a new unconnected node Repeat the process with the new node until all nodes are connected Oliver Yu 2015 Network2 SHORTEST ROUTE PROBLEM: SOLUTION ALGORITHM Initiation Start with the Origin node O, and let S be the set of nodes that is one step away from O and connect these nodes to O. Next Step Let C be the subset of connected nodes in S with the shortest distance from O; for each node in C, record its distance to O as well as the symbol of the previous node it is connected (for the initiation, the previous node is O). If the Destination node D is in C, then the shortest route from O is found by tracing back the route from D to O. If not, connect each node in C to a not yet connected node that is one step away; these newly connected nodes together those in S that are not in C become the new S; then go to Next Step. Oliver Yu 2015 Network3 Problem 9-33 Bechtold Construction is in the process of installing power lines to a large housing development. Steve Bechtold wants to minimize the total length of wire used, which will minimize his costs. The housing development is shown as a network. Each house has been numbered, and the distances between houses are given in hundreds of feet. What do you recommend? Oliver Yu 2015 Network4 HOMEWORK ASSIGNMENTS HW12 (20 points): Use Network for Problem 933 to find a minimal spanning tree. HW13 (20 points): Use Network for Problem 933 to find the shortest route from node 1 to node 14. Oliver Yu 2015 Network5