1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Connected Components in Graph Theory

  1. Mar 1, 2013 #1
    1. The problem statement, all variables and given/known data

    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?

    2. Relevant equations



    3. The attempt at a solution

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

    Thanks a lot.

    Assaf
     
  2. jcsd
  3. Mar 1, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Can you think of a useful number (or pair of numbers, perhaps) you could associate with each vertex?
     
  4. Mar 2, 2013 #3
    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.
     
  5. Mar 2, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    My method doesn't beat O(v^2), but it's easy to describe. Remove all vertices degree 1. Repeat until only 1 or 2 vertices left. Pick any of those.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Connected Components in Graph Theory
  1. The graph is connected (Replies: 4)

Loading...