Results 1 to 8 of 8

Math Help - Central and Bicentral vertex in graph

  1. #1
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54

    Central and Bicentral vertex in graph

    How do i prove that tree has exactly one center vertex or possibly 2 (bicentral) if the two are neighbour vertexes, i need unformal prove if possible, thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1
    Quote Originally Posted by goroner View Post
    How do i prove that tree has exactly one center vertex or possibly 2 (bicentral) if the two are neighbour vertexes, i need unformal prove if possible.
    This is certainly no proof. I can give you a method of finding the center (bicenter) of a tree.

    Suppose that n>2.
    First, remove all vertices of degree one along with any incident edges.
    We still have a tree remaining. If the number of remaining vertices is more than two, then repeat the process.
    If the number of remaining vertices is two you have a bicenter; if it is one you have the center.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    the algorithm is ok ill check it, just one quick question, in the recurrent steps do i check if i got more then two vertices of degree one to continue with the process or it's about all degree vertices, thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1
    Quote Originally Posted by goroner View Post
    the algorithm is ok ill check it, just one quick question, in the recurrent steps do i check if i got more then two vertices of degree one to continue with the process or it's about all degree vertices, thanks!
    I don't know exactly what that means.
    The idea is to work the tree down until one vertex or two vertices of degree one remain.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    i meant when i firstly start, i see all the leafs and get them off the tree altogether with the edges incident with those vertices, now i got new leafs cause previously i deleted the edges that were connecting these new leafs with the vertices that previously were leafs, so now i check if my tree contains two or less vertices if so i stop and i conclude that if there's two vertices one of those could be either center or bicenter vertex (one or another bout cold permute the role), if previously the condition does not hold that means i must continue to remove leafs altogether with the edges incidenting those leafs, eventually ill end up with tree with 1 or 2 vertex. Is that what you talked about?
    My question up there was: in the step when you check if in the tree exists more than two vertices, do you check for vertices with degree one, or you check for vertices no matter the degree they got, but it is clear to me now so thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1
    You keep removing leafs and their stems, removing all on the same level, until there remains only one vertex, there remains two vertices of degree one.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    as i noted, i always get the root to be one of the vertices to be center/bicenter isn't obvious that i can pick the root and one of it's children as the vertices i look for, cause in a rooted tree if you keep on removing the leafs you will eventually end up with the root and one child to it..
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2010
    From
    Skopje
    Posts
    54
    as i told you, the root is the central node always, cause if you just take the tree and redraw it with that all of the child nodes of his you put around him evenly, you will note that the root is actually the center of the graph hence it's central node, and as i told you you can take one of his children randomly and assign it as bicenter node that's it, is just an eye to see it =), thanks anyway!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] graph vertex colouring
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2010, 10:46 AM
  2. vertex basis for the graph
    Posted in the Geometry Forum
    Replies: 2
    Last Post: June 7th 2010, 03:58 AM
  3. n-vertex graph
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 25th 2009, 10:37 AM
  4. Finding the vertex of the parabolic graph
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 28th 2008, 02:15 PM
  5. How to find vertex of a graph or equation
    Posted in the Calculus Forum
    Replies: 14
    Last Post: June 6th 2008, 07:57 PM

Search Tags


/mathhelpforum @mathhelpforum