World's most popular travel blog for travel bloggers.

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

, , No Comments

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.

0 comments:

Post a Comment

Let us know your responses and feedback