What is Discrete Mathematics?

Unlike continuous mathematics (like calculus), which deals with smooth, unbroken values, discrete mathematics focuses on countable, distinct values. This makes it ideal for computer science, logistics, and modelling systems with a finite number of states.

The Role of Your CAS Calculator

Throughout this unit, your CAS is an indispensable tool. It’s not just for calculations; it’s for efficient problem-solving. Mastering matrix storage, inverse calculations, and recursive functions will save valuable time and reduce errors in assessments.

Order & Elements

The order (or dimension) of a matrix is its size, given as rows × columns. An individual number inside is an element, identified by its position, a_ij (element in row i, column j).

Types of Matrices

Basic Arithmetic

• Addition/Subtraction: Matrices must have the same order. Add or subtract corresponding elements.
• Scalar Multiplication: Multiply every element in the matrix by a single number (a scalar).

Matrix Multiplication

To multiply matrix A by B (A × B), the number of columns in A must equal the rows in B. The result’s order is (rows of A) x (columns of B). Remember, this operation is not commutative (A × B ≠ B × A).

The Determinant & Inverse

An inverse, A^-1, only exists for a square matrix if its determinant (det(A)) is not zero. For a 2×2 matrix, det(A) = ad - bc. If det(A) = 0, the matrix is singular. The inverse is used to solve matrix equations like AX = B, where X = A-1B.

Constructing the Model

• Transition Matrix (T): A square matrix where columns represent ‘From’ and rows represent ‘To’. Each column must sum to 1.
• State Matrix (S): A column matrix showing the number/proportion in each state at a point in time. S₀ is the initial state.

Predicting Future States

To find the state after ‘n’ periods, the rule is Sn = Tn × S0. This is efficient for long-term predictions. For step-by-step changes, use the recurrence relation Sn+1 = T × Sn.

Steady State & Culling

In many systems, after a large number of transitions, the state matrix approaches a steady state where proportions no longer change. This is found by calculating TⁿS₀ for a large n. Models can also include external additions or removals (culling) with a matrix B, making the rule Sn+1 = T × Sn + B, which must be solved iteratively.

Core Components & Types

• Vertex (Node) & Edge (Arc): A point and the line connecting it to another.
• Degree of a Vertex: The number of edges connected to it.
• Weighted Graph: A graph where each edge has a numerical value (e.g., distance, cost).
• Directed Graph (Digraph): A graph where edges have a direction, shown by an arrow.
• Planar Graph: A graph that can be drawn with no edges crossing. For these, Euler’s formula holds: v - e + f = 2.

Paths, Trails & Circuits

The way you travel through a network matters. A path repeats no vertices or edges. A trail can repeat vertices but not edges. A circuit is a closed trail (starts and ends at the same vertex).

Minimum Spanning Trees: Prim’s Algorithm

Used for **minimum connector** problems (e.g., connecting houses with minimum cable). It finds the set of edges with the lowest total weight that connects all vertices without forming a cycle.

Shortest Path: Dijkstra’s Algorithm

Used to find the path of least total weight between a specific **start and end vertex**. It works by systematically finding the ‘cheapest’ vertex to visit next from the start point.

Allocation: The Hungarian Algorithm

Used for **assignment problems** (e.g., assigning workers to tasks for minimum total cost). It uses row and column reduction on a cost matrix to find the optimal one-to-one assignment.

Scheduling: Critical Path Analysis (CPA)

Used for **project management**. It determines a project’s minimum completion time by finding the **critical path** – the sequence of tasks with zero float (slack) time. Any delay on this path delays the entire project.

Algorithm Identification

This is the most critical skill. Before starting, ask: “What is the fundamental goal? Connection, shortest path, allocation, or scheduling?” Applying the wrong algorithm is a common and costly error.

Procedural Accuracy

The algorithms are step-by-step processes. A single arithmetic mistake or a missed step (like not updating a label in Dijkstra’s) can invalidate all subsequent work. Be meticulous.

Master Your CAS

Your CAS calculator is an essential tool for speed and accuracy. Use it for arithmetic, but ensure you understand the concepts. Practice storing matrices and using the recursive `Ans` function for iterative problems like culling/restocking.