Prior content: None
Previous Section: Algorithms
Next Section: Algorithms on Graphs
Contents
- Whole Topic Notes
- 2A Modelling with Graphs
- 2B Graph Theory
- 2C Special Types of Graph
- 2D Representing Graphs and Networks Using Matrices
- 2E The Planarity Algorithm*
- Whole Topic Summary Resources (Including Past Paper Questions)
Whole Topic Notes
Full Notes to Accompany Examples
Dr Frost
- Dr Frost Decision 1 Graphs and Networks Section
- Dr Frost Decision 1 Graphs and Networks Slides
FMSP Whole Chapter Videos
- FMSP Decision 1 (AS) playlist (Courtesy of MEI)
2A Modelling with Graphs
Textbook resources
FMSP Video Courtesy of MEI
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
2B Graph Theory
Textbook resources
FMSP Video Courtesy of MEI
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
- 910e: State the degree/valency of a vertex in a graph or the sum of the degrees.
- 910f: Determine the number of edges in a graph given the degree of the graph's vertices.
- 910g: Determine whether a walk through a graph is a path, trial, cycle or Hamiltonian cycle.
- 910h: Determine if a subgraph of a graph is connected.
- 910i: Determine if a graph is simple.
- 910j: Use Euler's handshaking lemma to solve problems involving the degree of vertices in a graph.
- 910k: Determine if a graph is tree or a spanning tree.
- 910l: Find a spanning tree of a graph.
- 910m: Determine if two graphs are isomorphic.
- 913a: Understand terminology of digraphs, including arcs and loops.
- 913b: Identify the indegree or outdegree of a vertex.
- 913c: Identify sinks and sources in a directed graph and their associated indegrees and outdegrees.
- 910: Exam Practice: Graphs, connected graphs and the degree of vertices
- 913: Exam Practice: Directed graphs (digraphs)
2C Special Types of Graph
Textbook resources
No Video Yet
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
- 910c: Determine the complement of a graph.
- 911a: Draw a complete graph Kₙ
- 911b: Determine the number of edges in a complete graph Kₙ
- 911c: Draw a complete bipartite graph K(a,b)
- 911d: Determine the number of edges in a complete bipartite graph K(a,b)
- 911: Exam Practice: Complete and bipartite graphs
2D Representing Graphs and Networks Using Matrices
Textbook resources
No Video Yet
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
2E The Planarity Algorithm*
Textbook resources
FMSP Video Courtesy of MEI
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
- 917a: Understand the definition of a planar graph and determine if graphs are planar by observation.
- 917b: Use Euler's formula V + R = E + 2
- 917c: Use the planarity algorithm to determine whether a graph is planar.
- 917d: Understand subdivision of graphs, contraction of edges and when a graph is a minor of another.
- 917e: Use Kuratowski's theorem to determine if a graph is planar.
- 917f: Determine the thickness of a graph (with thickness up to 2).
- 917: Exam Practice: Planar graphs and testing for planarity
Whole Topic Summary Resources (Including Past Paper Questions)
External whole topic past paper style questions
- WW Dr Frost Style QQQs (Version 1) Word Doc, PDF (Q’s Only) or PDF (Q’s & Sol.)
- WW Dr Frost Style QQQs (Version 2) Word Doc, PDF (Q’s Only) or PDF (Q’s & Sol.)
Activities
- NRICH (student problems)