Question

Draw an\({{\bf{S}}_{\bf{k}}}\)-tree for \({\bf{k = 0,1,2,3,4}}\).

Short answer

Sketch of the \({S_k}\)-tree for \(k = 0,1,2,3,4\) is shown below.

Step-by-step solution

General form

Principle of \({{\bf{S}}_{\bf{k}}}\)-trees:A rooted tree T is called an \({{\bf{S}}_{\bf{k}}}{\bf{ - tree}}\) if it satisfies this recursive definition.

It is an \({S_0}\)-tree if it has one vertex. For \(k > 0\), T is an \({S_k}\)-tree if it can be built from two \({S_{k - 1}}\)-trees by making the root of one the root of the \({S_k}\)-tree and making the root of the other child of the root of the first \({S_{k - 1}}\)-tree.

Draw the trees

Since \({S_0}\) contains a single vertex.

\({S_1}\)contains an edge between two single vertices and one of the vertices has to be the root.

\({S_2}\)contains two copies of \({S_1}\) with an edge from the root of one copy to the root of the other copy.

Note: You need to place the root of the right copy at level 1 along with the rest of the copy.

Similarly, \({S_3}\) and \({S_4}\) will be traced.

Let us see the graph to understand the above notes.

Hence, the above graph represents the \({{\bf{S}}_{\bf{k}}}\)-tree for \({\bf{k = 0,1,2,3,4}}\).