Articulation point of graph / Biconnected components and DFS traversal


In the connected graph G, a vertex V is said to be an articulation point if and only if the deletion of vertex V disconnects the graph into two or more non - empty components. For more precisely satisfy this concept, consider the following connected graph
 
In this graph, basically vertex 2 is an articulation point, as if we delete the vertex, it will disconnects the graph into two non - empty component.
 

As shown in the fig, it would be disconnected the graph into two parts as shown in fig (b). thus we cannot say that, the above graph is bi-connected graph. Again for simplicity consider the following graph
The above graph (c) would be considered as bi-connected graph, as we deleted any vertex it can not be form another part of graph. By the above description, we can surely say that in connected graph G, every bi-connected component contains at least two vertices. Now for identifying the articulation point and the bi-connected components, DFS techniques of graph can be very useful. Consider the following graph and weights on it. Lets apply the DFS technique, mainly DFS technique is using the stack.
 
Apply DFS on above graph, then the graph would be as follows 
 

Comments

Post a Comment

Popular posts from this blog

Brief shortnote on Requirement elicitation and requirement analysis

Image
- Requirement elicitation means gathering of requirements. - Perhaps it is most difficult, critical, most error prone and most communication intensive aspect of software development. - The most important goal of software requirement engineering is to find out what the customer really wants. - The users need can be identify only by understanding expectation of the user from the developers. - Requirements are gathered by asking the question to user and writing down their answers and their exceptions of the software that how he want to use software. - Gathering the requirements of users is the most difficult part of the software development, because both developer and user have different mindset regarding the software. - Here, communication of both the parties are the most essential for software product. - There are number of requirement elicitation method. https://en.wikipedia.org/wiki/Requirements_elicitation   - Some people think that one methodology is alway
Read more

Requirement Engineering

Image
- Requirement engineering produces one large document, written in natural language, contain a description of what the system will do without describing how will it do. - Requirement engineering is the discipline application of proven principles, methods, tools and notations to describe the proposed system’s intended behavior and its associated constraints. - This process contains the four steps as shown in fig i] Requirement Elicitation This is also known as gathering of requirements. Here the requirements are identified with the help of customer and existing system process are available. ii] Requirement Analysis Requirement analysis     are start with requirement elicitation. Here the requirements are analysis in order to identify inconsistencies, defects, omission etc. iii] Requirement Documentation This is the end product of requirement elicitation and analysis. The documentation is very important as it is the foundation of the software. iv] Requi
Read more