Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

I am dealing with a particular problem where I want to analyze the properties of a graph of connected nodes. What I am looking for are weak points in the graph (i.e. places where I can remove the fewest number of nodes to break the graph). It won't be easy to explain in text for this question, but I shall try my best.

In my problem, I have a set of points where each point is connected to all neighboring points and is not connected to any non-neighboring points. Weight of the connections is not a factor. One way to perhaps think of this would be a set of pixels that make up an object.

x
xx
xxxxx

In the above object, each x represents a node and every node is connected to every node that is above, below, left, right, or diagonal from it. What I would like is to analyze this graph such that I could identify that the 3rd node in the 3rd row is a weak point to the graph (remove it and access from the left side of the graph to the right side of the graph is broken). Furthermore, I would also like to identify that the two nodes in the second column could be removed which would break the entire graph in half.

I clicked through all the links on the Graph Theory page of Wikipedia, but the ones I could understand almost exclusively seemed to be about finding shortest paths and similar coverage problems. I didn't see anything about looking for potential weak points in the graph, but I'm sure there must be something. Does anyone out there know of a potential avenue of research or similar solved problems that I can look at?

Thanks in advance for your help.

share|improve this question
2  
You may be interested in Menger's theorem and the Cheeger number of a graph. – Jonathan Christensen Jan 12 at 22:12
1  
That was a great start. Thanks. It helped me find en.wikipedia.org/wiki/Vertex_separator which looks like it will help me determine specific weak nodes. It looks like Menger's theorem and Cheeger number will help me determine the likelihood of finding truly weak nodes which is also important for the problem that I'm tackling. – Kyle Jan 12 at 23:45
1  
Check out: Souza, Cid de, and Egon Balas. "The vertex separator problem: algorithms and computations." Mathematical programming 103.3 (2005): 609-631. – B.D Jan 13 at 0:12
That's looking promising. The parts of it that I can understand sound like exactly the thing I'm trying to do. Very awesome. – Kyle Jan 13 at 0:30

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.