# Tree graph restructuring.

I have a graph $G(V,E)$ and a tree $T(V',E')$ where $|V|=|V'|$ and $T$ is isomorphic to a subgraph of $G$. In other words I found a spanning tree of $G$ and made one of its nodes act as the root.

I now have 2 problems I want to look at:

1. If I remove a node from $G$ what is the optimal way to determine if a new $T$ exits and if so find it. 2.Assume $v_0$ is the root of $T$. I'm given an arbitrary node $v_i$ and need to find a new $T$ in which $v_i$ is the root.

I would like to know what (if any) literature or solutions already exist for these problems?

I am asking this question because I am working on a project involving network topologies and would like to know about any existing solution (especially if they have proofs) before I start trying to solve the problem on my own.

-

The case where the existing root is not being deleted is straightforward: simply reverse the parent-child relationship between the new node and its extant parent. The new root and the old root cannot share any descendants, because then there would have been a cycle in the tree. In the directed case, add a path from $v_i$ to $v_o$ to $T$, remove the link from the parent of $v_i$ to $v_i$ and break any cycles created. – Chad Musick Oct 9 '11 at 20:42