IB Mathematics Applications & Interpretation 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$.

Draw on this

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.