graph theory
I am trying to write a divide & conquer algorithm for trees. For the divide step I need an algorithm that partitions a given undirected Graph G=(V,E) with n nodes and m edges into sub-trees by removing a node . All subgraphs should have the property that they don't contain more than n/2 nodes (the tree should be split as equal as possible). First I tried to recursively remove all leaves from the tree to find the last remaining node, then I tried to find the longest path in G and remove the middle node of it. The given graph below shows that both approaches don't work:
Is there some working algorithm that does what I want (returns the node H in the above case).
I think you could do it with an algorithm like this:
Start in the root (if the tree isn't rooted, pick any node).
In each step, try to descend into the child node that has the largest subtree (the number of nodes “below” it is the biggest).
If doing that would make the number of nodes “above” bigger than n/2, stop, otherwise continue with that child.
This algorithm should be O(log n) if the tree is reasonably balanced and we have sizes of subtrees precomputed for each node. If one of those conditions doesn't apply, it would be O(n).
One exact algorithm is as this,
Start from leafs and create disjoint graphs (in fact all are K1), in each step find the parent of this leafs, and merge them into new tree, in each step if node x has r known child and degree of node is j such that j = r+1 , simply a node which is not in child node of x is parent of current node in this case we say node x is nice , else, there are some child such that related rooted subtree of them not constructed, in this case we say the node x is bad .
So in each step connect nice nodes to their related parent, and it's obvious each step takes sum of {degree of parent nice nodes} also in each step you have at least one nice node (cause you start from leaf), So the algorithm is O(n), and it will be done completely, but for finding node which should be removed, In fact in each step is required to check size of a dijoint list (subtree lists), this can be done in O(1) in construction, Also if the size of list is equal or bigger than n/2, then select related nice node. (in fact find the nice node in minimum list which satisfies this condition).
Obvious thing is that if is possible to divide tree in good way (each part has at most n/2 node) you can done it by this algorithm, but if is not so ( in fact you cant divide it in two or more part of size smaller than n/2) this gives you good approximation for it. Also as you can see there is no assumption in input tree.
note: I don't know is possible to have a tree such that it's impossible to partition it into some parts of size smaller than n/2 by removing one node.
This problem seems similar to finding the center of mass of an object. Assume each of your nodes is a point mass of equal mass (weight) and its position is given by the position in the graph. Your algorithm tries to find the center of mass, ie the node that has a similar accumulated weight of nodes in all connected sub-trees.
You may compute the accumulated weights on all sub-trees for each node. Then choose the one that is most balanced, st no sub-tree weighs more than n/2 . Probably this is a task for some dynamic programming.
上一篇: 我如何在Linux中重新启动IDLE Python Shell？
下一篇: 图论