Question

Suppose that an airline must reduce its flight schedule tosave money. If its original routes are as illustrated here, which flights can be discontinued to retain service between all pairs of cities (where it may be necessary to combine flights to fly from one city to another)?

Short answer

For the result follow the steps.

Step-by-step solution

method for finding breadth first search.

In breadth first search first choose a root. Add all edges incident to the root. Then each of the vertices at level 1, add all edges incident with ta vertex not included in the tree yet. And repeat until all vertices were added to the tree.

Find the result.

By using the breadth first search method get the result.

Let’s start from the vertex with the most amount of edges connecting to it, which is Chicago flight.

Now add all edges that are incident to Chicago.

Now, add all edges incident to Denver.

Finally, draw an edge from Boston to Bangor.

The resulting trees is then a possible spanning tree.All edges not included in the spanning tree are then all flights that should be discontinued.

The spanning tree is

The flights to be discontinued.

Some flights are mention below

Denver-St Louis

Los Angeles-Dallas

Los Angeles-Atlanta

St Louis-Dallas

And flights may be very.

This is the required result.