Bipartite Graph:

bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V₁ and V₂ such that Edge  (u, v) E implies .either (u in V₁ and v in V₂₎ or (u in V₂  and v in V₁₎. That is, all edges go between the two sets V₁ and V2 and no edge is present containing only V1 or V2 vertices

Algorithm to prove if a graph is bipartite ?

The idea is to start by placing a random node into a FIFO queue . Color it blue. Then repeat following while there are nodes still left in the queue.

dequeue an element. Color its neighbors with a different color than the extracted element and insert (enqueue) each neighbor into the FIFO queue. For example, if you dequeue (extract) an element (node) colored red, color its neighbors blue. If you extract a blue node, color its neighbors red.

If there are no coloring conflicts, the graph is bipartite. If you end up coloring a node with two different colors, than it’s not bipartite.
This approach would  only work for connected graphs. However, you can apply the same algorithm on each connected component to make it work for any graph.

Modified BFS approach :

To determine if a graph G = (V, E) is bipartite, we perform a BFS on it with a little modification such that whenever the BFS is at a vertex u and encounters a vertex v that is already ‘gray’ our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite. Note that this modification does not change the running time of BFS and remains O(V + E).

Simply what it means is start from any vertex of graph and color it black , and check its neighbor, if its not yet colored color it with opposite color (neighbor of black would be colored white and neighbor of white as black ). So if at any point en edge is seen between two identical color then its not a bipartite graph

Triangle is not bipartite but a quad is bipartite

Applications:

1 Job recruitment process:

Suppose there are ‘n’ companies competing to hire students from a university, and that ‘m’ students are available for hiring. Assume that each company has only one job opening, and hence can hire at most one student.

After the tests and interviews, each company shortlists certain candidates. The company sees no distinction among its shortlisted candidates, and is willing to hire any one of them to fill its opening.

So its a problem of bipartite matching.

Let L be the set of companies, and R be the set of students.

An edge exists if r is one of the candidates shortlisted by the company.

Each company can hire at most one (either it hires a student, or goes home empty-handed.)

Obviously, each student can work in at most one company (either the student is selected by one company; or goes home empty-handed.)

Hence, this is a case of bipartite matching between the set of companies and the set of students.

The university would certainly like to find out the maximum number of students who can get placed through this recruitment process.

In other words, the university wishes to find out the size of the maximum bipartite matching possible for the company-student graph.

There exist polynomial time algorithms for computing a maximum bipartite matching. Hence, the problem can be solved by running any of those algorithms on the given instance of the company-student graph.

2. Link Prediction:

One of the most interesting challenges associated with social media is predicting which user is expected to comment on which blog. This can be  formulated as a link prediction problem in bipartite graphs. Recently, sparse matrix factorization became popular for link prediction. Therefore, we can apply matrix factorization to predict which user is expected to comment which blog.