Bipartite Graph — [Notes]

· Bipartite Graph
· Application

Bipartite Graph

A bipartite graph is one whose vertices can be split into two independent groups U, V such that every edge connects between U and V.

Other definitions exist such as:
The graph is two colorable or there is no odd length cycle.

Source — https://youtu.be/eQA-m22wjTQ

Application

• FAQ — What is the maximum matching we can create on a bipartite graph? Suppose white nodes are jobs and red nodes are people then we can ask how many people can be matched to jobs in this

Suppose white nodes are jobs and red nodes are people then we can ask how many people can be matched to jobs in this

• The bipartite graph also creates a critical role in the field of network flow

The bipartite graph also creates a critical role in the field of network flow