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. |