7.04e, 7.04f - Route inspection and choosing algorithms | OCR A-Level Further Mathematics A

Plan a shortest inspection journey that covers every road, including necessary repetitions. You will pair odd vertices, compare all pairings of up to six odd vertices, count those pairings, adapt the endpoints, and choose an algorithm from the practical objective.

Closing an inspection route

An inspector must cover every road and return to the depot. Is it enough to repeat the road joining the two nearest odd junctions? With four or six odd junctions, that locally cheap choice can leave an expensive problem behind. The whole pairing matters.

You already know

A connected undirected graph has an Eulerian circuit exactly when every vertex has even degree. With exactly two odd vertices, it has an Eulerian trail starting at one and finishing at the other. Traversing an edge again can be modelled by adding a parallel copy.

The road-inspection model here is a connected undirected network with non-negative weights. Every edge must be traversed at least once; vertices and edges may be revisited. If every degree is even, an Eulerian circuit uses every edge exactly once, so the original total weight is already the minimum closed inspection weight.

Repeating a path changes the parity of its endpoints. Every internal vertex gains two incidences and keeps its parity. Consequently, pairing the odd vertices and duplicating the paths between each pair makes every degree even.

Closed route inspection

Let $W$ be the sum of all original edge weights. Find shortest-path distances between the odd vertices, and choose a complete pairing of those vertices with minimum total distance $P$ . Then

\text{minimum closed inspection weight}=W+P

If there are no odd vertices, $P=0$ . Each original edge contributes to $W$ once, however many times the final route uses it.
In the formula booklet.

Shortest connecting paths are essential: a direct edge may cost more than an indirect journey, and a pair need not be directly connected. Dijkstra supplies the distances if they are not obvious.

Why does the least pairing give an optimum, rather than just one possible route? In any closed inspection, the extra traversals must correct the original odd degrees. Those extra edges can be separated into paths pairing the odd vertices, together with possible closed circuits. Non-negative circuits cannot reduce the cost, and each connecting path costs at least its shortest-path distance. Thus no closed inspection can beat the least pairing total; duplicating the selected shortest paths attains it.

Worked example 1: two odd vertices

Question. Roads form triangle $ABC$ , with $AB=3$ , $BC=4$ , $CA=5$ , and a tail $C-D-E$ , with $CD=2$ , $DE=3$ . Find the minimum inspection weight, starting and finishing at $A$ .

Plan. Find odd vertices, duplicate a shortest path between them, then add its weight to the original total.

\begin{aligned} W&=3+4+5+2+3=17 &&\text{count each original edge once}\\ \deg(C)=3,\quad\deg(E)&=1 &&\text{only odd vertices}\\ d(C,E)&=2+3=5 &&\text{shortest path }C-D-E\\ W+P&=17+5=22 &&\text{make both odd degrees even} \end{aligned}

Why this step? Starting at $A$ does not make $A$ an odd vertex; a closed route must have even degree everywhere.

Answer. Minimum weight $22$ , duplicating $CD$ and $DE$ .

Check. The route $A-B-C-D-E-D-C-A$ uses every road and has weight $3+4+2+3+3+2+5=22$ .

Change only the length of $DE$ . It appears once in the original total and once in the duplicated path.

Worked example 2: a longer bridge

Question. In example 1, $DE$ has weight $6$ instead of $3$ . Find the new minimum closed inspection weight.

Plan. Recalculate both the original total and the shortest path between the unchanged odd vertices.

\begin{aligned} W&=3+4+5+2+6=20 &&\text{new original total}\\ P=d(C,E)&=2+6=8 &&\text{only odd pairing}\\ W+P&=20+8=28 &&\text{closed inspection minimum} \end{aligned}

Why this step? The tail is a dead end, so each of its roads must be used in both directions on a closed inspection journey.

Answer. $28$ .

Check. Increasing the tail edge by $3$ increases the closed journey by $6$ , because that edge is traversed twice.

With two odd vertices there is only one pairing, but you must still use a shortest path between them.

Four odd vertices

Four odd vertices have three complete pairings. Compare all three sums before choosing what to repeat.

[DIAGRAM: asset_name: Four odd junctions; asset_slug: h245_7_04_four_odd; caption: Every vertex has odd degree; repeating AB and CD gives the least additional weight 6; description: Complete undirected network A B C D with AB 3 AC 4 AD 8 BC 2 BD 5 CD 3. Highlight the repeated pairing AB and CD as parallel dashed arcs. Show pairing totals AB plus CD equals 6, AC plus BD equals 9, AD plus BC equals 9, where shortest AD distance is 7 through C.]
Every vertex has odd degree

For odd vertices $A,B,C,D$ , once $A$ 's partner is chosen, the other pair is forced. The possibilities are $(AB,CD)$ , $(AC,BD)$ , $(AD,BC)$ . Pair costs refer to shortest paths, not necessarily individual edges.

Worked example 3: comparing all pairings

Question. Find the minimum closed inspection weight for the pictured network.

Plan. Calculate its original weight, find the six pair distances, then compare the three pairing totals.

W=3+4+8+2+5+3=25 \qquad\text{sum original edges}

Every vertex has degree $3$ . The shortest distances are

d_{AB}=3,\ d_{AC}=4,\ d_{AD}=7,\ d_{BC}=2,\ d_{BD}=5,\ d_{CD}=3

Here $d_{AD}=4+3=7$ through $C$ , shorter than the direct edge of weight $8$ .

Pairing	Additional weight
$AB,CD$	$3+3=6$
$AC,BD$	$4+5=9$
$AD,BC$	$7+2=9$

Why this step? The individually cheapest pair $BC$ leaves the expensive pair $AD$ ; its combined cost $9$ loses to $6$ .

Answer. Duplicate $AB$ and $CD$ . Minimum weight $25+6=31$ .

