Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By MooMooMoo

Math Help - Connected Components in Graph Theory

  1. #1
    Member
    Joined
    May 2008
    Posts
    171

    Connected Components in Graph Theory

    Hey guys,

    I have this question.

    Given a tree T = (V , F), find an algorithm which finds u in V, so in the graph T = (V \ {u} , F) the size of each connected component is |V| / 2 at most. What is the complexity?

    I need to split this tree down the middle somehow, any idea?

    Thanks a lot.

    Assaf
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2013
    From
    Washington
    Posts
    9
    Thanks
    2

    Re: Connected Components in Graph Theory

    G is bipartite since it is a tree. Try to separate the two vertex sets and look at the edges that join them. Once you do that you should be able to count edges really easily using a pile of different algorithms.

    You need an algorithm to find out what it's algorithmic complexity is. But this problem is definitely polynomial.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    171

    Re: Connected Components in Graph Theory

    Ok, so I did the following:

    I woluld first use BFS algorithm (it has to be run for each verticle) for computng shortest distances between all pairs of verticles. Then for each verticle V find Vm - the largest distance to any other verticles amongs the data retuirned form BFS. Then, the verticles with the smallest Vm are the one in the graph center.

    It comes down to O(V^2), any thing better then that?

    Thanks a lot.

    Assaf.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2013
    From
    Washington
    Posts
    9
    Thanks
    2

    Re: Connected Components in Graph Theory

    Hi Assaf,

    O(V^2) is pretty good. I'm glad you got it worked out!
    Thanks from asi123
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What is a simply connected and 4-connected graph?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2012, 11:18 AM
  2. k-connected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2010, 05:26 PM
  3. How many connected components does this graph contain?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 02:09 PM
  4. Path connected components.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 22nd 2009, 05:46 AM
  5. Connected components.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 18th 2007, 07:50 PM

Search Tags


/mathhelpforum @mathhelpforum