In a directed graph modeling web hyperlinks, page A links to page B, and page B links to page C. Can page C reach page A by following links?
AYes — since A, B, and C are all connected, the graph is connected and any page can reach any other
BNot necessarily — directed edges are one-way, and reachability from C to A depends on whether a directed path back to A exists
CYes — in any connected graph, every vertex can reach every other vertex
DNo — once you reach a page with no outgoing links you cannot continue, so backward traversal is impossible
Direction creates asymmetric reachability — the existence of a directed path from A to C does not guarantee any path from C back to A. The web link graph is a classic example: following hyperlinks is strictly one-directional. This is the fundamental departure from undirected graphs, where connectivity is symmetric. A digraph can be 'weakly connected' (undirected version is connected) without being 'strongly connected' (every vertex reachable from every other).
Question 2 Multiple Choice
A vertex in a digraph has in-degree 0 and positive out-degree. This vertex is called a source. Which best describes its role?
AIt receives information from all other vertices but produces none
BIt produces information or flow that others receive, but nothing points into it from other vertices
CIt is an isolated vertex with no connections in either direction
DIt has equal in-degree and out-degree, making it balanced
A source has no incoming arcs (in-degree 0) and at least one outgoing arc. Nothing feeds into it — it originates flow. In a software dependency graph, a source package has no dependencies of its own. In a web graph, a source page is never linked to by other pages. This is the directed analogue of an isolated node only in one direction — it participates in the graph actively as an originator, not passively as a receiver.
Question 3 True / False
A directed graph can be weakly connected without being strongly connected — treating all edges as undirected yields a connected graph, but directed paths between some pairs of vertices may not exist in both directions.
TTrue
FFalse
Answer: True
Weak connectivity only requires that the underlying undirected graph (ignoring arrows) is connected. Strong connectivity requires that every vertex can reach every other vertex by following directed paths. A simple counterexample: A → B → C is weakly connected (A, B, C are all linked) but not strongly connected (C cannot reach A or B following directed paths). Most real directed graphs — web links, citation networks, dependency graphs — are weakly but not strongly connected.
Question 4 True / False
In a directed graph, if vertex B is reachable from vertex A via a directed path, then vertex A is necessarily reachable from vertex B via a directed path.
TTrue
FFalse
Answer: False
This is the key conceptual error when transitioning from undirected to directed graphs. In undirected graphs, connectivity is symmetric. In directed graphs, reachability is asymmetric — following arrows forward may take you somewhere you cannot return from. B reachable from A means there exists a sequence of arcs pointing in the forward direction from A to B; there may be no path back. This asymmetry is exactly why one-way streets, hyperlinks, and dependency graphs require digraphs to model accurately.
Question 5 Short Answer
What is the difference between weak connectivity and strong connectivity in a directed graph, and why does the distinction matter in practice?
Think about your answer, then reveal below.
Model answer: A digraph is weakly connected if ignoring edge directions leaves a connected undirected graph — all vertices are linked, but directional reachability may be one-way. It is strongly connected if every vertex can reach every other vertex by following directed paths. The distinction matters because many algorithms and real-world properties depend on which type applies. Topological sorting, for example, is only possible in directed acyclic graphs (which are not strongly connected). Strongly connected components partition a digraph into the maximal subsets within which every vertex is mutually reachable, which is essential for analyzing dependency cycles, finding feedback loops in systems, and determining which nodes in a web graph can be reached from each other.
The directed analogue of the handshaking lemma — sum of in-degrees equals sum of out-degrees equals number of arcs — also reflects this structure. Identifying strongly connected components is a fundamental algorithmic problem solved by Kosaraju's or Tarjan's algorithm, both of which build on depth-first search.