Question

a) Define a rooted tree and the root of such a tree.

b) Define the parent of a vertex and a child of a vertex in a rooted tree.

c) What are an internal vertex, a leaf, and a subtree in a rooted tree\(?\)

d) Draw a rooted tree with at least \({\bf{10}}\) vertices, where the degree of each vertex does not exceed \({\bf{3}}\). Identify the root, the parent of each vertex, the children of each vertex, the internal vertices, and the leaves.

Short answer

a) A rooted tree is a directed graph where a vertex is specified (which is the root of the tree) and there is a unique path from the root to every other vertex.The root is the unique vertex in the directed graph that has the property that there is a unique path from the root to every other vertex.

b) The children of \({\bf{m}}\) are all vertices below \({\bf{m}}\) that are connected to \({\bf{m}}\) by an edge. The parent of \({\bf{m}}\) is the vertex above \({\bf{m}}\) that is connected to \({\bf{m}}\) by an edge.

c) The internal vertices are all vertices that have children.The leaves are all vertices with no children.A subtree of a tree is a subgraph of that tree and this subgraph also has to be a tree itself.

d) Answers could vary.

Step-by-step solution

Definition

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.

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

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

A rooted tree is a directed graph where a vertex is specified (which is the root of the tree) and there is a unique path from the root to every other vertex.

Parent and child of a vertex

The root is the vertex in the directed graph that has the property that there is a unique path from the root to every other vertex (there will not be another vertex in the graph that has this property).

The children of a vertex \({\bf{m}}\) are all vertices below \({\bf{m}}\) that are connected to \({\bf{m}}\) by an edge.

The parent of a vertex \({\bf{m}}\) is the vertex above \({\bf{m}}\) that is connected to \({\bf{m}}\) by an edge.

Rooted tree

The internal vertices are all vertices that have children.

The leaves are all vertices with no children.

A subtree of a tree is a subgraph of that tree and this subgraph also has to be a tree itself.

The tree requires a degree of at most \({\bf{3}}\) at each vertex, which means that every vertex can have at most \({\bf{3}}\) children.

A possible such tree is:

Step 4:Vertex and children

The root is the vertex at the top of the tree, which is \({\bf{a}}\).

Root\({\bf{ = a}}\)

The children of a vertex \({\bf{m}}\) are all vertices below \({\bf{m}}\) that are connected to \({\bf{m}}\) by an edge.

\(\begin{array}{*{20}{r}}{{\bf{ Vertex }}}&{{\bf{ Children }}}\\{\bf{a}}&{{\bf{b,c}}}\\{\bf{b}}&{{\bf{d,e,f}}}\\{\bf{c}}&{\bf{g}}\\{\bf{d}}&{{\bf{h,i}}}\\{\bf{e}}&{{\bf{ No children }}}\\{\bf{f}}&{\bf{j}}\\{\bf{g}}&{{\bf{ No children }}}\\{\bf{h}}&{{\bf{ No children }}}\\{\bf{i}}&{{\bf{ No children }}}\\{\bf{j}}&{{\bf{ No children }}}\end{array}\)

Vertex and parent

The parent of a vertex \({\bf{m}}\) is the vertex above \({\bf{m}}\) that is connected to \({\bf{m}}\) by an edge.

\(\begin{array}{*{20}{r}}{{\bf{ Vertex }}}&{{\bf{ Parent }}}\\{\bf{a}}&{{\bf{ No parent }}}\\{\bf{b}}&{\bf{a}}\\{\bf{c}}&{\bf{a}}\\{\bf{d}}&{\bf{b}}\\{\bf{e}}&{\bf{b}}\\{\bf{f}}&{\bf{b}}\\{\bf{g}}&{\bf{d}}\\{\bf{h}}&{\bf{d}}\end{array}\)

Internal vertices and leaves

The internal vertices are all vertices with children.

Internal vertices \({\bf{ = a, b, c, d, f}}\)

The leaves are all vertices without children.

Leaves \({\bf{ = e, g, h, i, j}}\)