# Connected Components in Graph Theory

• Mar 1st 2013, 08:23 AM
asi123
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
• Mar 2nd 2013, 01:12 AM
MooMooMoo
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.
• Mar 2nd 2013, 03:38 AM
asi123
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.
• Mar 2nd 2013, 10:14 AM
MooMooMoo
Re: Connected Components in Graph Theory
Hi Assaf,

O(V^2) is pretty good. I'm glad you got it worked out!