Graph Theory37 sections · 1633 units
Open in Course

Heavy Paths as Chains

(Maximal heavy sequences)

A heavy path is a maximal sequence of heavy edges. Start at some node, follow heavy edges downward as far as possible. Stop when you reach a node with no heavy child. Each heavy path forms one chain. Light edges connect different chains. Every node belongs to exactly one chain, either as part of a long heavy path or as a singleton chain.

The root might start a chain if it has a heavy child. Otherwise, it forms a chain by itself. Chains partition the tree into disjoint paths.