Solution Found!
A mail carrier must deliver mail on foot along the streets of the Green Hills
Chapter 5, Problem 22(choose chapter or problem)
A mail carrier must deliver mail on foot along the streets of the Green Hills subdivision shown in Fig. 39. The mail carrier must make two passes on every block that has houses on both sides of the street (once for each side of the street), but only one pass on blocks that have houses on only one side of the street. Draw a graph that models this street-routing problem.
Questions & Answers
QUESTION:
A mail carrier must deliver mail on foot along the streets of the Green Hills subdivision shown in Fig. 39. The mail carrier must make two passes on every block that has houses on both sides of the street (once for each side of the street), but only one pass on blocks that have houses on only one side of the street. Draw a graph that models this street-routing problem.
ANSWER:Step 1 of 3
In Fig.39, we have N vertices. The edges required to be connected graph. For every edge, it is required to pay $1.
Let the N vertices are divided into two subparts i.e. m and n. Here, the m subparts contain \(\frac{N}{2}\) vertices if N is even and \(\frac{N-1}{2}\) vertices if N is odd. The remaining vertices are part of a group which has n vertices.