Networks — practice questions

A network has nodes P, Q, R, S and T. The arcs are $PQ$, $PR$, $QR$, $QS$, $RS$, $ST$. Write down the degree of each node and verify your answer with the handshake rule.

A courier depot D serves four drop-off points W, X, Y and Z. Travel is possible D–W (12 min), D–X (9 min), W–X (5 min), W–Y (14 min), X–Y (7 min), Y–Z (6 min) and X–Z (15 min). Draw the network, and explain what the model does and does not represent about the real road system.

Prove that every network must have an even number of odd-degree nodes, and use the result to explain why a network with exactly one odd node cannot exist.

A network has nodes P, Q, R, S, T with arcs $PQ = 7$, $PR = 9$, $QR = 4$, $QS = 6$, $RT = 8$, $ST = 5$, $RS = 11$. Use Kruskal's algorithm to find the minimum spanning tree and its total weight.

A ski field must run power to five huts. The possible cable runs, in hundreds of metres, are $AB = 12$, $AC = 15$, $BC = 9$, $BD = 14$, $CD = 14$, $CE = 20$, $DE = 11$. Cable costs $85 per metre. Find the cheapest way to power all five huts, and explain why one tie in the weights does not affect your answer.

A regional council has already built the link $CD$ (5 km) in the six-station network ($AB = 4$, $AC = 6$, $BC = 3$, $BD = 8$, $CD = 5$, $CE = 11$, $DE = 4$, $DF = 9$, $EF = 3$). It now asks: what is the cheapest way to connect all six stations given that $CD$ is already built, and would the answer change if instead the expensive arc $CE$ had already been built? Justify your reasoning in general terms.

Find the shortest path from P to T in a network with arcs $PQ = 5$, $PR = 2$, $QR = 1$, $QS = 6$, $RS = 8$, $ST = 3$, $RT = 12$. State the route and its length.

A courier drives from the depot D to customer Z. Travel times in minutes are $DW = 12$, $DX = 9$, $WX = 5$, $WY = 14$, $XY = 7$, $XZ = 15$, $YZ = 6$. Because of a one-way system the leg $XZ$ can only be driven from X to Z. Find the fastest route to Z, and advise the courier on the return trip.

In the pump-station network ($AB=4$, $AC=6$, $BC=3$, $BD=8$, $CD=5$, $CE=11$, $DE=4$, $DF=9$, $EF=3$) the shortest route from A to F is 18 km. Roadworks will slow one arc. Determine which single arc, if any, could be lengthened without changing the shortest distance, and by how much each arc on the route could be lengthened before the best route changes.

A network has degrees: P = 2, Q = 4, R = 3, S = 3, T = 2. State whether it is traversable, and where any journey must start and finish.

A rubbish truck must drive along every street in a suburb. The street network has nodes with degrees: depot D = 4, W = 3, X = 5, Y = 4, Z = 2, V = 2. Explain whether the round can be done without repeating a street, and advise the council.

A gritting network has six intersections with degrees 3, 3, 3, 3, 4 and 4, and every road is 2 km long. Determine the minimum distance the gritter must drive to cover every road, starting and finishing at the depot, which is one of the degree-4 intersections. Justify that no shorter journey exists.

For each situation, name which of the three network methods applies and give a one-sentence reason: (i) a power company connecting six new subdivisions to the grid for the least cable; (ii) a driver finding the quickest way from the airport to the stadium; (iii) a council checking every stretch of footpath in a park.

A network of five sites has arcs $AB = 6$, $AC = 3$, $BC = 4$, $BD = 7$, $CD = 5$, $CE = 9$, $DE = 2$. Find the minimum spanning tree and the shortest path from A to E, and explain why the two answers use different arcs.

A council will build a fibre network linking six sites using the minimum spanning tree ($AB=4$, $AC=6$, $BC=3$, $BD=8$, $CD=5$, $CE=11$, $DE=4$, $DF=9$, $EF=3$; MST total 19 km). The engineers argue that a tree is too fragile and want the network to survive any single cable break. Determine the cheapest network that meets that requirement, and evaluate whether the council should pay for it.