Editing Heavy-light decomposition
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 9: | Line 9: | ||
<p>At most two edges incident upon a given vertex may then be heavy: the one joining it to its parent, and at most one joining it to a child. Consider the subgraph of the tree in which all light edges are removed. Then, all resulting connected components are paths (although some contain only one vertex and no edges at all) and two neighboring vertices' heights differ by one. We conclude that '''the heavy edges, along with the vertices upon which they are incident, partition the tree into disjoint paths, each of which is part of some path from the root to a leaf.'''</p> | <p>At most two edges incident upon a given vertex may then be heavy: the one joining it to its parent, and at most one joining it to a child. Consider the subgraph of the tree in which all light edges are removed. Then, all resulting connected components are paths (although some contain only one vertex and no edges at all) and two neighboring vertices' heights differ by one. We conclude that '''the heavy edges, along with the vertices upon which they are incident, partition the tree into disjoint paths, each of which is part of some path from the root to a leaf.'''</p> | ||
<p>Suppose a tree contains <math>N</math> vertices. If we follow a light edge from the root, the subtree rooted at the resulting vertex has size at most <math>N/2</math>; if we repeat this, we reach a vertex with subtree size at most <math>N/4</math>, and so on. It follows that '''the number of light edges on any path from root to leaf is at most <math>\lg N</math>.'''</p> | <p>Suppose a tree contains <math>N</math> vertices. If we follow a light edge from the root, the subtree rooted at the resulting vertex has size at most <math>N/2</math>; if we repeat this, we reach a vertex with subtree size at most <math>N/4</math>, and so on. It follows that '''the number of light edges on any path from root to leaf is at most <math>\lg N</math>.'''</p> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Applications== | ==Applications== |