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

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

The only edges are A→B, B→C. Can a traveller go from C to A? Justify without adding edges.

The only edges are A → B and B → C.

Can a traveller go from C to A? Justify without adding edges.

Read it once, slowly. Then copy it onto your page.
  • What is going on? Two links, A → B and B → C. Each has an arrow: like a one-way street, you may only go the way it points.
  • What is fixed? The only edges: there are no others. Without adding edges: you may not invent a link to make the trip work.
  • What do they want? Yes or no: can you get from C to A? Then a reason, because they say justify.
Céim

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

Directed, Undirected, Connected & Disconnected Graphs

Arrow directions determine permitted travel, while connectivity describes which vertices are joined by paths.

Why it matters

Separating connectivity from directed reachability prevents you from assuming that a route can always be travelled in reverse.

The worked example

The only edges are A → B and B → C. Can a traveller go from C to A? Justify without adding edges.

How the worked example goes

  1. Read

    • What is going on? Two links, A → B and B → C. Each has an arrow: like a one-way street, you may only go the way it points.
    • What is fixed? The only edges: there are no others. Without adding edges: you may not invent a link to make the trip work.
    • What do they want? Yes or no: can you get from C to A? Then a reason, because they say justify.
  2. Understand

    • How do I picture it?
    • Two one-way streets: A to B, then B to C. You may drive with the arrows, never against them.
    • A graph whose edges have arrows is a directed graph. Each one-way edge is called an arc.
  3. Reduce

    • Every trip from C starts with one arc. So what do you look for first? An arc out of C: A trip from C must begin on an arc leaving C. If there is none, the trip cannot start.
    • Where do I start?
    • Stand at C. List every arc that points out of it. If the list is empty, no trip from C can begin, so none reaches A.
  4. Solve

    • List the arcs out of C.
    • Arcs out of C: none.
    • A → B points out of A, not out of C.
  5. Check

    • Is it right, and did I answer it?
    • Count the arcs at C: 1 in, 0 out. Forwards, A → B → C works, but that is the opposite trip ✓
    • Contrast: if both links were two-way, C → B → A would work. They are not.