Results 1 to 7 of 7

Thread: [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 $\displaystyle \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 $\displaystyle \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: Nov 9th 2009, 07:10 AM
  3. [SOLVED] Graph Theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 11th 2007, 12:46 AM
  4. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 8th 2007, 12:29 AM
  5. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 29th 2007, 02:28 AM

Search Tags


/mathhelpforum @mathhelpforum