Decision mathematics: formulas
Pick a formula to see it explained with worked examples and a solver that shows every step.
About this topic
Decision maths helps you find the best way to do something, like the shortest route or the cheapest plan. On this page you will find 26 pages, such as Edges in a complete graph, Euler’s formula for planar graphs and polyhedra and Planar graph bounds.
On every page you get worked examples, the common slips to avoid and a solver that shows the working. A friendly first stop is Edges in a complete graph, or go back to Discrete maths and number theory.
Formulas in this topic
- Handshaking lemmaIn any graph, ∑vdeg(v)=2∣E∣: the degrees add up to twice the number of edges. So the number of vertices of…
- Edges in a complete graphThe complete graph Kn has every pair of its n vertices joined by an edge, so it has 2n(n−1) edges.
- Edges in a treeA tree is a connected graph with no cycles. A tree with V vertices has exactly E=V−1 edges.
- Euler’s formula for planar graphs and polyhedraFor a connected planar graph drawn without crossings, V−E+F=2, where V is the number of vertices, E the…
- Planar graph boundsA simple connected planar graph with V≥3 vertices has at most E≤3V−6 edges. If a graph has more, it cannot be…
- Critical path: floatIn a critical path analysis, the float of an activity is float=latest finish−earliest start−duration.…
- Route inspection (Chinese postman)The shortest route that travels along every edge of a connected network and returns to the start has length…
- Zero-sum game: optimal mixed strategy (2 × 2)For the payoff matrix (acbd) (the row player's winnings) with no saddle point, the row player plays row 1…
- Linear programming: optimum at a vertexIn linear programming, the maximum or minimum of P=ax+by over a feasible region bounded by straight lines…
- Travelling salesperson: boundsFor the travelling salesperson problem (the shortest tour visiting every city once and returning), the…
- Dijkstra relaxation stepIn Dijkstra's algorithm, relaxing an edge (u,v) of weight w updates the tentative distance:…
- Floyd–Warshall recurrenceThe Floyd–Warshall algorithm finds all-pairs shortest paths with the recurrence…
- Minimum spanning tree sizeA spanning tree of a connected graph with ∣V∣ vertices has exactly ∣V∣−1 edges. A minimum spanning tree (MST)…
- Euler circuit and trailA connected graph has an Euler circuit (a closed walk using every edge exactly once) if and only if every…
- Bin packing lower boundThe number of bins of capacity C needed for items of total size Σ is at least ⌈CΣ⌉. This lower bound is…
- Critical path: earliest and latest timesIn an activity network the earliest time of an event is Ej=maxi(Ei+dij) (forward pass) and the latest…
- Walks and the adjacency matrixIf A is the adjacency matrix of a graph, then (An)ij is the number of walks of length n from vertex i to…
- Complete bipartite graphThe complete bipartite graph Km,n has two parts of sizes m and n, with every vertex of one part joined to…
- Complement of a graphThe complement Gˉ of a graph G on n vertices has the same vertices and exactly the edges that G lacks, so…
- Planar graph bound (bipartite)A connected planar bipartite graph with V≥3 vertices has at most 2V−4 edges (compared with 3V−6 for planar…
- Kuratowski's theoremKuratowski's theorem: a graph is planar if and only if it contains no subdivision of K5 or K3,3 as a…
- Value of a cutA cut separates the source from the sink into sets S∋s and T∋t. Its value is the sum of the capacities of the…
- Game theory: play-safe strategiesIn a zero-sum game with payoff matrix aij to the row player, the row player's play-safe value is…
- Dominated strategiesIn a zero-sum game, row i is dominated by row k if akj≥aij for every column j: the row player never loses…
- Simplex tableau: reading the solutionIn a final simplex tableau, the basic variables take the values in the right-hand-side column, the non-basic…
- Decision maths: shortest path, critical path analysis and the simplex methodDecision maths solves practical optimisation problems on networks and with constraints. Each method follows a…
Decision mathematics questions
What is a network used for?
To model things like roads, pipes or computer links so you can find the best route.
What if I get stuck?
Read the worked examples on the page first, then try the solver with your own numbers and compare each step.