December 16th, 2008
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.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.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.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.
Posted in linkdatax.com | edit
