(1) (3 points) How many strongly connected components are in the three graphs be

Question

(1) (3 points) How many strongly connected components are in the three graphs below? List the vertices associated with each one Reminder: for undirected graphs strongly connected and connected are equivalent state- ments G2 (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 G6 (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. Ca T 6 3. Introduction to Trees (7 points) (1) (2 points) Which of the graphs Gi, G2, G3, and Ga above are trees? (briefly justify your (2) (5 points) Use induction on to show that for all 1, a full binary tree with I leaves has answers 21- 1 vertices total. Activa Go to Se

Explanation / Answer

Solution:

Note:
The first question is done as per Chegg guidelines, please repost others.

G1:

In G1 there are 2 strongly connected components.

G2:

In G2 as well, there is 1 strongly connected component.

G3:

IN G3 there are no strongly connected components.

G4:

In G4 there are 2 strongly connected components.

and they are

b-e-d and c-f

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.