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

Front: DEFINE
Define: 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: DEFINE
Define: 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: DEFINE
Define: 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 differencing final labels against edge weights.

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 = ?
Back: total weight + cheapest pairing of the odd nodes

Front: DEFINE
Define: minimum spanning tree.
Back: Connects all n nodes with n − 1 edges and no cycle, at least total weight. Prim grows from a node; Kruskal works down the sorted edges rejecting cycles. Both give the same total.

Front: SPOT THE ERROR
Say what is wrong with this claim:
The nearest neighbour algorithm gives the shortest tour.
Back: It gives a valid tour, and so an upper bound, but it never looks ahead. On the standard five-node network it returns 117 when the best tour is 109.

Front: DEFINE
Define: Eulerian and semi-Eulerian.
Back: No odd nodes means a closed trail exists using every edge once; exactly two odd nodes means such a trail exists but must start and end at them; more than two means neither.

Front: STANDARD RESULT — LEARN IT
Total float:
float = ?
Back: latest finish - earliest start - duration

Front: STANDARD RESULT — LEARN IT
Lower bound on workers:
least workers = ?
Back: 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: DEFINE
Define: 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.