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.