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!

## graph problems

**Moderator:** Board moderators

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.

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
```