Subtree definition

3.2k Views Asked by At

The definition of subtree of a tree is a tree that descends from a node of the starting tree. My question is if we can consider the "cross tree" below and say that the graph starting from $A$, going to the red node and branching toward $C$ and $D$ is a subtree of the previous cross tree or if the only subtree is the one starting from the red node. I have some confusions about the definition of subtree. Thanks!

enter image description here

2

There are 2 best solutions below

1
On BEST ANSWER

Everything depends from what vertex is a root. Guess that exactly $A$ is a root and guess that red vertex is called $E$ $\implies$ $\text{subtrees}$={$CE$, $ED$, $CED$, $CEB$, $BED$, $AEC$, $AEB$, $AED$, $AECD$, $AEBD$, $AEBC$, $AEBCD$} are a subtrees of the presented tree by you.

Also I can provide other images describing a definition subtree:

enter image description here

or

enter image description here

or

enter image description here

6
On

It depends on the precise definition of a tree.

If a tree is an unoriented, simple graph, which is connected and doesn't have loops, then a subtree is just a connected subgraph. In this case, the subgraph you describe is a subtree.

If a tree is an oriented, simple graph, such that the underlying unoriented graph is connected and doesn't have loops, and you define a subtree (associated to some vertex $x$) to be the set of vertices $y$ such that there exists a finite sequence of oriented arrows such that each starts where the one before ends, such that the first one begins at $x$, and the last ends at $y$, then whether the subgraph you describe is a subtree or not depends on the orientation you choose on the edges.

There are also definitions of rooted trees: these are trees with a distinguished vertex. There are probably definitions of subtrees in rooted trees that specify the subtree to share the root with the tree... I don't know really.

In conclusion, you check the precise definition of the words "tree" and "subtree" in the reference you are using.