Results 1 to 7 of 7

Math Help - [SOLVED] Graph Theory Question - Totally stumped

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    12

    [SOLVED] Graph Theory Question - Totally stumped

    Hey guys,

    I'm working on a Discrete Math assignment and I came across a graph theory question that has me thinking "what?!" I would appreciate some help getting the answer. It might be easy, but I just can't think of it.


    Question:

    There are ________ non-isomorphic rooted trees with five vertices.


    Any and all help is greatly appreciated!

    Thanks guys and gals!
    Last edited by MathHelp12345; May 12th 2010 at 09:46 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathHelp12345 View Post
    Hey guys,

    I'm working on a Discrete Math assignment and I came across a graph theory question that has be thinking "what?!" I would appreciate some help getting the answer. It might be easy, but I just can't think of it.


    Question:

    There are ________ non-isomorphic rooted trees with five vertices.


    Any and all help is greatly appreciated!

    Thanks guys and gals!
    Maybe you're confused by the non-isomorphic part. It means, how many rooted trees with five vertices exist that are distinct up to isomorphism? So, just try to draw them all.

    Edit: Actually, there seem to be quite a few, but I think you can count them without enumerating them by dividing into subtrees.

    Edit 2: I had accidentally started drawing trees with 6 vertices and overestimated the count. 5 isn't too bad.
    Last edited by undefined; May 12th 2010 at 09:23 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    12
    Quote Originally Posted by undefined View Post
    Maybe you're confused by the non-isomorphic part. It means, how many rooted trees with five vertices exist that are distinct up to isomorphism? So, just try to draw them all.

    Edit: Actually, there seem to be quite a few, but I think you can count them without enumerating them by dividing into subtrees.

    Edit 2: I had accidentally started drawing trees with 6 vertices and overestimated the count. 5 isn't too bad.

    Thanks for the help! So what you're saying it's just asking how many ways can a tree with 5 vertices be drawn? If so, I'm assuming there is a formula for this, and not just the brute force method. Do you, or anyone else know what this formula might?

    EDIT: Okay so I looked around and I think I found the answer, but I'm not entirely sure. The non-isomorphic part is still throwing me off a little bit. If i'm looking at this question correctly for 3 vertices the answer would be 5, the answer for 4 vertices would be 14, and for the 5 vertices question the answer would be 42?

    However! Would non-isomorphic mean the same thing as "structurally different"? In that case the answer for 5 vertices would be 6, correct?

    EDIT 2: Actually, I'm now quite certain the answer is 3.
    Last edited by MathHelp12345; May 12th 2010 at 10:01 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathHelp12345 View Post
    Thanks for the help! So what you're saying it's just asking how many ways can a tree with 5 vertices be drawn? If so, I'm assuming there is a formula for this, and not just the brute force method. Do you, or anyone else know what this formula might?

    EDIT: Okay so I looked around and I think I found the answer, but I'm not entirely sure. The non-isomorphic part is still throwing me off a little bit. If i'm looking at this question correctly for 3 vertices the answer would be 5, the answer for 4 vertices would be 14, and for the 5 vertices question the answer would be 42?

    However! Would non-isomorphic mean the same thing as "structurally different"? In that case the answer for 5 vertices would be 6, correct?

    EDIT 2: Actually, I'm now quite certain the answer is 3.
    I'm not sure what you're counting, but I got 9, and I confirmed my answer with OEIS, sequence A000081.

    If you'd like me upload an image, I can make one, just post a reply.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2010
    Posts
    12
    Quote Originally Posted by undefined View Post
    I'm not sure what you're counting, but I got 9, and I confirmed my answer with OEIS, sequence A000081.

    If you'd like me upload an image, I can make one, just post a reply.
    I've been looking it up on various sites and everywhere seems to think the answer is 3. A non-isomorphic tree is a tree that is totally different, meaning it is not the same tree just drawn a different way.

    Thus the answer should be, if I'm doing it correctly:

    --*--*--*--*--*

    *
    |
    --*--*--*
    |
    *

    *
    |
    *--*--*
    |
    *

    This last one cannot be drawn right because it wont let me add spaces, but the two edges leading up and down at the beginning should be over the middle V


    Sorry for the poorly drawn trees but '*' is a vertex and '--' is an edge.

    http://www.maths.usyd.edu.au/u/sandr...009/t04sol.pdf

    EDIT: Now that I think about it these trees aren't rooted. 9 very well may be the answer, could you show me a picture of that please?
    Last edited by MathHelp12345; May 12th 2010 at 10:36 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MathHelp12345 View Post
    I've been looking it up on various sites and everywhere seems to think the answer is 3. A non-isomorphic tree is a tree that is totally different, meaning it is not the same tree just drawn a different way.

    Thus the answer should be, if I'm doing it correctly:

    --*--*--*--*--*

    *
    |
    --*--*--*
    |
    *

    *
    |
    *--*--*
    |
    *

    This last one cannot be drawn right because it wont let me add spaces, but the two edges leading up and down at the beginning should be over the middle V


    Sorry for the poorly drawn trees but '*' is a vertex and '--' is an edge.

    http://www.maths.usyd.edu.au/u/sandr...009/t04sol.pdf
    Keep in mind we are dealing with rooted trees. And a way to enter in text with spaces is to enclose the text in [ code][ /code] tags (without spaces).

    Here's a diagram



    (a bit ugly since I made it in MS Paint w/ a mouse - but don't knock it because it took some time to make!)

    On the second line I demonstrate what isomorphic equivalence refers to, using the \equiv symbol to indicate equivalence.

    Note how the last graph on the third line and the last graph on the last line would be equivalent if we were dealing with non-rooted trees... but we're not.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2010
    Posts
    12
    Quote Originally Posted by undefined View Post
    Keep in mind we are dealing with rooted trees. And a way to enter in text with spaces is to enclose the text in [ code][ /code] tags (without spaces).

    Here's a diagram



    (a bit ugly since I made it in MS Paint w/ a mouse - but don't knock it because it took some time to make!)

    On the second line I demonstrate what isomorphic equivalence refers to, using the \equiv symbol to indicate equivalence.

    Note how the last graph on the third line and the last graph on the last line would be equivalent if we were dealing with non-rooted trees... but we're not.
    Thank you! About two seconds ago it just occurred to me that those trees aren't rooted! I edited my previous post, but I did it at about the same time you posted this.

    9 is the answer.

    Thanks for the help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Graph Theory Question - Vertices
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 13th 2010, 07:47 AM
  2. [SOLVED] Graph Theory and Labeled Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2009, 07:10 AM
  3. [SOLVED] Graph Theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 11th 2007, 12:46 AM
  4. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2007, 12:29 AM
  5. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 29th 2007, 02:28 AM

Search Tags


/mathhelpforum @mathhelpforum