Three: Consider the following two definitions of a rooted undirected tree: Struc

Question

Three: Consider the following two definitions of a rooted undirected tree: Structural: A rooted tree of height n (n20) edges is a connected undirected graph without cycles where one node is designated as the root; and the longest path from the root to any node is of length n edges. (There could be more than one such path of length n.) Recursive A rooted tree of height 0 edges is a graph with one node (the root) and no edges A rooted tree of height n > 0 edges is a graph consisting of: The root node, One rooted sub-tree of height n-1, Zero or more additional rooted sub-trees of heightn-1, and For each sub-tree there is one edge between the root of the sub- tree and the root of the tree. All sub-trees are disjoint from each other. Prove that these two definitions are equivalent. (You may want to use induction for at least one direction of the proof.)

Explanation / Answer

Let us apply induction on height of recursive rooted undirected tree to prove it is equivalent to structural rooted undirected tree.

Basis:

when height h=0. recursive rooted undirected tree is simple a single node.

similarly,height h=0, the longest path contains (h=0) no edges, So this is also a single node.

Inductive step:

Assume for height k both  recursive rooted undirected tree and structural rooted undirected tree are equivalent.

For height k+1, recursive tree is formed by adding at least one k height recursive tree to a node(those are also structural tree of height k).

Now, longest path from root to any node of this graph will be: 1+longest path of k height structural tree=k+1.

Hence both are equivalent.

  

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.