Skip to main content

Graph Representation and Traversal Lab

P1. Model and identity​

Declare vertices 0–3 and directed records (0,1,5),(0,1,2),(1,2,0). Specify the additive-route answer from 0, including edge IDs, isolated vertices and zero weights. Explain what changes when edges become undirected.

P2. Representation ledger​

For V=10,000 and E=30,000, price a dense eight-byte scalar matrix versus the counts of list headers and directed adjacency records. Explain which extra byte costs need an implementation model, and how a scalar matrix loses parallel IDs.

P3. Structure assumptions​

Give a graph with V-1 edges that is not a tree, a DAG whose underlying undirected graph has a cycle, and a small nonbipartite graph. State the assumptions of the planar bound E<=3V-6. Include isolated vertices in your definitions.

P4. Reduction direction​

Model a dependency A requires B, plus worker/job assignments allowing workers at most one job. State edge direction, feasible outputs and both directions of the assignment reduction. Explain what changes with two jobs per worker.

P5. BFS evidence​

For 0→1,0→2,1→3,2→3 and isolated 4, give distances and two valid parent witnesses from 0. Prove shortest hop counts, and find a weighted counterexample to using the same result as minimum additive cost. Trace marking at enqueue.

P6. DFS and components​

Trace discovery/finish events for 0→1,1→2,2→1,0→2 in listed adjacency order. Classify the cycle edge and the later 0→2 edge. Explain the state required in an iterative frame and how to handle an undirected parallel edge to a parent.

P7. SCC partition​

For 0→1,1→0,1→2,2→3 and isolated 4, compute SCCs and the condensation DAG. Trace Kosaraju's two passes. Explain why weak connectivity or one source traversal does not produce the SCC partition. Describe a maximality check.

P8. DAG order and blocked tasks​

For 0→2,1→2,2→3 with isolated 4, give two valid orders and verify every edge. Add 3→2. Which vertices are in a cycle and which remain orderable? Explain why unemitted vertices in a more general Kahn run can include noncyclic descendants.

Use Practice Solutions after preserving your independent attempt. Equivalent valid witnesses are accepted.