Question Type 6: Applying algorithm to find the shortest route covering every edge once Exercises

An urban courier must travel along every street in a network with intersections $P, Q, R,$ and $S$. The street lengths are $PQ = 3$, $QR = 4$, $RS = 6$, $SP = 5$, and $PR = 2$.

Starting and ending at $P$, find the minimal distance required to traverse each street at least once.

In the graph with vertices $A, B, C, D$ and edges $AB=2, BC=3, CD=4, DA=5, AC=1, BD=6$, determine the minimal total weight of a closed walk covering every edge at least once.

A maintenance crew must traverse every street in a network with a central hub $O$ and peripheral nodes $A, B, C, D$. The street lengths are $OA = 2$, $OB = 3$, $OC = 4$, $OD = 5$, and the ring streets are $AB = 1$, $BC = 1$, $CD = 1$, $DA = 1$.

Starting and ending at $O$, find the minimal distance required to cover each street at least once.

On a map, five villages $A, B, C, D$ and $E$ are connected by roads with the following lengths: $AB=3$, $AC=4$, $AD=2$, $BC=5$, $CD=6$, $DE=3$ and $BE=4$.

Starting and ending at $A$, find the minimum length of a route that travels along each road at least once.

A tree network consists of a central node $O$ connected to leaves $A$, $B$, and $C$ by edges $OA = 3$, $OB = 4$, and $OC = 5$. Find the length of the minimal closed walk that covers every edge at least once.

Show that the graph with vertices $1, 2, 3$ and edges $1-2 = 5$, $2-3 = 7$, $3-1 = 4$ has an Eulerian circuit and state its length.

In a connected weighted graph, explain why duplicating the minimal-weight perfect matching on the odd-degree vertices yields an Eulerian multigraph and hence solves the Chinese postman problem.

A street network is represented by a graph with vertices $V = \{1, 2, 3, 4, 5, 6\}$ and edges with the following weights:

• Edge $\{1, 2\}$ has weight 2
• Edge $\{2, 3\}$ has weight 3
• Edge $\{3, 4\}$ has weight 4
• Edge $\{4, 5\}$ has weight 5
• Edge $\{5, 6\}$ has weight 6
• Edge $\{6, 1\}$ has weight 1
• Edge $\{2, 5\}$ has weight 2
• Edge $\{3, 6\}$ has weight 3

Find the minimum length of a closed path that covers each street at least once.

Consider a graph with vertices $A, B, C$, and $D$ and weighted edges $AB=3$, $BC=4$, $CD=5$, $DA=2$, and $BD=6$.

Find the length of the shortest closed walk starting and ending at $A$ that covers every edge at least once.

In a graph with vertices A, B, C, D, E and edge weights $AB=2$, $BC=3$, $CD=4$, $DE=5$, $EA=6$, $AC=1$, determine the minimum length of a closed walk starting and ending at A that traverses every edge at least once.