Question

Answer the same questions as listed in Exercise \({\bf{3}}\) for the rooted tree illustrated.

Short answer

(a). a

(b). a, b, d, e, h, i, o

(c). c, f, j, k, l, m, n, p, q, r, s

(d). None

(e). d

(f). p

(g). a, b, g

(h). e, f, g, j, k, l, m

Step-by-step solution

Definitions

A tree is an undirected graph that is connected and that does not contain any simple circuits.

A graph is connected if there exists a path between every pair of vertices.

A simple path is a path that does not contain the same edge more than once.

A circuit is a path that begins and ends in the same vertex.

Finding the vertex, internal vertices, leaves and children of \({\bf{j}}\)

1. The root of the tree is the vertex at the top of the tree.

Root =a

2. The internal vertices are all vertices that have children.

Internal vertices =a, b, d, e, g, h, i, o

3. The leaves are all vertices with no children.

Leaves =c, f, j, k, l, m, n, p, q, r, s

4. The children of j are all vertices below j that are connected to j by an edge. Since j is not connected to vertices lower than j in the tree, j does not have any children.

Children of j = None

Finding the parents, siblings, ancestors and descendants’ vertices

5. The parent of h is the vertex above h that is connected to h by an edge.

Parent of h=d

6. The siblings of o are the vertices who have the same parent as o.

Siblings of o=p

7. The ancestors of m are all vertices in the path from the root to m (except m itself).

Ancestors of m=a, b, g

8. The descendants of b are all vertices whose ancestor is b.

Descendants of b=e, f, g, j, k, l, m