Define bipartite graph. Also given an example of it, where do you use this type of graph.

Bipartite Graphs are those which have two sets of vertices which are mutually disjoint . The Relation or edges in these graphs exists only between two vertices which are not from the same set of vertices. 

Famous example :
Assigning n jobs to m persons can be modelled using  a Bipartite Graph..
The edge exists if a job i can be allotted to a person p.

Obviously this requires a Bipartite model of graph, Since an edge here can not exist between a job to another job or a person to another person.

No comments

Powered by Blogger.