A
bipartite graph is a graph (in the
graph theory sense) where the vertices can be divided into two sets A and B, where every
vertex in A does not have an edge to any other vertex in A, and any vertex in B does not have an edge to any other vertex in B.
Bipartite graphs are used to solve a number of matching problems, such as maximizing matches of jobs to workers, and classes to classrooms.