The graph to the right represents a network of water mains. Each vertex is an access...

    

Transcribed Image Text:

The graph to the right represents a network of water mains. Each vertex is an access point, and each edge is a segment of pipe. The city suspects that one of the pipes might be leaking, and would like to send a robot through the network to inspect each segment. (a) Suppose that the robot is placed in the net- work and removed from it using only a single access point. How can you conclude that either the robot skips a segment of pipe, or visits a segment of pipe at least twice? (b) If it is very important that the robot travels through each segment exactly once, indicate which access points should be used to put the robot in the network and remove it? Why did you choose those access points? (c) Trace a path through the network starting at one of your indicated access points, and ending at the other. Label the vertices to indicate the order in which they are encountered (some vertices may be labelled multiple times, if they are encountered multiple times). Activate Windows Go to Settings to activate Windows The graph to the right represents a network of water mains. Each vertex is an access point, and each edge is a segment of pipe. The city suspects that one of the pipes might be leaking, and would like to send a robot through the network to inspect each segment. (a) Suppose that the robot is placed in the net- work and removed from it using only a single access point. How can you conclude that either the robot skips a segment of pipe, or visits a segment of pipe at least twice? (b) If it is very important that the robot travels through each segment exactly once, indicate which access points should be used to put the robot in the network and remove it? Why did you choose those access points? (c) Trace a path through the network starting at one of your indicated access points, and ending at the other. Label the vertices to indicate the order in which they are encountered (some vertices may be labelled multiple times, if they are encountered multiple times). Activate Windows Go to Settings to activate Windows