Results 1 to 6 of 6

Math Help - [SOLVED] Graph Theory Question - Vertices

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    12

    [SOLVED] Graph Theory Question - Vertices

    Hello guys,

    I have a question concerning the relationship between vertices in a full binary tree and the internal vertices in a full binary tree. I'm assuming there is a formule for this problem, but I have been unable to locate it.

    Thanks for the help, I really need to solve this question:

    If a full binary tree has 231 vertices, then it has ____ internal vertices.


    Thanks guys and gals!
    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
    Hello guys,

    I have a question concerning the relationship between vertices in a full binary tree and the internal vertices in a full binary tree. I'm assuming there is a formule for this problem, but I have been unable to locate it.

    Thanks for the help, I really need to solve this question:

    If a full binary tree has 231 vertices, then it has ____ internal vertices.


    Thanks guys and gals!
    The definition of full binary tree is "a tree in which every node other than the leaves has two children" (Wikipedia). If you draw them on paper, you will notice that you start out with just one vertex, which we can call a leaf, then after that each leaf creates two new leaves while becoming itself an internal vertex. So, each time you add two branches to a leaf, you destroy one leaf and create two more. The overall effect is that the number of leaves is always one greater than the number of internal vertices. So, we could write

    n + (n+1) = 231
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    12
    Quote Originally Posted by undefined View Post
    The definition of full binary tree is "a tree in which every node other than the leaves has two children" (Wikipedia). If you draw them on paper, you will notice that you start out with just one vertex, which we can call a leaf, then after that each leaf creates two new leaves while becoming itself an internal vertex. So, each time you add two branches to a leaf, you destroy one leaf and create two more. The overall effect is that the number of leaves is always one greater than the number of internal vertices. So, we could write

    n + (n+1) = 231

    Thanks for your help again!

    If I'm understanding this correctly the work and answer is as followed:

    n vertices has i = (n-1)/m

    i = (231-1)/2 => 115.
    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 your help again!

    If I'm understanding this correctly the work and answer is as followed:

    n vertices has i = (n-1)/m

    i = (231-1)/2 => 115.
    I think the "m" is supposed to be a 2? Anyway, that's what I get too.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2010
    Posts
    12
    Quote Originally Posted by undefined View Post
    I think the "m" is supposed to be a 2? Anyway, that's what I get too.
    Yep! The 'm' is the m-ary tree, which in this case is 2.

    Thanks for your help!
    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
    Yep! The 'm' is the m-ary tree, which in this case is 2.

    Thanks for your help!
    Oh, good call! Didn't think of that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Graph Theory Question - Totally stumped
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 12th 2010, 10:38 PM
  2. colouring vertices in graph theory
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 3rd 2009, 03:53 PM
  3. Coloring Vertices in Graph Theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 06:04 AM
  4. Replies: 5
    Last Post: June 22nd 2008, 10:20 PM
  5. [SOLVED] Graph Theory
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 11th 2007, 12:46 AM

Search Tags


/mathhelpforum @mathhelpforum