vertexCut -- break up a tree at a vertex

Synopsis

• Usage:
vertexCut(T,e,l,newl)
vertexCut(T,E,l,newl)
• Inputs:
• T, an instance of the type LeafTree,
• e, a set, an edge specified by the set of leaves on one side of it
• E, a list, an edge specified by a list of the leaves on one side of it
• l, , a leaf of the tree
• newl, , the label for a new leaf
• Outputs:

Description

Vertices of a tree of class LeafTree do not have explicit names. Therefore a vertex v is specified by naming an edge e incident to v, and leaf l on the opposite side of the edge as v.

The function outputs the subtrees of T obtained by deleting the vertex v from T and then re-adding v to each of the resulting subtrees as a new leaf. The new leaf on each subtree is adjacent to the edge previously adjacent to v on T. Each subtree has a copy of the vertex labeled newl, but their edge sets form a partition of the edge set of T.

Each subtree in P has one leaf that was not a leaf of T, and therefore previously unlabeled. The label for this new leaf is input as newl.

 i1 : T = leafTree(4,{{0,1}}) o1 = {{0, 1, 2, 3}, {set {0, 1}, set {0}, set {1}, set {2}, set {3}}} o1 : LeafTree i2 : P = vertexCut(T, set {0,1}, 0, 4); i3 : P#0 o3 = {{2, 4}, {set {2}}} o3 : LeafTree i4 : P#1 o4 = {{3, 4}, {set {3}}} o4 : LeafTree i5 : P#2 o5 = {{0, 1, 4}, {set {0}, set {1}, set {4}}} o5 : LeafTree