Question

1. Graphs (11 points) (1) (3 points) How many strongly connected components are in the three graphs below? List the vertices associated with each one. 00 (2) (4 points) For the graph G5: (a) (0.5 points) Specify the set of vertices V. (b) (0.5 points) Specify the set of edges E. (c) (1 point) Give the degree for each vertex. (d) (1 point) Give the adjacency matrix representation for this graph. (Assume vertices are sorted lexicographically.) (e) (1 point) Give the adjacency list representation for this graph. (3) (4 points) For the graph Go: (a) (0.5 points) Specify the set of vertices V. (b) (0.5 points) Specify the set of edges E. (c) (1 point) Give the in-degree and the out-degree for each vertex. (d) (1 point) Give the adjacency matrix representation for this graph. (Assume vertices are sorted lexicographically.) (e) (1 point) Give the adjacency list representation for this graph. b C of G5 2. Introduction to Trees (7 points) (1) (2 points) Which of the graphs G1, G2, G3, and G4 above are trees? (briefly justify your answers) (2) (5 points) Use induction on 1 to show that for all 1 > 1, a full binary tree with I leaves has 21 – 1 vertices total.

Please answer question 2. Introduction to Trees

Thank you

Answer 1

1). Out of graphs G1,G2,G3,G4  graph G2 is a tree because :-

Graph G2 is :-

2 op

Graph G2 satisfies all the conditions and properties of a tree which are as :-

• It has n vertices and (n-1) edges .
• No loop should be present in tree .
• All vertices are connected to each other through edges .

While in case of graph G1

- Gತ

it does not satisfies the property of a tree which is :-

A tree must have n vertices and (n-1)edges , so therefore it is not a tree.

In case of graph G3

the edges bcf are forming a loop which is not possible in a tree.So it is not a tree .

In case of graph G4

9

their is also a self loop in edge cf so it is not a tree.

Hence, from the graph G1,G2,G3and G4 , graph G2 is a tree.

2). TO show using induction on l for l>=l , a full binary tree with l leaves has 2l-1 vertices total.

We can prove N = 2l-1 (or N = l+l-1) by induction as :-

Base Case :-

A tree with 1 leaf has 1 node altogether. A tree with 2 leaves has 3 nodes altogether. Base case proves the theorem for L = 1and L=2.

Inductive hypothesis :-

Let's assume that any full binary tree with l leaves has n = 2l-1 total nodes.

Inductive step :-

Prove that all any full binary tree with L+1 leaves has N = 2(L+1)-1 total nodes.

Let T be a full biinary tree with L+1 leaves . Select  a leaf v at maximal depth such that v’s sibling is also a leaf at maximal depth. Remove both v and v’s sibling and let T′ be the resulting tree. T′ is a full binary tree with L leaves which, by our inductive hypothesis, must have 2L−1 total nodes N. Note v’s parent is now a leaf in tree T′. Add v and v’s sibling back to their parent and notice the parent becomes an internal node. Thus, the tree loses one leaf but gains another two (that we added). The number of leaves increased by a total of 1 from L⇒L+1, while the number of nodes increased by two 2L−1+2 = 2L+1. This clearly equals 2(L+1)−1, thus proving by induction that the number of total nodes N in any full binary tree with L leaves is 2L−1.