Check. Each vertex receives one extra incidence, changing its degree from $3$ to $4$ ; the connected augmented network is Eulerian.

Change only $AD$ from $8$ to $1$ . Recalculate shortest paths before comparing the same three pairings.

Worked example 4: an indirect distance changes

Question. Find the minimum closed inspection weight after this change.

Plan. Update the original total and all affected pair distances.

\begin{aligned} W&=25-8+1=18 &&\text{changed original edge}\\ d_{AD}&=1 &&\text{new direct minimum}\\ d_{BD}&=3+1=4 &&\text{now shorter through }A \end{aligned}

The other pair distances stay $3,4,2,3$ for $AB,AC,BC,CD$ .

\begin{aligned} AB+CD&=3+3=6 &&\text{first pairing}\\ AC+BD&=4+4=8 &&\text{second pairing}\\ AD+BC&=1+2=3 &&\text{third pairing, least}\\ W+P&=18+3=21 &&\text{add the least duplication} \end{aligned}

Why this step? Changing one road can improve another pair's shortest distance, such as $B-D$ , even though that pair's direct road did not change.

Answer. Duplicate $AD$ and $BC$ , giving minimum weight $21$ .

Check. All four odd degrees become even and $1+2$ is the least complete pairing sum.

The opening question now has a counterexample: in example 3, greedily taking $BC=2$ is worse than pairing $AB$ and $CD$ .

Watch out

Wrong: pair the closest two odd vertices, then accept whatever remains. Right: minimise the sum over a complete pairing of all odd vertices.

Find shortest pair distances before using the three-case comparison.

Six odd vertices

With six odd vertices, organise the fifteen pairings so that none is missed or counted twice.

[DIAGRAM: asset_name: Six odd junctions; asset_slug: h245_7_04_six_odd; caption: The nine original roads have total weight 36; all six junctions have degree 3; description: Hexagonal undirected network A B C D E F with cycle edges AB 2 BC 3 CD 4 DE 3 EF 2 FA 4 and chords AD 7 BE 6 CF 5. Highlight optimal duplicated edges AB CD EF, total 8. Place chord labels apart from crossings, and label crossings as having no junction.]
The nine original roads have total weight 36

Fix $A$ 's partner in turn as $B,C,D,E,F$ . For each choice, the remaining four vertices have exactly the three pairings from part 2. That makes five groups of three, rather than an unstructured search.

Worked example 5: all fifteen cases

Question. Find the minimum closed inspection weight for the six-junction network in the diagram.

Plan. Use shortest-path distances, then compare the fifteen complete pairings grouped by $A$ 's partner.

The original total is

W=2+3+4+3+2+4+7+6+5=36

Every vertex has degree $3$ . The shortest distances are:

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	$2$	$5$	$7$	$6$	$4$
$B$	$2$	–	$3$	$7$	$6$	$6$
$C$	$5$	$3$	–	$4$	$7$	$5$
$D$	$7$	$7$	$4$	–	$3$	$5$
$E$	$6$	$6$	$7$	$3$	–	$2$
$F$	$4$	$6$	$5$	$5$	$2$	–

For example, $d(A,E)=4+2=6$ through $F$ , and $d(B,F)=2+4=6$ through $A$ .

Pairing	Cost	Pairing	Cost	Pairing	Cost
$AB,CD,EF$	$8$	$AB,CE,DF$	$14$	$AB,CF,DE$	$10$
$AC,BD,EF$	$14$	$AC,BE,DF$	$16$	$AC,BF,DE$	$14$
$AD,BC,EF$	$12$	$AD,BE,CF$	$18$	$AD,BF,CE$	$20$
$AE,BC,DF$	$14$	$AE,BD,CF$	$18$	$AE,BF,CD$	$16$
$AF,BC,DE$	$10$	$AF,BD,CE$	$18$	$AF,BE,CD$	$14$

P=2+4+2=8,\qquad W+P=36+8=44

Why this step? Each row fixes $A$ 's partner and exhausts the three possibilities left, so every complete pairing is considered exactly once.

Answer. Duplicate $AB,CD,EF$ , giving minimum closed weight $44$ .

Check. Each of the six vertices gains one incidence. The augmented connected network has all even degrees.

Change only $CF$ from $5$ to $1$ . Its effect is not limited to pairings explicitly containing $CF$ : shortest distances such as $CE$ and $BF$ also change.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	$2$	$5$	$7$	$6$	$4$
$B$	$2$	–	$3$	$7$	$6$	$6$
$C$	$5$	$3$	–	$4$	$7$	$5$
$D$	$7$	$7$	$4$	–	$3$	$5$
$E$	$6$	$6$	$7$	$3$	–	$2$
$F$	$4$	$6$	$5$	$5$	$2$	–

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	$2$	$5$	$7$	$6$	$4$
$B$	$2$	–	$3$	$7$	$6$	$6$
$C$	$5$	$3$	–	$4$	$7$	$5$
$D$	$7$	$7$	$4$	–	$3$	$5$
$E$	$6$	$6$	$7$	$3$	–	$2$
$F$	$4$	$6$	$5$	$5$	$2$	–

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.04e, 7.04f - Route inspection and choosing algorithms

Closing an inspection route

Four odd vertices

Six odd vertices

Continue this lesson.

Learn faster with Nova

	$A$	$B$	$C$	$D$	$E$	$F$
$A$	–	$2$	$5$	$7$	$6$	$4$
$B$	$2$	–	$3$	$7$	$6$	$6$
$C$	$5$	$3$	–	$4$	$7$	$5$
$D$	$7$	$7$	$4$	–	$3$	$5$
$E$	$6$	$6$	$7$	$3$	–	$2$
$F$	$4$	$6$	$5$	$5$	$2$	–