Jump to content

Graph connecitivty and run time analysis

AlanTuring
in Mathematics

Featured Replies

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.

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

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.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.