Bipartite Graphs
A bipartite graph is a graph whose vertex stet can be partitioned into two sets $X$ and $Y$, such that every edge joins a vertex in $X$ to a vertex in $Y$:
graph LR
x1 ------ y1 & y2
x2 ------ y1 & y3 & y2
x3 ------ y2
x4 ------ y1 & y3 & y2
Matchings
This is where we use a subset of the edges to produce a graph where each vertex appears in at most one edge.
Generally we want to produce the largest matching, such as pairing people with ideal tasks, so that people are has happy as possible.
We can generate such a matching by posing this as a network flow problem. We can add a source $s$ connected to all $x$ vertices and a sink $t$ connected to all $y$ vertices. We weight all edges as one:
graph LR
s ----|1| x1 & x2 & x3 & x4
y1 & y2 & y3 ----|1| t
x1 -----|1| y1 & y2
x2 -----|1| y1 & y3 & y2
x3 -----|1| y2
x4 -----|1| y1 & y3 & y2
We can then calculate a maximal matching using a maximal flow algorithm such as Ford-Fulkerson.