Step 4 of 7 · Worked example · TEACH

← Networks, Graphs & Matrices

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Higher Level · Applied Maths · Networks, Graphs & Matrices · Step 4

Follow the worked example and explain why each modelling and calculation step is valid.

An undirected simple graph on A,B,C has edges AB and BC. Construct its binary adjacency matrix in that order and check the sum of entries.

An undirected graph on A, B, C, with no loops or repeated edges, has edges A–B and B–C.

Construct its binary adjacency matrix M in that order. Check the sum of entries.

Read it once, slowly. Then copy it onto your page.
  • What is going on? Three vertices, A, B, C, and two edges, A–B and B–C. Undirected: each edge works both ways.
  • What does this rule out? No loops: no edge from a vertex back to itself. No repeated edges: at most one edge per pair.
  • What do they want? The binary adjacency matrix M, with rows and columns in the order A, B, C, and then the sum of all its entries.
Céim

Higher Level Applied Maths · Networks, Graphs & Matrices · Step 4 of 7

Building an Adjacency Matrix

A binary adjacency matrix records which pairs of vertices are connected, using a fixed row and column order.

Why it matters

Accurate matrix entries prevent direction errors and make degree checks straightforward in exam questions.

The worked example

An undirected graph on A, B, C, with no loops or repeated edges, has edges A–B and B–C. Construct its binary adjacency matrix M in that order. Check the sum of entries.

How the worked example goes

  1. Read

    • What is going on? Three vertices, A, B, C, and two edges, A–B and B–C. Undirected: each edge works both ways.
    • What does this rule out? No loops: no edge from a vertex back to itself. No repeated edges: at most one edge per pair.
    • What do they want? The binary adjacency matrix M, with rows and columns in the order A, B, C, and then the sum of all its entries.
  2. Understand

    • How do I picture it?
    • Sketch
    • A ─── B ─── C
  3. Reduce

    • Where do I start?
    • Fill one row per vertex: put a 1 under each of its neighbours, 0 everywhere else.
    • Then add every entry. Each edge gives two 1s, so expect 2 × 2 = 4 before you start.
  4. Solve

    • B is joined to A and to C. Write row B (columns A, B, C) on your page. Which is it? [1 0 1]: B to A is 1, B to B is 0 (no loop), B to C is 1.
    • Fill the rows.
    • Row A: joined to B only
  5. Check

    • Is it right?
    • Symmetric: row A, column B = row B, column A = 1, and the same for B and C. Diagonal all 0 ✓
    • Row sums 1, 2, 1 are the degrees of A, B, C from the sketch ✓