DB5 - Refining network models
A network answer is only as useful as the assumptions behind its nodes, arcs and weights. You will translate a practical objective into weights, identify missing restrictions and refine a model when costs or available links change. Earlier spanning-tree and route methods will let you assess which results remain valid and which need recalculating.
Translating context into weights
If a survey bans a possible cable that the cheapest network never used, must the minimum installation cost change? We will answer this after deciding what the model actually measures.
A node may represent a building, road junction or destination. An arc must represent an available connection or journey. Its weight must measure the objective: cable length for minimum cable, money for minimum expenditure, journey time for minimum travel time. Use consistent units, and decide whether the total really is the sum of the arc weights.
For example, adding installation times gives elapsed completion time if one crew installs links one at a time. With several crews working in parallel, elapsed time does not usually equal the sum. Similarly a charge paid once for the whole job belongs outside the sum; a charge paid for every selected arc belongs in that arc's weight.
Worked example 1: a common installation rate
Question. Three buildings have possible cable lengths AB 2, AC 3, BC 4 kilometres. All links are feasible. Installation costs £1000 per kilometre, with a £600 fee for the whole project. Find the minimum installation cost for basic connection.
Plan. Minimise total cable length, multiply by the common positive rate, then add the project fee once.
The three possible spanning trees have lengths , , kilometres. Choose AB and AC. Every solution pays the same £600, so it cannot change which tree is best.
Answer. .
Check. The other two costs are £6600 and £7600, both greater. The chosen two arcs connect all three nodes.
Change only the common rate. This scales all cable costs equally and therefore preserves the selected tree.
Worked example 2: a revised common rate
Question. The cable lengths are still AB 2, AC 3, BC 4 kilometres and the project fee is still £600, but the common rate becomes £1500 per kilometre. Find the new minimum cost.
Plan. Keep the minimum-length tree because multiplication by a positive common rate preserves comparisons.
AB and AC still total 5 kilometres. The new cost is .
Answer. £8100, using AB and AC.
Check. The two rejected tree costs are and , so the decision is unchanged.
The algebra explains the connection: if every feasible solution has cost , where and is constant, minimising that cost is equivalent to minimising . Edge-specific rates or discounts need new comparisons instead.
Watch out
Wrong: “Add the £600 project fee to every arc.” That charges it repeatedly. State whether a cost is paid per kilometre, per selected link or once per project before calculating.
Apply the same distinction with new lengths and costs.
Symmetry, costs and practical restrictions
An undirected arc with one weight assumes that travel or connection is possible both ways with the same relevant cost. That can suit cable length, but not necessarily journey time uphill and downhill. Use directed arcs and separate weights for unequal directions; a directed journey model cannot automatically use the undirected route-inspection parity rule or MST method as a route solver.
[DIAGRAM: asset_name: Direction-dependent journey times; asset_slug: aqa7367-network-directions; caption: Travelling from A to B takes 4 minutes, while the return takes 7 minutes; description: Nodes A and B have two separately drawn directed arcs. The upper arc points from A to B and is labelled 4 minutes. The lower arc points from B to A and is labelled 7 minutes. A note says that a single undirected weight cannot describe both times.]
For the same geometrical connection, distance might be symmetric while travel time is not. The objective controls which information matters. A model using distance cannot claim to minimise time without a justified relationship between them.
Evaluating a model
To evaluate a network model, identify an assumption, explain how the context may violate it, and state the effect on feasibility or on the objective. To refine it, change the relevant arcs, weights or restrictions and then check the resulting solution.
Consider the triangle AB 2, AC 3, BC 4 kilometres. With a common rate, AB and AC minimise cost. If costs per kilometre are £2000 on AB, £1000 on AC and £500 on BC, the monetary weights become £4000, £3000, £2000. The minimum-cost tree is now AC and BC, costing £5000, even though its length is 7 kilometres rather than 5. The old shortest-length tree costs £7000. This is why “shortest” and “cheapest” need separate weights when rates vary.
Other missing restrictions can change feasibility. A link crossing prohibited land should be deleted, not assigned a small ordinary weight. Requiring backup routes excludes every tree. A maximum time between two destinations is a route condition, not merely a condition on the sum of all selected cables. A capacity limit also needs information beyond connection alone; do not assume an MST verifies it.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account