AlanTuring Posted September 25, 2012 Share Posted September 25, 2012 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. Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now