Matching of Bipartite Graphs using NetworkX
A simple introduction to matching in bipartite graphs with Python code examples
Graph matching can be applied to solve different problems including scheduling, designing flow networks and modelling bonds in chemistry. In this article, I will give a basic introduction to bipartite graphs and graph matching, along with code examples using the python library NetworkX.
Before moving to the nitty-gritty details of graph matching, let’s see what are bipartite graphs.
Bipartite Graphs
According to Wikipedia,
A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V.
In a bipartite graph, we have two sets of vertices U and V (known as bipartitions) and each edge is incident on one vertex in U and one vertex in V. There will not be any edges connecting two vertices in U or two vertices in V. Figure 1 denotes an example bipartite graph.
