Thread: tree related question ...

I have a tree (see the attachment)

=================
Now the question is:
"How many non-isomorphic "rooted-trees" can be created from this tree by choosing the appropriate root?"
=================

Does anyone have an idea?

I mean are we allowed to break this tree apart? and create little trees ?

Originally Posted by iwan1981

I have a tree (see the attachment)

=================
Now the question is:
"How many non-isomorphic "rooted-trees" can be created from this tree by choosing the appropriate root?"
=================

Does anyone have an idea?

I mean are we allowed to break this tree apart? and create little trees ?

No, you can't introduce any breaks. What you can do is to twist or turn the branches so as to change the shape of the tree.

The root has to come at the end of one of the branches. So there are nine possible choices of root (see the attachment). That gives you nine possible rooted trees. But some of them are isomorphic. For example, the tree with vertex 2 as its root is isomorphic to the tree with vertex 5 as its root, because you can get from one to the other by twisting those two branches so that they swap positions. Similarly, the trees with roots at 6, 7 and 8 are all isomorphic. Are there any other isomorphisms among these trees?

Thanks for your reply!

Are there any other isomorphisms among these trees?

Well as you said yourself:
- 2 and 5 are isomorpic
- 6, 7 and 8 are all isomorpic as well

- 4 and 9 are isomorphic as well ...
- as mentioned before ... 2 and 5 where isomorphic but I think I have to add 1 to that so 1, 2 and 5 are isomorphic.

So with your explanation I think I have found the answer ...
We can create 9 rooted trees (as you said yourself) and from those 9 there are only 1 non-isomorphic.
This is with vertex 3.

This is correct right?

and if I slightly adjust the tree like the new attachment (I have added a new vertex below (lets say that's vertex 10)) ... we can still create 1 non-isomorphic trees right?
Because 4, 10 and 9 are isomorphic with each other ...
ANd with introducing this new vertex "10" we also introduce an extra option that 1 and 10 are isomormic right?

I hope I grasp the idea and that I am right?
Almost starting to like it :-)

Thanks!

Originally Posted by Opalg

The root has to come at the end of one of the branches.

Not necessarily; any vertex can be a root.

Originally Posted by emakarov

Not necessarily; any vertex can be a root.

yes ... but a root need to have an outdegree of 1 and an indegree of 0 right? So not any vertex can be the root ...

Originally Posted by iwan1981

yes ... but a root need to have an outdegree of 1 and an indegree of 0 right? So not any vertex can be the root ...

I am not aware of a definition of a rooted tree that requires this. The definitions I encountered allowed any outdegree.

Originally Posted by emakarov

I am not aware of a definition of a rooted tree that requires this. The definitions I encountered allowed any outdegree.

Ok ... I am confused then .... but lets just say that the tree I have drawn ...
That the Root should have an indegree of 0 and on outdegree of 1 ... then my answer is still correct that we can only create 1 non-isomorphic tree right?

Thanks,

I think we should consider using Cayley's theorem.

Originally Posted by Also sprach Zarathustra

I think we should consider using Cayley's theorem.

Ok that goes to deep for me ... what is "Cayley's theorem???"

Originally Posted by Also sprach Zarathustra

I think we should consider using Cayley's theorem.

I don't see how Cayley's formula is applicable because it talks about all possible trees on n vertices, not rooted trees derived from a given tree.

Originally Posted by iwan1981

We can create 9 rooted trees (as you said yourself) and from those 9 there are only 1 non-isomorphic.
This is with vertex 3.

The adjective "non-isomorphic" cannot be applied to just one tree. It is NOT the case that a tree is non-isomorphic if no other trees are isomorphic to it. Rather, the question is asking to find a set of trees that a pairwise non-isomorphic. For example, trees with root 1 and 3 are non-isomorphic because they have a different path length from the root to the vertex with three leaves.

Originally Posted by emakarov

I don't see how Cayley's formula is applicable because it talks about all possible trees on n vertices, not rooted trees derived from a given tree.

The adjective "non-isomorphic" cannot be applied to just one tree. It is NOT the case that a tree is non-isomorphic if no other trees are isomorphic to it. Rather, the question is asking to find a set of trees that a pairwise non-isomorphic. For example, trees with root 1 and 3 are non-isomorphic because they have a different path length from the root to the vertex with three leaves.

So vertex 1 would be an option ... and vertex 3 would be one ... but vertex 10 (or 4 of 9) could be one as well...?
So the count is 3 now ...

Originally Posted by iwan1981

yes ... but a root need to have an outdegree of 1 and an indegree of 0 right? So not any vertex can be the root ...

Originally Posted by emakarov

Not necessarily; any vertex can be a root.

That is true.
This particular graph is non-directed. Therefore the terms indegree or outdegree do not apply. Now definitions do vary from text to text. But I think it is safe to say that generally a rooted tree is one in which a root is specified (in a directed graph the root does have an indegree of zero). Now turn to the question of isomorphic rooted trees. It is true that in a non-directed tree any vertex can be specified root. Because any graph is isomorphic to itself what sense would it make to ask about isomorphic rooted tree in a given graph? Well Richard Johnsonbaugh makes the following distinction: Two rooted trees are isomorphic if and only if the trees are isomorphic and the roots have the same degree.

Again, that may not agree with that definition in the text from which the OP was taken. But if we use Johnsonbaugh’s definition we can easily answer this question.

Again, that may not agree with that definition in the text from which the OP was taken. But if we use Johnsonbaugh’s definition we can easily answer this question.

and what would that be then if we look at the tree in the attachment?

Originally Posted by iwan1981

and what would that be then if we look at the tree in the attachment?

Any vertex can be a root. If two vertices have the same degree then they are roots of isomorphic rooted trees. So how many vertices have different degrees?

Originally Posted by Plato

Any vertex can be a root. If two vertices have the same degree then they are roots of isomorphic rooted trees. So how many vertices have different degrees?

I just numbered them ... to make it more clear to specify the vertexes that we are talking about ...

Are you talking about vertices that are connected to each other?

If that is the case ... then I would say that
- vertices 1, 2, 3 and 4 can be used to create a non isomorphic tree
- vertices 6 and 5 can also be used to create a non isomorphic tree

So I count "6" in total ... can someone confirm this?

Thanks,