Step 7 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 7

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

A directed multigraph has 2 edges from A to B, 4 from B to D, 3 from A to C and 6 from C to D, and no other edges. Parallel edges count as distinct choices. How many two-edge walks go from A to D?

A directed multigraph has 2 edges from A to B, 4 from B to D, 3 from A to C and 6 from C to D, and no other edges. Parallel edges count as distinct choices.

How many two-edge walks go from A to D?

Read it once, slowly. Then copy it onto your page.
  • What is going on? One-way roads, because the graph is directed. 2 roads A to B, 4 B to D, 3 A to C, 6 C to D.
  • What is fixed? No other edges: nothing else to use. Parallel edges are distinct: two roads from A to B are two different choices.
  • What do they want? A count: how many trips go from A to D using exactly two edges. A trip along edges is a walk.
Céim

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

Interpreting Matrix Products & Multiple Representations

An entry of an adjacency matrix power counts walks of that length between the corresponding vertices.

Why it matters

In an exam, interpreting matrix entries prevents you from confusing direct edges, walks and simple paths.

The worked example

A directed multigraph has 2 edges from A to B, 4 from B to D, 3 from A to C and 6 from C to D, and no other edges. Parallel edges count as distinct choices. How many two-edge walks go from A to D?

How the worked example goes

  1. Read

    • What is going on? One-way roads, because the graph is directed. 2 roads A to B, 4 B to D, 3 A to C, 6 C to D.
    • What is fixed? No other edges: nothing else to use. Parallel edges are distinct: two roads from A to B are two different choices.
    • What do they want? A count: how many trips go from A to D using exactly two edges. A trip along edges is a walk.
  2. Understand

    • How do I picture it?
    • Top route
    • A ─(2 roads)→ B ─(4 roads)→ D
  3. Reduce

    • Which expression counts the two-edge walks from A to D? 2 × 4 + 3 × 6: Multiply within each middle stop, then add the two stops, which share no walk.
    • Where do I start?
    • Call the count N. Then N = 2 × 4 + 3 × 6.
  4. Solve

    • Count each branch, then add.
    • Through B
    • 2 × 4 = 8
  5. Check

    • Is it right?
    • Count from the other end, by the last road.
    • B → D: 4 roads, 2 before each