Google Answers Logo
View Question
 
Q: Graph Theory ( Answered 5 out of 5 stars,   1 Comment )
Question  
Subject: Graph Theory
Category: Science > Math
Asked by: herbie217-ga
List Price: $10.00
Posted: 26 Jun 2002 04:29 PDT
Expires: 26 Jul 2002 04:29 PDT
Question ID: 33445
Let G be a connected graph.  Given a subset X of vertices of G, find
an algorithm to determine the minimal connected subgraph of G
containing X.  In other words, find a subset of edges of G so that
there is a path from every element in X to any other element in X
having the property that no other such subset can contain fewer edges.
 Note: it must be clear how to code the algorithm in C or some other
programming language.  You can assume that G is represented by an
incidence matrix.  Please also provide some references.

Request for Question Clarification by rbnn-ga on 26 Jun 2002 11:07 PDT
Are you looking for a minimal connected subgraph with the property in
question or a minimum connected subgraph? Usually in combinatorics, we
say a set is "minimum" with respect to a certain property if that set
is the smallest with the given property; we say a set is "minimal"
with respect to the property if deletion of any element from that set
will result in the property no longer holding in the set.

That is, your problem statement "so that no other such subset can
contain fewer edges" is normally called a "minimum connected
subgraph". The "minimal connected subgraph" would be a connected
subgraph containing X such that deletion of any edge from that
subgraph would not be connected.

Clarification of Question by herbie217-ga on 26 Jun 2002 14:55 PDT
Sorry for the incorrect use of terms.  In fact, I do mean minimum.  I
was using the word minimal in the sense that the subgraph may not be
unique.  Also, if it makes things easier you can assume that the graph
is a tree, in which case, I think the subgraph would be unique.
Answer  
Subject: Re: Graph Theory
Answered By: rbnn-ga on 26 Jun 2002 16:09 PDT
Rated:5 out of 5 stars
 
OK, I will answer the question in your clarification:
 Let G have vertices V and edges E be an (undirected) graph that is
also a tree. Let X be a subset of V. Find the graph G' with the
minimum number of  edges, vertices V' subset of V and E' subset of E,
such that X subset of V' and G' is connected.

We observe that removal of any edge in a tree disconnects that tree;
therefore G' must also be a tree. (An undirected graph is a tree if
and only if it is connected and acyclic).

Here is one way to solve the problem in linear time, if G is given on
input in adjacency list format.

We assume without loss of generality that the root of G is in X (since
any node in an undirected tree can be made the root).

We assume each node in V has field children pointing to its children,
and we will add a field numberXdescendants as well.

Step 1: For each node in G, find out how many descendants are in X:

 function compute_descendants (node) //node is a node in the tree
   ndescendants=0; // the number of descendants in X
   foreach (childnode in node.children)
     ndescendants = ndescendants + compute_descendants(childnode);
   if (node is in X)
      ndescendants=ndescendants+1.
   node.numberXDescendants=ndescendants
   return ndescendants
   

We start by calling:
  compute_descendants(root)

Step 2: Find the minimum tree. Here are a greedy algorithm works. We
simply prune subtrees that have no X descendants in them.

That is, the answer, V' will comprise all nodes any of whose children
are in X (or which are in X themselves) and the edges will be all
edges connecting them:

  function walk(node)
    if (node.numberXdescendants>0)
       add node to V'
       for_each (childnode in node.children) {
           if (childnode.numberXdescendants>0)
              { walk(childnode)
                add edge (node, childnode) to E'
               }

We solve the problem by calling:
  walk(root)

after which global variables V' and E' will have the answer.

Depending on the datastructures and input format, asymptotic
complexity will be between linear and linear*logarithmic, i.e., N log
N.

Proof of correctness:
  Since (V',E') forms a tree, it is clearly connected, and by
construction V' contains X. Thus, we only need to show that G'=(V',E')
is the minimum such graph. We can use induction to see this. First, we
note that indeed walk(node) does correctly compute the subtree of G
that consists of all nodes of G any descendant of which are in X or
which are in X themselves.

Let G''=(V'',E'') be any other subtree containing X. V'' must contain
the root of the tree, which is in X by assumption. If V'' contains a
node, then it must also contain any nodes in any subtrees of children
of that node which contain nodes in X. That is, if childnode is a
child of node, then if childnode.numberXdescendants is > 0, then it is
the case that V'' must contain childnode as well. Hence, V' is a
subset of V''.

References:
 This all standard graph theory. Some graph theory sites are:
http://www.math.fau.edu/locke/graphthe.htm or
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/mst.html .

Is this sufficient detail for you? I can send you some Java code for
the problem as well, but I want to make sure this is the problem you
want the answer to.
herbie217-ga rated this answer:5 out of 5 stars
This is exactly the problem I needed solved.  You have provided just
the right amount of detail.  I coded the algorithm yesterday and it
works very well.  I am also very pleased that the algorithm is NlogN. 
Thank you very much for your help!

Comments  
Subject: Re: Graph Theory
From: jhouse-ga on 26 Jun 2002 07:15 PDT
 
Your question is not an easy one...  There doesn't seem to be any kind
of logical starting point for an arbitrary set.  For a moment I though
I had something when I tried to consider a pair of nodes that are
closer to each other than to any other nodes...  You can't rely on
using the shortest path between any of the relevent nodes...

Starting with an arbitrary configuration and making successive
approximations also seems problematic.
Good luck on finding your answer... Hopefully my comment will inspire
someone to conquer the challenge :)

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy