Jump to content

Graph connecitivty and run time analysis


AlanTuring
 Share

Recommended Posts

Hi so i am preparing for my algorithms class exam and this question is the second last one in my text book with graphs, and i am not too sure how to obtain an algorithm that is just O(m+n).

 

 

a) Prove that every connected graph G=(V,E) has a node v∈V such that removing v and all its adjacent edges will not disconnect G.

 

(b) For a given connected graph G=(V,E), design an O(n+m)-time algorithm to find such a node.

 

 

 

I have understood that i need to take a case such as say for nodes v,w there is a node in between the path from v to w such that if v - x - w is the path, and x is removed, the graph is still connected. Anyone have any ideas?

 

TIA.

 

 

 

 

 

Edited by AlanTuring
Link to comment
Share on other sites

  • 1 month later...

Your questions are very simple and easy to solve ...

 

question a talks about the case of having a graph made of two sub-graphs which are only connected through 1 edge, where nodes on its sides are considered critical

 

question b is not simple, but to find that critical node, you have to go over all nodes in the graph, then check if there exist a circuit,

then it's part of a cycle, and breaking it won't disjoint any sub-graph in that graph by removing this node

 

note: you have to check for all edges connected to every node, if there exist a node that has no circuit, then it's a critical node

Edited by khaled
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.