3. (10 points) In a directed graph, strongly connected component is defined as a

Question

3. (10 points) In a directed graph, strongly connected component is defined as a subset of vertices C E V that are mutually reachable from each other, which means that for any pair of vertices v, w E C , there is a path from v to w, and from w to v. A) Let G be an undirected graph on n vertices, and let k be the number of components of G. If we add one edge to G, how many components might it have? B) Let G be a directed graph on n vertices, and let k be the number of strongly connected components (SCC's) of G. If we add one edge to G, how many SCC's might it have?

Explanation / Answer

A) No of components in Graph G is k and by adding one edge such that it starting and ending point both lies on the same graph, then no. of components will remain k, whereas if it lies on two differrent components then no. of components will reduce to k-1.

B) Similarly their is a possibility that the edge connects two diffrerent SCCs such that it becomes the missing link and joins them to form a single SCC, therefore no. of SCCs will reduce to k-1 and if doesn't work in that way then no. of SCCs will remain k.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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