Graphs and Networks: Bipartite Graphs

Bipartite Graphs

A Bipartite Graph is a type of graph where the vertices can be divided into two distinct groups or sets such that every edge in the graph connects a vertex from one set to a vertex from the other set.
Each vertex can be part of one set only and must not be linked to any vertex within the same set. Only cross connections are allowed.

Bipartite graphs can often be represented visually with each of their two sets of vertices grouped together.
A Complete Bipartite Graph denoted as K(m,n), is a special type of bipartite graph where every vertex of the first set is connected to every vertex of the second set, creating m*n edges.

Commonly used to model relationships between two different types of things: e.g., jobs and workers, students and courses, or people and clubs.

The degree of a vertex in a bipartite graph is the number of edges connected to it.
A bipartite graph does not contain any odd length cycles.
A graph is bipartite if and only if it is possible to colour the vertices of the graph using two colours such that no two adjacent vertices share the same colour.
If the vertices of a bipartite graph are all connected, it is called a connected bipartite graph.
In a bipartite graph, the Maximum Matching is the largest possible set of edges with no vertex shared between them.
In a weighted bipartite graph, the Minimum Cost Maximum Matching is a matching where the sum of the weights of all the edges is as small as possible.

Algorithms such as the Hungarian Algorithm or the Hopcroft-Karp Algorithm can solve optimization problems related to bipartite graphs, such as the finding the Maximum Matching or the Minimum Cost Maximum Matching.