Bipartite Graphs

Basic Characteristics

• 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.

Representation

• 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.

Applications

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

Common Properties

• 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.

The Bipartite Matching Algorithm

• 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.