Discrete Mathematics — OCR GCSE Further Mathematics Revision

    This subtopic introduces the fundamental categorisation of mathematical problems into existence, construction, enumeration, and optimisation. It also cover

    Topic Synopsis

    This subtopic introduces the fundamental categorisation of mathematical problems into existence, construction, enumeration, and optimisation. It also covers essential counting techniques, including set notation, partitions, the pigeonhole principle, and arrangement and selection problems, which serve as a foundation for Discrete Mathematics.

    Key Concepts & Core Principles

    Exam Tips & Revision Strategies

    Common Misconceptions & Mistakes to Avoid

    Examiner Marking Points

    Discrete Mathematics

    OCR
    GCSE

    This subtopic introduces the fundamental categorisation of mathematical problems into existence, construction, enumeration, and optimisation. It also covers essential counting techniques, including set notation, partitions, the pigeonhole principle, and arrangement and selection problems, which serve as a foundation for Discrete Mathematics.

    0
    Objectives
    39
    Exam Tips
    39
    Pitfalls
    0
    Key Terms
    52
    Mark Points

    Subtopics in this area

    Mathematical Preliminaries
    Graphs and Networks
    Algorithms
    Network Algorithms
    Decision Making in Project Management
    Graphical Linear Programming
    The Simplex Algorithm
    Game Theory

    Topic Overview

    Discrete Mathematics is a branch of mathematics dealing with objects that can assume only distinct, separated values. In the OCR GCSE Further Mathematics course, this topic introduces you to the mathematics of decision-making, counting, and optimisation. You'll explore concepts like graph theory, combinatorics, and algorithms, which are fundamental to computer science, operations research, and network analysis. Understanding discrete mathematics helps you solve real-world problems such as finding the shortest route, scheduling tasks, or counting possibilities efficiently.

    This topic is crucial because it bridges pure mathematics with practical applications. You'll learn to model situations using graphs, trees, and matrices, and apply systematic methods to solve problems. For example, you'll use Dijkstra's algorithm to find the shortest path in a network or apply the pigeonhole principle to prove existence results. Discrete mathematics also develops logical reasoning and algorithmic thinking, skills that are highly valued in STEM fields and beyond.

    In the OCR GCSE Further Mathematics syllabus, discrete mathematics appears in the Decision Mathematics component. It builds on basic algebra and logic, and connects to topics like matrices and probability. Mastering discrete mathematics not only prepares you for A-level Further Mathematics but also gives you a toolkit for tackling complex, real-world problems with confidence.

    Key Concepts

    Core ideas you must understand for this topic

    • →Graph theory: vertices, edges, adjacency matrices, and types of graphs (simple, complete, bipartite). Understand how to represent networks and traverse them using algorithms like Kruskal's and Prim's for minimum spanning trees.
    • →Combinatorics: counting principles including the multiplication rule, permutations, and combinations. Know when to use factorial notation and how to solve problems involving arrangements and selections.
    • →Algorithms: step-by-step procedures for solving problems, such as Dijkstra's algorithm for shortest paths, sorting algorithms (bubble sort, quick sort), and the use of flow charts and pseudocode.
    • →Pigeonhole principle: if n items are placed into m containers and n > m, then at least one container contains more than one item. This principle is used to prove existence in combinatorial problems.
    • →Critical path analysis: using activity networks to find the minimum project completion time, identify critical activities, and calculate floats. This is essential for project management.

    What You Need to Demonstrate

    Key skills and knowledge for this topic

    • Correct classification of problems into existence, construction, enumeration, or optimisation
    • Accurate use of set notation and partition counting
    • Correct application of the pigeonhole principle
    • Accurate use of the multiplicative principle for arrangements
    • Correct calculation of permutations (nPr) and combinations (nCr)
    • Correct handling of constraints in arrangement and selection problems
    • Accurate application of the inclusion-exclusion principle for two sets
    • Correct use of terminology: vertex (node), arc (edge), degree, adjacent, tree, simple, connected, simply connected.

    Marking Points

    Key points examiners look for in your answers

    • Correct classification of problems into existence, construction, enumeration, or optimisation
    • Accurate use of set notation and partition counting
    • Correct application of the pigeonhole principle
    • Accurate use of the multiplicative principle for arrangements
    • Correct calculation of permutations (nPr) and combinations (nCr)
    • Correct handling of constraints in arrangement and selection problems
    • Accurate application of the inclusion-exclusion principle for two sets
    • Correct use of terminology: vertex (node), arc (edge), degree, adjacent, tree, simple, connected, simply connected.
    • Correct identification of walks, trails, paths, cycles, and routes.
    • Correct use of notation for complete graphs (Kn) and complete bipartite graphs (Km,n).
    • Application of vertex degrees to determine if a graph is Eulerian, semi-Eulerian, or neither.
    • Correct construction of an isomorphism via reasoned argument or explicit labelling.
    • Correct application of Euler's formula (V + R = E + 2) for planar graphs.
    • Correct application of Kuratowski's theorem regarding planarity.
    • Correct use of adjacency matrices and weighted matrix representations.
    • Correct tracing of an algorithm through its steps.
    • Accurate calculation of run-time complexity based on problem size.
    • Correct identification of the order of an algorithm (e.g., O(n^k)).
    • Correct application of sorting algorithms (Bubble, Shuttle, Quick sort).
    • Correct application of packing algorithms (Next-fit, First-fit, First-fit decreasing, Full bin).
    • Correct interpretation of algorithm outputs.
    • Correct application of Dijkstra's algorithm to find the shortest path.
    • Correct application of Prim's or Kruskal's algorithm to find a minimum spanning tree.
    • Correct use of the nearest neighbour method for the Travelling Salesperson problem.
    • Correct identification of odd nodes and pairing for the Route Inspection problem.
    • Clear demonstration of the algorithm process rather than just the final answer.
    • Correct calculation of upper and lower bounds for the Travelling Salesperson problem.
    • Construction and interpretation of activity networks using activity on arc
    • Execution of forward pass to determine earliest start times
    • Execution of backward pass to determine latest finish times
    • Identification of critical activities and the critical path
    • Calculation and interpretation of total float
    • Calculation and interpretation of independent and interfering float (Stage 2)
    • Construction of cascade charts (Stage 2)
    • Determination of the effect of delays on project completion time (Stage 2)
    • Correct formulation of the objective function and all inequality constraints
    • Accurate plotting of constraint lines on a graph
    • Correct identification and shading of the feasible region
    • Correct evaluation of the objective function at the vertices of the feasible region
    • Correct identification of the optimal solution (maximum or minimum)
    • Correct handling of integer constraints where required
    • Correct formulation of the initial simplex tableau in standard format
    • Correct identification of the pivot column (most negative value in the objective row)
    • Correct identification of the pivot row (minimum non-negative ratio of RHS to pivot column)
    • Accurate performance of row operations to update the tableau
    • Correct interpretation of the tableau to identify basic and non-basic variables
    • Correct identification of the optimal solution when no negative entries remain in the objective row
    • Correct identification of zero-sum game structures and pay-off matrices.
    • Accurate application of dominance arguments to reduce matrix size.
    • Correct identification of stable solutions (saddle points) and Nash Equilibria.
    • Accurate formulation and solution of mixed strategy problems using simultaneous equations or graphical methods.
    • Correct reformulation of games into linear programming problems for simplex algorithm application.

    Examiner Tips

    Expert advice for maximising your marks

    • 💡Always check if the order of items matters before choosing between permutations and combinations
    • 💡For arrangement problems with restrictions, consider the 'gap method' or 'subtraction method' (total arrangements minus forbidden arrangements)
    • 💡When using the inclusion-exclusion principle, clearly define the sets involved
    • 💡Show clear working for counting problems to allow for method marks even if the final calculation is incorrect
    • 💡Use the notation nPr and nCr correctly as specified in the formulae booklet
    • 💡When asked to show two graphs are isomorphic, provide a clear mapping of vertices.
    • 💡Always check if a graph is simple before applying theorems like Ore's theorem.
    • 💡Use colouring arguments to test for bipartiteness.
    • 💡Be prepared to draw planar representations if a graph is planar.
    • 💡Ensure you can distinguish between the different types of graph traversals (Eulerian vs Hamiltonian).
    • 💡Use the provided Formulae Booklet for algorithm sketches and the hierarchy of orders.
    • 💡Show clear, step-by-step working when tracing algorithms to ensure method marks are awarded.
    • 💡Be prepared to adapt or alter a short set of instructions to create an algorithm.
    • 💡Remember that small-scale problems are used to demonstrate understanding of the process, not just rote application.
    • 💡If a question specifies an algorithm (e.g., Dijkstra's), you must use it; otherwise, inspection may be acceptable.
    • 💡Use the Formulae Booklet for algorithm sketches, but focus on understanding the process.
    • 💡Only use specific algorithms if instructed to do so; otherwise, inspection may be faster.
    • 💡Show detailed reasoning for algorithm steps to ensure full marks.
    • 💡Practice identifying the correct algorithm for the specific network problem type.
    • 💡Ensure clear communication of the algorithm's progress in small-scale problems.
    • 💡Focus on understanding the theory and processes rather than rote memorization of algorithms
    • 💡Use technology in the classroom to demonstrate large-scale problems, but be prepared to demonstrate understanding on small-scale problems in the exam
    • 💡Ensure clear labeling of nodes and arcs in activity networks
    • 💡Double-check the forward and backward pass calculations as errors here propagate through the entire analysis
    • 💡Always label axes and constraint lines clearly on your graph
    • 💡Use a ruler for all straight-line graphs
    • 💡Check the vertices of the feasible region carefully, as the optimal solution often lies at one of these points
    • 💡If integer solutions are required, ensure you test integer points near the optimal vertex if the vertex itself is not an integer coordinate
    • 💡Use technology (graphing software) during practice to investigate the effects of changing coefficients
    • 💡Ensure the tableau is set up correctly with objective row and constraint rows clearly distinguished
    • 💡Always show the ratio calculations when determining the pivot row
    • 💡Double-check arithmetic after each iteration as one error propagates through the entire tableau
    • 💡Clearly state the values of the variables and the objective function at the end of the process
    • 💡Use the provided Formulae Booklet for algorithm steps if needed, but focus on understanding the process
    • 💡Always check for a saddle point (stable solution) first before attempting more complex methods.
    • 💡Use dominance arguments to simplify the pay-off matrix as much as possible before solving.
    • 💡Clearly state the strategy being used (e.g., pure vs mixed) and the corresponding pay-off.
    • 💡When using graphical methods for mixed strategies, ensure the axes are clearly labeled with probabilities.
    • 💡Show all steps when reformulating a game into a linear programming problem.
    • 💡When solving graph theory problems, always label your vertices and edges clearly. Show all steps in algorithms like Dijkstra's or Prim's, as marks are awarded for method even if you make a small arithmetic error.
    • 💡In combinatorics, decide whether order matters before applying formulas. Write down whether it's a permutation or combination explicitly to avoid confusion. Use the multiplication principle for multi-stage tasks.
    • 💡For critical path analysis, double-check that you've correctly identified all dependencies and that the forward and backward passes are accurate. The critical path is the longest path through the network; any delay on it delays the whole project.

    Common Mistakes

    Pitfalls to avoid in your exam answers

    • Confusing permutations (order matters) with combinations (order does not matter)
    • Incorrectly applying the inclusion-exclusion principle by failing to subtract the intersection
    • Misinterpreting constraints in arrangement problems (e.g., items that cannot be next to each other)
    • Failing to account for identical items when calculating arrangements
    • Misapplying the pigeonhole principle by not correctly identifying the 'pigeons' and 'holes'
    • Confusing the definitions of walk, trail, path, and cycle.
    • Assuming that having the same degree sequence is sufficient to prove isomorphism.
    • Misapplying Ore's theorem by failing to check if the graph is simple or if the condition holds for all pairs of non-adjacent vertices.
    • Incorrectly identifying the number of arcs in complete or complete bipartite graphs.
    • Failing to correctly identify the number of odd-degree vertices when determining Eulerian properties.
    • Confusing the order of an algorithm with its actual run-time.
    • Incorrectly identifying the pivot in Quick sort when not specified.
    • Failing to follow the specific sorting or packing algorithm requested in the question.
    • Misinterpreting the hierarchy of orders (e.g., failing to recognize O(n log n) vs O(n^2)).
    • Errors in tracing algorithms due to lack of systematic recording.
    • Confusing the different network algorithms (e.g., using Prim's instead of Dijkstra's).
    • Failing to show the working steps of an algorithm when required.
    • Incorrectly identifying odd nodes in the Route Inspection problem.
    • Misinterpreting the requirements for upper and lower bounds in the Travelling Salesperson problem.
    • Errors in trace-back procedures for shortest paths.
    • Confusing earliest start times with earliest finish times
    • Miscalculating float by failing to correctly identify the critical path
    • Incorrectly applying the 'burst' and 'merge' terminology in network analysis
    • Failing to account for scheduling restrictions when constructing cascade charts
    • Incorrectly shading the feasible region (e.g., shading the wrong side of a constraint line)
    • Failing to include non-negativity constraints (x >= 0, y >= 0)
    • Misinterpreting the objective function (e.g., confusing maximisation with minimisation)
    • Failing to check all vertices of the feasible region for the optimal value
    • Incorrectly handling integer programming requirements
    • Incorrect choice of pivot column or row
    • Arithmetic errors during row operations
    • Failure to correctly identify the optimal solution from the final tableau
    • Misinterpreting the objective row values
    • Errors in setting up the initial tableau from the problem constraints
    • Confusing pure strategies with mixed strategies.
    • Incorrectly identifying or failing to identify a saddle point in a pay-off matrix.
    • Errors in setting up the linear programming formulation for mixed strategies.
    • Misinterpreting the Nash Equilibrium in the context of the game.
    • Failing to check for dominance before attempting more complex solution methods.
    • Misconception: 'A complete graph has an edge between every pair of vertices, so it must be a simple graph.' Correction: While complete graphs are simple, not all simple graphs are complete. A simple graph has no loops or multiple edges, but it may not have all possible edges.
    • Misconception: 'In permutations, order doesn't matter.' Correction: Permutations are about arrangements where order does matter. When order doesn't matter, we use combinations. For example, selecting a committee (order irrelevant) is a combination, while arranging books on a shelf (order relevant) is a permutation.
    • Misconception: 'Dijkstra's algorithm always finds the shortest path, even with negative weights.' Correction: Dijkstra's algorithm fails if there are negative weight edges. For graphs with negative weights, use the Bellman-Ford algorithm instead.

    Frequently Asked Questions

    Common questions students ask about this topic

    Before You Start

    Prior knowledge that will help with this topic

    • •Basic algebra: ability to manipulate equations and understand notation like factorials.
    • •Logical reasoning: understanding of if-then statements, and, or, not, and the ability to follow step-by-step instructions.
    • •Basic probability: familiarity with the concept of counting outcomes, which helps in combinatorics.

    Study Guide Available

    Comprehensive revision notes & examples

    Read Study Guide

    Likely Command Words

    How questions on this topic are typically asked

    Find
    Calculate
    Show
    Explain
    Determine
    Understand
    Use
    Construct
    Identify
    Model
    Solve
    Trace
    Compare
    Sort
    Interpret
    Demonstrate
    Formulate
    Discuss
    Reduce

    Ready to test yourself?

    Practice questions tailored to this topic

    Related Topics in OCR GCSE Further Mathematics

    Mechanics

    View Topic

    Statistics

    View Topic

    Pure Core

    View Topic

    Statistics

    View Topic