The following graph represents a portion of the subway system of a city. The ver

Question

The following graph represents a portion of the subway system of a city. The vertices on the graph correspond to subway stations, and the edges correspond to the rails. Your job is to write a program for a cleaning car to efficiently clean this portion of the subway system.

Using Euler’s theorem, explain why it is possible to pass through all of the stations by traversing every rail only once.

Using Fleury’s algorithm, provide an optimal path to clean all the rails by passing through them only once.

Is it possible to find an optimal path described in question 3-b that starts on any station? Explain your answer.

Explanation / Answer

Euler made the remarkable discovery that whether a network is traversable depends on the number of odd vertices.

Euler found that the only traversable networks are those that have either no odd vertices or exactly two odd vertices

in the graph we have 2 odd vertices (A,B) so it is possible to pass through all of the stations by traversing every rail only once.

b) If we have 2 odd vertices, then we start at one of those two vertices.

To find our way, we choose the edge that is not a bridge if we have a choice.

A->C->D->E->G->H->E->I->J-.>E->F->B.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.