Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - tree related question ...

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    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 ?
    Attached Thumbnails Attached Thumbnails tree related question ...-undirected-tree.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: tree related question ...

    Quote Originally Posted by iwan1981 View Post
    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?
    Attached Thumbnails Attached Thumbnails tree related question ...-tree.jpg  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related question ...

    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!
    Attached Thumbnails Attached Thumbnails tree related question ...-undirected-tree2.jpg  
    Last edited by iwan1981; July 10th 2011 at 01:22 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: tree related question ...

    Quote 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related question ...

    Quote Originally Posted by emakarov View Post
    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 ...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: tree related question ...

    Quote Originally Posted by iwan1981 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related question ...

    Quote Originally Posted by emakarov View Post
    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,
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: tree related question ...

    I think we should consider using Cayley's theorem.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related question ...

    Quote Originally Posted by Also sprach Zarathustra View Post
    I think we should consider using Cayley's theorem.
    Ok that goes to deep for me ... what is "Cayley's theorem???"
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: tree related question ...

    Quote 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.

    Quote 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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related question ...

    Quote Originally Posted by emakarov View Post
    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 ...
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: tree related question ...

    Quote Originally Posted by iwan1981 View Post
    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 ...
    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related 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?
    Attached Thumbnails Attached Thumbnails tree related question ...-undirected-tree2.jpg  
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: tree related question ...

    Quote Originally Posted by iwan1981 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    Re: tree related question ...

    Quote Originally Posted by Plato View Post
    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,
    Attached Thumbnails Attached Thumbnails tree related question ...-undirected-tree3.jpg  
    Last edited by iwan1981; July 11th 2011 at 07:35 AM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 07:40 PM
  2. question about graphs / undirected tree
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 13th 2011, 12:58 PM
  3. Another tree diagram question
    Posted in the Statistics Forum
    Replies: 4
    Last Post: May 15th 2009, 05:43 AM
  4. Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2008, 02:17 AM
  5. Spanning tree question.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 7th 2007, 06:01 PM

Search Tags


/mathhelpforum @mathhelpforum