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

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.

An urban courier must travel every street in the network with intersections P, Q, R, S and street lengths $PQ=3$, $QR=4$, $RS=6$, $SP=5$, $PR=2$. Starting and ending at P, find the minimal distance to traverse each street at least once.

Consider the graph with vertices A, B, C, and D and weighted edges $AB=3$, $BC=4$, $CD=5$, $DA=2$, $BD=6$. Find the length of the shortest closed path starting and ending at A that covers every edge at least once.

A maintenance crew must traverse every street in a network with central hub O and peripheral nodes A, B, C, D. Street lengths are $OA=2$, $OB=3$, $OC=4$, $OD=5$, and the ring streets $AB=1$, $BC=1$, $CD=1$, $DA=1$. Starting and ending at O, find the minimal distance covering each street at least once.

In the 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.

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.

In the street network with vertices $1,2,3,4,5,6$ and edges weighted $1$–$2=2$, $2$–$3=3$, $3$–$4=4$, $4$–$5=5$, $5$–$6=6$, $6$–$1=1$, $2$–$5=2$, $3$–$6=3$, find the minimum length closed path covering each street at least once.

For the tree network with central node O connected to leaves A, B, C by edges $OA=3$, $OB=4$, $OC=5$, find the minimal closed walk covering every edge at least once.

On a map, five villages A, B, C, D, E are connected by roads of lengths $AB=3$, $AC=4$, $AD=2$, $BC=5$, $CD=6$, $DE=3$, $BE=4$. Starting and ending at A, find the shortest route that travels each road at least once.

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.