k-connectivity of a graph

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Guardian_Shadow
New poster
Posts: 19
Joined: Thu Oct 12, 2006 6:04 pm

k-connectivity of a graph

Post by Guardian_Shadow » Mon Jan 08, 2007 6:59 pm

So, suppose we need to find out what's the least number of edges we need to delete, to break an undirected graph into two components.
I know that the number of edges can be found using a min cut - max flow algorithm, but how do you actually determine which edges to delete ?!
Thanks for the help.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Tue Jan 09, 2007 2:06 am

Let S be the set of vertices reachable from the source via an augmenting path, and T the set of those from which there exists an augmenting path to the sink. If you use the Ford Fulkerson method to find the max flow, at the end no augmenting path from the source to the sink exists, so S and T are disjoint and the set of edges to delete to disconnect source and sink is simply those going from S to T (because they are the ones that prevent the existence of yet another augmenting path).

Post Reply

Return to “Algorithms”