A tree is a connected, acyclic undirected graph. So, for each pair v and u of...

Transcribed Image Text:

A tree is a connected, acyclic undirected graph. So, for each pair v and u of nodes in a tree, there is exactly one simple path connecting v and u (a simple path is one that does not repeat any node). The diameter of a tree t is the length of the longest simple path in t. For example, the tree shown below has diameter 12. A (nonempty) rooted tree is a tree (V, E) together with a node (the root) v E V. In the diagram below we have placed the tree's root at the top. The height of a rooted tree (v, V, E) is the length of the longest simple path from v to some other node u E V. For example, the rooted tree shown below has height 8. Assume that a rooted tree is represented as a label-and-pointer structure that provides the root (a label) together with a (possibly empty) list of pointers, each pointing to a rooted tree. Design a linear-time recursive algorithm that, given a non-empty rooted tree, finds the tree's diameter. Hint: Given the rooted tree G = (v, V, E), let v's neighbours be u₁,..., uk. Removing v and its incident edges from G leaves us with k separate rooted trees G₁,..., Gk, with roots u₁,..., uk, respectively, and these graphs can now be dealt with recursively, after which G's diameter can be calculated. A tree is a connected, acyclic undirected graph. So, for each pair v and u of nodes in a tree, there is exactly one simple path connecting v and u (a simple path is one that does not repeat any node). The diameter of a tree t is the length of the longest simple path in t. For example, the tree shown below has diameter 12. A (nonempty) rooted tree is a tree (V, E) together with a node (the root) v E V. In the diagram below we have placed the tree's root at the top. The height of a rooted tree (v, V, E) is the length of the longest simple path from v to some other node u E V. For example, the rooted tree shown below has height 8. Assume that a rooted tree is represented as a label-and-pointer structure that provides the root (a label) together with a (possibly empty) list of pointers, each pointing to a rooted tree. Design a linear-time recursive algorithm that, given a non-empty rooted tree, finds the tree's diameter. Hint: Given the rooted tree G = (v, V, E), let v's neighbours be u₁,..., uk. Removing v and its incident edges from G leaves us with k separate rooted trees G₁,..., Gk, with roots u₁,..., uk, respectively, and these graphs can now be dealt with recursively, after which G's diameter can be calculated.

Answer rating: 100% (QA)

An object of this class holds data about a game of checkers It knows what kind of piece is on each square of the checkerboard Note that RED moves up the board ie row number decreases while BLACK moves ... View the full answer