Chain Decomposition on Trees

Graph thinking reframes problems: entities → vertices, relationships → edges, then pick traversal or classic algorithm.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Ask: directed? weighted? connected? Build correct representation first; only then choose BFS, DFS, Dijkstra, topo, MST, or flow.

Try this in Python

# adjacency list: adj[u] = neighbors of u
adj: list[list[int]] = [
    [1, 2],
    [0, 3],
    [0],
    [1],
]
print(len(adj), adj[0])

Common mistakes

• Solving without explicit graph model.
• Mixing tree and general graph assumptions.

Key takeaways

• Draw small example with 5–6 nodes.
• Name the algorithm family before coding.