Problems on edges and graphs

Assignment Help Data Structure & Algorithms

Reference no: EM1380153

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

<b>problem:</b>
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?

<b>solution:</b>

Suppose if we add an edge to a biconnected graph with k strongly connected components, then there are 3-situations: the endpoints of edge lie in different strongly connected component and there is no path between 2 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

Reference no: EM1380153

Questions Cloud

Explain an application level protocol : Create and explain an application level protocol to be used in an automatic teller machine and a bank's centralized computer. Your protocol should permit a user's card and password to be verified,

Find efficiency of high speed digital transmission system : Assume I have a multiplexer that is connected to a high speed digital transmission system that can transfer 1,536,000 data bits per second.

Website creation : Construct a basic, generic structure of a web site. Name it something generic etc. Demonstrate some basic layout of the content of the pages.

Design a dss to help decision-makers : Design a DSS to help decision-makers run the 2012 London Olympics-Write down the step-by-step solution to train the classifier by the basic perceptron learning rule.

Problems on edges and graphs : Suppose if we add an edge to a biconnected graph with k strongly connected components, then there are 3-situations: the endpoints of edge lie in different strongly connected component and there is no path between 2 in the original graph,

Finding total available storage capacity : A certain hard disk has 480 cylinders, sixteen tracks, and thirty-two sectors of 512 bytes each. It spins at 4800 revolutions per minute, and has an adjacent cylinder seek time of eighty msec, and a max seek time of onde hundred msec.

Creating visual studio.net web application : Make a Visual Studio.NET 2005 web application with one aspx form. Place a CheckBoxList, TextBox, Button, and Label control on the form.

Creating a data flow chart : Create a Data Flow Chart and then make an application that allows a user to enter a stock transaction and determine the stockbroker's commission.

Computing available storage space : There are twenty gigabyte of space on a computer's hard disk. I transfer information via a telephone line (connection) at the rate of 14,400 bits per second.

User Account

All Pages