Skip to main content
CSP LabBy Educator Today
AP CSP course

C55 · Topic 4.2 · 40 minutes · CSN-1.E

Redundant paths

By the end you can:

  • Find valid paths in an undirected graph.
  • Identify a single point of failure.
  • Explain how redundancy supports connectivity.

Before this lesson: topics 4.1.

Redundancy
Additional components or paths that can preserve a function when some fail.
Fault tolerance
A system’s ability to continue specified operation despite some failures.

Understand

A route in a supplied network must use actual links between consecutive devices. In an undirected graph a link can be travelled in either direction. Alternative routes provide redundancy: communication may continue if one link fails, provided a complete working path still connects source and destination.

Redundancy is about the specified failures a system can tolerate, not a guarantee that every component works or that no outage is possible. An endpoint with no working connection is isolated even if many links elsewhere remain. State the graph and failure model before making a resilience claim.

Worked example

Undirected links are S-A,S-B,A-C,B-C,C-T,A-D,D-T.

  1. S-A-C-T and S-A-D-Tare both valid simple routes.
  2. S-B-C-A-D-T is also valid because C-A is a permitted reverse traversal of A-C.
  3. S-D-T is invalid because the graph contains no S-D link.

Explore each concept

Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.

  • Redundancy and resource cost
  • Single-link versus multiple failures
  • Endpoint isolation
Open this example on its own

Change it · step through · explain

Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.

Ready · Make a prediction

Ready to explore: Test every single failure and combined failures
  1. Failure testeach-single-linkWaiting
  2. Add direct S-T linknoWaiting

Ready to explore: Test every single failure and combined failures

Why: Change an input, predict the first effect, then advance one step.

Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.

Step through and experiment

Change it · step through · explain

Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.

Ready · Make a prediction

Ready to experiment
  1. Input 1C-TWaiting
  2. Input 2(empty)Waiting

Ready to experiment

Why: Predict the first change, then advance one step.

Try this: Fail C-T, then also D-T. Add a link and predict whether it reconnects S to T.

Check a misconception

Claim: A link written A-C can never be used from C to A in an undirected graph.

The written order does not impose a direction on an undirected link.

Guided practice

Give all simple routes from S to Tin the original graph.

Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.

Independent transfer

Remove C-T and list every surviving simple path.

Exit check

Why does an extra B-T link not repair failure of both S-A and S-B?

Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.

Check yourself

  1. Question 1 of 2Which route is valid in the supplied graph?

    Select one answer.

  2. Question 2 of 2Which TWO statements describe redundancy correctly?

    Select exactly two answers (0 of 2 selected).

Your practice so far

Check an answer to see its rationale.

Teacher guidance and scoring