Computer Science Homework Solutions
Problem
#74502

Edges and graphs

The solution below got cut off.  Please let me know what is the total solution:

problem:
The number of strongly connected components in a graph G is k. By how much can this number change if we add a new edge?

solution:

If we add an edge to a biconnected graph with k strongly connected components, then there are three scenarios: the endpoints of the edge lie in different strongly connected component and there is no path between the two in the original graph, the endpoints of the edge lie in different strongly connected component and there is a path between the two in the original graph, and the endpoints of the edge lie in the same strongly connected component. In the former, the edge becomes a bridge, and thus the strongly connected components remain separate. In the middle case, the edge completes a simple cycle that includes the path between the two stongly connected components and thus the number of strongly connected components decreaseby n − 1, where n is the number of strongly connected components on that path (including the two in which the endpoints

Solution
What is this?
By OTA - Overall OTA Rating
Xiao Liu, MS - 4.7/5
Purchase Cost Now
$2.19 CAD (was ~$3.99)
Included in Download
  • Plain text response
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
  • Edges and graphs - The number of strongly connected components in a graph G is k. By how much can this number change if we add a new edge?
  • Data Structures C++ - Explain biconnected graph in your own words.
  • E-R Diagram - Assume that at XYZ company each product (described by Product No., Description, and Cost) is comprised of at least three components (described by Component No., Description, and Unit of Measure) and c ...
  • C++ Programming (Arrays and Strings) - A) Write C++ statements to do the following: 1. Declare an array alpha of 15 components of the type int. 2. Output the value of the tenth component of the array alpha. 3. Set the val ...
  • TCP/IP network scenarios - Identify the problems with the TCP/IP network in each scenario and explain how they should be fixed. Explain your answer for each of the scenarios. See attachment for scenarios.
Browse