What is a Graph? · Basic Graphs

Lesson 12

Nikolai Chukhin · Alexander S. Kulikov

Another important class is bipartite graphs. An undirected graph is called bipartite if its set of nodes \(V\) can be partitioned into two sets \(V_{1}\) and \(V_{2}\) such that every edge joins a node from \(V_{1}\) and a node from \(V_{2}\). (In other words, there are no edges within one part.) In many applications, a graph is given together with a partition and is denoted by \(G(V_{1} \sqcup V_{2}, E)\). Sometimes, \(V_{1}\) and \(V_{2}\) are called \(L\) and \(R\) and a graph is drawn with the nodes from \(L\) on the left and nodes from \(R\) on the right. Here is an example where it is visually clear that every edge joins two nodes from different parts.

In applications, the two parts may have different “physical meaning”:

  • boys and girls;

  • students and dormitories;

  • hospitals and patients;

  • servers and requests;

  • customers and products.

At the same time, it is not always the case that a graph is given together with a partition of the set of nodes into two parts. For example, the following \(7 \times 4\) grid graph is bipartite though it may not be immediate from its drawing.

To ensure that it is bipartite, one may specify, for each node, the part it belongs to. To do this, one just assigns labels \(1\) and \(2\) to all nodes and ensures that every edge joins two nodes with different labels. Instead of (or together with) the labels \(1\) and \(2\), one may also use two different colors. Being bipartite is the same as being 2-colorable: we say that a graph is 2-colorable if it is possible to assign one of two colors to every node such that no edge has the endpoints of the same color.

There exist efficient algorithms that take a graph and check whether it is bipartite (that is, whether its set of nodes can be split into two parts so that every edge joins two nodes from different parts). We will soon learn how it is done. (Roughly, it can be done as follows. Start with any node and color it red. Then, color its neighbors blue. Then, color all their neighbors red, and so on. This way, one either runs into a conflict, in which case it can be shown that a graph is not bipartite for sure, or constructs the required \(2\)-coloring.) In the meantime, we give an example.

from networkx import grid_2d_graph, is_bipartite

print(is_bipartite(grid_2d_graph(7, 4)))

True