Skip to content

Bipartite Graph

Introduction

A bipartite graph, also known as a bipartite graph, is a type of graph with a special structure. Its vertex set can be partitioned into two disjoint subsets such that every edge in the graph connects a pair of vertices from these two sets, and no edge connects vertices within the same subset.

Thanks to this simple structure, bipartite graphs not only exhibit many elegant properties but are also widely used in real-world modeling scenarios, such as task assignment, recommendation systems, matching markets, etc. Many optimization problems that are difficult on general graphs can be solved efficiently and accurately on bipartite graphs.

Definition

If the vertex set \(V\) of a graph \(G=(V,E)\) can be partitioned into two disjoint subsets \(X\) and \(Y\) such that the two endpoints of every edge \(e\in E\) belong to \(X\) and \(Y\) respectively, then \(G\) is called a bipartite graph. The sets \(X\) and \(Y\) are often referred to as its two parts, or the left part and right part of the bipartite graph, respectively. When the two parts \(X\) and \(Y\) of a bipartite graph are known, the graph \(G\) can also be represented by the triple \((X, Y, E)\).

A typical bipartite graph is shown below.

Trees, even cycles, grid graphs, etc., are common examples of bipartite graphs.

Characterization

A bipartite graph can also be equivalently defined by the following properties:

  • The graph \(G\) is 2‑colorable. That is, all vertices of the graph can be colored using at most two colors, ensuring that adjacent vertices have different colors.
  • The graph \(G\) contains no cycles of odd length.

Clearly, the first property is equivalent to the definition of a bipartite graph: simply color the two parts of the bipartite graph with two different colors.

The second property is slightly more complex. Consider attempting to color the graph \(G\) with two colors. Since different connected components do not interfere with each other's coloring, we can consider each connected component separately. Choose a vertex \(s\) in the connected component and perform DFS, recording the distance from each vertex \(v\) in the component to \(s\). Starting from \(s\), by induction on the DFS spanning tree, if a feasible coloring exists, it must be based on the parity of the distance from each vertex \(v\) to the starting vertex \(s\), coloring them with two different colors accordingly.

Next, consider edges not in the spanning tree. If the two endpoints of these non-tree edges have different colors, the current coloring scheme is feasible; otherwise, no feasible scheme exists. Furthermore, two vertices having different colors is equivalent to their distances to the tree root \(s\) having opposite parity, which in turn is equivalent to the non-tree edge forming an even cycle rather than an odd cycle. Therefore, as long as there are no odd cycles, these non-tree edges must connect vertices of different colors, and the entire graph can be colored with two colors, meaning the graph must be bipartite.

Determination

To determine whether a graph is bipartite, we can simply use the above equivalent characterization and attempt to color the graph. For this purpose, DFS or BFS can be used to traverse the graph. If an odd cycle is detected, i.e., a situation where coloring is impossible, then the graph is not bipartite; otherwise, it is bipartite.

The specific procedure is as follows:

  • Traverse the vertices. If a vertex that has not been colored is found, a new connected component is discovered.
  • Choose a color for that vertex and use it as the starting point for DFS or BFS to attempt coloring the connected component.
  • When traversing adjacent vertices, if a vertex that has already been colored is found, check whether its color is the same as the current vertex's color. If they are the same, the graph is not bipartite, and the algorithm returns immediately; otherwise, continue traversing.
  • If a vertex that has not been colored is found, color it with the opposite color of the current vertex.

Refer to the following code:

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int n;
std::vector<std::vector<int>> gr;
std::vector<int> colors, vis;

// Depth-first search to color vertices.
bool dfs(int cr) {
  vis[cr] = true;
  for (int nt : gr[cr]) {
    if (vis[nt]) {
      if (colors[cr] == colors[nt]) return false;
    } else {
      colors[nt] = colors[cr] ^ 1;
      if (!dfs(nt)) return false;
    }
  }
  return true;
}

// Check whether the graph GR is bipartite.
// If so, the vector COLORS will store a feasible coloring.
bool check_bipartite() {
  for (int i = 1; i <= n; ++i) {
    // Check connected components one by one.
    if (!vis[i]) {
      colors[i] = 0;
      if (!dfs(i)) return false;
    }
  }
  return true;
}

The time complexity is \(O(|V|+|E|)\).

Applications

Due to their simple structure, many graph optimization problems can be solved efficiently on bipartite graphs. For details, refer to the relevant main entries.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用