Micro-questions over the paths and connectivity module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Routes
1. What is a route?
Answer
Any sequence of vertices where each one is joined to the next by an edge.
2. What is a walk?
Answer
The most general route — step along edges to neighbours, revisiting any vertex and reusing any edge you like. Every route is a walk.
3. What is a trail?
Answer
A walk that may not reuse an edge. You may still revisit a vertex, as long as you arrive by a road you have not driven before.
4. What is a path?
Answer
A walk that may not revisit a vertex. Since you never return to a vertex you can never reuse an edge either, so every path is also a trail.
5. What is a simple path?
Answer
Exactly the same thing as a path. “Simple” is added for emphasis, because some books use “path” loosely.
6. State the containment relationship between the three.
Answer
Every path is a trail, and every trail is a walk. The reverse is not true — a walk is usually not a path.
7. Why is the word “path” dangerous when reading textbooks?
Answer
Books disagree. Some use path to mean a walk and simple path for no repeated vertices. This course uses path = no repeated vertices, which is what algorithms literature almost always means. The one word that is never ambiguous is “walk”.
B. Closed routes
8. What makes a route closed?
Answer
It ends at the vertex it started from.
9. What is a closed walk?
Answer
A walk that ends where it started, with nothing else restricted — vertices and edges may be reused freely.
10. What is a circuit?
Answer
A closed trail: a closed walk that does not reuse an edge. You may pass through the same vertex twice, as long as you never drive the same road twice.
11. What is a cycle?
Answer
A closed route that does not revisit any vertex, apart from the start, which is also the finish. Also called a simple cycle.
12. How many vertices does a cycle need in a simple graph, and why?
Answer
At least three. With two you would have to drive back along the single joining edge, which makes it a walk rather than a cycle.
13. What lengths of cycle exist in a non-simple graph?
Answer
A self-loop is a cycle of length 1; a pair of parallel edges makes one of length 2. Which is one more reason algorithms usually ask for a simple graph.
14. How is length counted?
Answer
In edges, not vertices. A route through four vertices has length 3. Off-by-one mistakes here are extremely common.
15. What extra condition do directed paths and cycles carry?
Answer
Every edge must be followed in the direction it points.
16. Can a directed graph contain a cycle when you ignore the arrows but no directed cycle?
Answer
Yes, easily — e.g. , , . Undirected it is a triangle; directed it has no cycle at all.
C. Connectivity, undirected
17. When is an undirected graph connected?
Answer
When you can get from any vertex to any other by some path.
18. What is a connected component, and what does “maximal” mean here?
Answer
A maximal group of vertices that can all reach each other. Maximal means you cannot add another vertex without breaking that property.
19. What guarantee do components give about coverage?
Answer
Every vertex belongs to exactly one component, so the components split the graph completely — nothing left over, nothing counted twice.
20. How do you find the components, and at what cost?
Answer
One BFS or DFS started from each vertex you have not yet visited. altogether.
D. Connectivity, directed
21. What is strongly connected?
Answer
For every pair there is a directed path from to and one back from to . Everywhere reaches everywhere, following the arrows.
22. What is weakly connected?
Answer
The graph is connected once you rub out all the arrows and treat every edge as two-way. A much weaker promise.
23. What is an SCC?
Answer
A strongly connected component — a maximal group of vertices that can all reach each other following the arrows. The directed version of a connected component.
24. Which implies which?
Answer
Strong always implies weak. The reverse fails constantly.
25. Give the real-world illustration of weak-but-not-strong.
Answer
A one-way street system can look perfectly joined up on a map — weakly connected — while some junction cannot actually be left once you drive into it. That is a strong-connectivity failure and a real problem for anyone using it.
26. What is condensing a directed graph, and what does it always produce?
Answer
Collapsing each SCC down to a single point. It always produces a DAG.
27. Why is that genuinely useful?
Answer
Any tangle of circular dependencies becomes acyclic once each mutually-dependent group is treated as one unit — which is how a build tool reports “these five packages form a cycle” instead of looping forever.
E. DAGs
28. What is a DAG?
Answer
A directed acyclic graph — a directed graph with no directed cycle anywhere. Follow the arrows as long as you like and you never arrive back where you started.
29. What are DAGs the shape of? Give five examples.
Answer
Dependency: build targets, task schedules, spreadsheet formulas, course prerequisites, git commits.
30. What can a DAG — and only a DAG — be given?
Answer
A topological order: a straight-line arrangement where every edge points forwards.
31. Why does a directed cycle make topological order impossible?
Answer
Each vertex on the cycle would have to come before itself.
F. The prediction drill
32. Take the triangle and reverse one edge, giving , , . Is it strongly connected?
Answer
No. has out-degree 0 — once you reach it you cannot leave, so cannot reach or .
33. Is it weakly connected?
Answer
Yes. Rub out the arrows and it is a triangle, which is connected.
34. Is it a DAG?
Answer
Yes. There is no way to follow the arrows back to a starting vertex — is a source and is a sink.
35. Summarise the lesson in one sentence.
Answer
Three levels of strictness for routes (walk ⊃ trail ⊃ path), the same three closed (closed walk ⊃ circuit ⊃ cycle), and two different meanings of “connected” the moment edges get arrows.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Paths, Cycles and Connectivity — the module
- What a Graph Is — Question Bank — the previous bank
- Topological Sort — where DAGs are put to work
Software engineering
Infrastructure & security
Computer science
Hardware & engineering