Suppose interstate highways join the six towns A, B, C, D,E,F as follows: 1-77 goes from B through A to 1-82 goes from C through
D then through B to F: 1-85 goes from D through A to F; 1-90 goes from C through E to F and 1-91 goes from D to E.
a) Draw a graph of the network with vertices for towns and edges for segments of interstates linking neighboring towns. b) What is the minimum number of edges whose removal prevents travel between some pair of towns?
c) Is it possible to take a trip starting from town C that goes to every town without using any interstate highway for more than one edge (the trip need not return to C?
a) Draw a graph of the network with vertices for towns and edges for segments of interstates linking neighboring towns. b) What is the minimum number of edges whose removal prevents travel between some pair of towns?
c) Is it possible to take a trip starting from town C that goes to every town without using any interstate highway for more than one edge (the trip need not return to C?
1 answer:
You might be interested in