Title: InkMaths / Decision Mathematics 1: algorithms and networks
On every note of this deck, unless a note says otherwise:
Footer: Continue on InkMaths · © 2026 InkMaths. All rights reserved.

Front: RECALL
State the Simplex rules.
Back: Pivot on the most negative entry in the objective row, choosing the row by the smallest non-negative ratio of value to pivot-column entry. Stop when no negative entries remain.

Front: RECALL
State the bin packing lower bound.
Back: The total of the items divided by the bin size, rounded up. If an algorithm achieves it the packing is optimal; falling short proves nothing either way.

Front: DEFINE
Define: order of an algorithm.
Back: How the number of operations grows with the size n of the problem. An order n² algorithm takes four times as long on a list twice as long.

Front: RECALL
Explain how Prim and Kruskal differ.
Back: Prim grows one connected lump from a starting node, taking the cheapest edge out of what it already holds. Kruskal sorts every edge and works down the list, rejecting any edge that closes a cycle, so it builds separate fragments that join up late. Both reach the same total weight.

Front: RECALL
State Dijkstra's rule.
Back: Make permanent the smallest temporary label anywhere in the network, not the cheapest edge from where you are. Read the route back by starting at the destination and stepping to a neighbour whose label plus the edge weight equals the label you are on, repeating to the start. A matching edge on its own only says it lies on some shortest route to its higher-labelled end.

Front: CHECK YOURSELF
Why must the number of odd nodes in any graph be even?
Back: The orders total twice the number of edges, which is even. The even nodes contribute an even amount, so the odd ones must too, which needs an even number of them.

Front: STANDARD RESULT · LEARN IT
Route inspection:
shortest closed route = ?\(\text{shortest closed route} = ?\)shortest closed route = ?
Back: total weight + cheapest pairing of the odd nodes\(\text{total weight} + \text{cheapest pairing of the odd nodes}\)total weight + cheapest pairing of the odd nodes

Front: DEFINE
Define: minimum spanning tree.
Back: A set of edges joining all n nodes, using n − 1 edges and closing no cycle, of the least total weight any such set can have.

Front: SPOT THE ERROR
Say what is wrong with this claim:
The nearest neighbour algorithm gives the shortest tour.
Back: It gives one valid tour, so it gives an upper bound and nothing stronger. Taking the cheapest edge available at each step forces an expensive jump back to the start at the end. Run it from every vertex and quote the smallest result, and still call it an upper bound.

Front: DEFINE
Define: Eulerian and semi-Eulerian.
Back: In a connected graph, no odd nodes means a closed trail exists using every edge once. Exactly two odd nodes means such a trail exists but has to start at one of them and finish at the other. More than two means neither.

Front: STANDARD RESULT · LEARN IT
Total float:
float = ?\(\text{float} = ?\)float = ?
Back: latest finish - earliest start - duration\(\text{latest finish} - \text{earliest start} - \text{duration}\)latest finish - earliest start - duration

Front: STANDARD RESULT · LEARN IT
Lower bound on workers:
least workers = ?\(\text{least workers} = ?\)least workers = ?
Back: total work ÷ project duration, rounded up\(\text{total work} \div \text{project duration, rounded up}\)total work ÷ project duration, rounded up

Front: DEFINE
Define: slack, surplus and artificial.
Back: A ≤ constraint gains a slack variable; a ≥ constraint loses a surplus variable and then gains an artificial one so that a starting solution exists at all.

Front: RECALL
State the travelling salesman lower bound.
Back: Delete a node, find a minimum spanning tree on what is left, then add back the two shortest edges from the deleted node. Any tour at all gives an upper bound.

Front: DEFINE
Define: critical activity.
Back: One whose earliest and latest start times agree, so it has zero float. The critical activities form a continuous path whose durations total the project duration.