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.Ordinary 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: no arrows, so 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 between any two vertices.
  • What do they want? The binary adjacency matrix M, rows and columns in the order A, B, C. Then the sum of all its entries.
Céim

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

Building an Adjacency Matrix

A binary adjacency matrix records each connection as a 1 and each absence of a connection as a 0 in a fixed vertex order.

Why it matters

This representation lets you count connections and check directions using rows and columns.

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: no arrows, so 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 between any two vertices.
    • What do they want? The binary adjacency matrix M, rows and columns in the order A, B, C. Then the sum of all its entries.
  2. Understand

    • How do I picture it?
    • Draw A, B, C in a row: A joined to B, B joined to C.
    • Count the neighbours: A has 1, B has 2, C has 1. The number of edges at a vertex is its degree.
  3. Reduce

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

    • Fill row A.
    • Columns A, B, C
    • Row A: joined to B only
  5. Check

    • Is it right, and did I answer it?
    • Mirror check: 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 picture. And 4 ÷ 2 = 2 edges ✓