Results 1 to 4 of 4

Math Help - question about graphs / undirected tree

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    66

    question about graphs / undirected tree

    Hi,

    I am a little bit stuck in understanding this question ....
    Can someone please help me with this and explain how I find the answer?

    "In a directed graph every vertex has an "in-degree" and an "out-degree".
    The "in-degree" is the number of heads of edges (arrows) adjacent to a vertex, and the "out-degree" is the number of tails of edges adjacent to a vertex.
    A tree is called a "rooted tree" if one vertex has been designated the root, which by definition must have an in-degree of 0 and an out-degree of 1.
    All the other vertices must have an in-degree of 1.
    Below is given an undirected tree. How many non-isomorphic "rooted trees" can be created from this tree by choosing an appropriate root?"




    I would say you can create "10" trees here ... because there are 10 points where you can create a root of.
    I just don't get the "non-isomorphic "rooted trees" part here ... kind of confuses me ...

    Or is the answer "5" because I can only pick the vertices that are on "on the "left sides" and the vertices that are starting from below?

    Or is the answer "1" because there is no way you can redraw this tree in another way?

    Or is the answer 106 ... that we need to try to create a tree and see how many combinations is possible with 10 vertices?

    I am kind of confused here ...

    Thanks,
    Last edited by iwan1981; June 12th 2011 at 03:16 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    Do you know what a graph isomorphism is ?

    Here is an easy one to check your understanding:

    How many non-isomorphic spanning trees does this graph have ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2011
    Posts
    66
    isomorphism is that you can create a different shape of the graph by just only moving the vertices.
    So you have 2 different shapes (graphs) for the eye ... but if you move the vertices around you can move back and forward between the 2 graphs:
    example: with pictures I found here --> Graph isomorphism - Wikipedia, the free encyclopedia

    And I have no clue what the answer is to your question ... maybe you can explain that ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: question about graphs / undirected tree

    Quote Originally Posted by iwan1981 View Post
    I would say you can create "10" trees here ... because there are 10 points where you can create a root of.
    Can't you make each of the 14 vertices a root? Many of the resulting trees will be isomorphic, though.

    I just don't get the "non-isomorphic "rooted trees" part here ... kind of confuses me ...
    You need to find the number of rooted trees such that there is no isomorphism between any pair of them. If you understand isomorphism, the question should be clear. I assume that we are considering unordered trees, i.e., one can change the order of children of any vertex without making it a different tree. This is important for seeing that the trees with the root in the leftmost vertex and in the topmost vertex are isomorphic.

    I see 4 non-isomorphic trees rooted at the leftmost vertex, second left, central bottom and the one just above it, but this needs to be double-checked.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 14th 2011, 11:31 PM
  2. tree related question ...
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 10th 2011, 11:55 PM
  3. Cycles in an undirected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 12:30 AM
  4. Another tree diagram question
    Posted in the Statistics Forum
    Replies: 4
    Last Post: May 15th 2009, 05:43 AM
  5. Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2008, 02:17 AM

Search Tags


/mathhelpforum @mathhelpforum