## graph problems

Moderator: Board moderators

minton3
New poster
Posts: 3
Joined: Fri Sep 01, 2006 5:36 pm

### graph problems

HI!
My first problem is to know if a graph is bipartite in the fastest way.
I don't know any algorithm in particular to do it...and I think I can do it in the best way in O(n), or I hope so, but if someone knows a method or a good algorithm it would be nice to know it.
The second problem is this:
I have 1 graph, and I want to divide it in 2 diferent groups of nodes, in such a way that the amount of conected nodes between the first group and the second is maximum... I hope you understand my bad description.
In another way to see this problem, just think in a group of people where some of them are friends. And I want to divide it in 2 teams such that the amount of pairs of friends between 1 team and another is maximum.
I would appreciate any help!

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
Checking if a graph is bipartite is basically checking if a graph can be 2-colored.

This can be done with DFS in linear time.

I'm not really sure what your second problem is, but it sounds like the Maximum Cut problem which is NP-hard.

A simple 2-approximation heuristic is simply to assign nodes in an arbitrary order, and each time assign a node to the side with which he forms the most pairs with the other side.

minton3
New poster
Posts: 3
Joined: Fri Sep 01, 2006 5:36 pm
Checking if a graph is bipartite is basically checking if a graph can be 2-colored.

This can be done with DFS in linear time.
thanks
But can you explain me a little more please?
I am not sure how to do it in linear time

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
Color every node using DFS as "black" or "white".

Color the root black, make it the current node, and do the following:

Code: Select all

``````For every node connected to the current node
If node is uncolored
Color it with the opposite color of the current node
Recursively do a DFS on it
Else If node is colored the same color as the current node
Graph is not Bipartite
exit
``````
If an adjacency list representation is used, the running time is O(V+E) which is linear in the number of vertices and edges.

minton3
New poster
Posts: 3
Joined: Fri Sep 01, 2006 5:36 pm
thanks a lot for your help
it was very useful

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
Hi,
How to solve the 10505(Montesco vs Capuleto)?
Is it the Bi-coloring problem? and can be done with DFS in linear time?

thnx