如何判断一个图是否为二分图？

1. Overview

In graph theory, a bipartite graph is a special kind of graph that consists of two vertex sets. In this tutorial, we’ll discuss a general definition. We’ll also present an algorithm to determine whether a given graph is bipartite or not.

2. Bipartite Graph Definition

Let’s consider a graph G(V, E) . The graph is a bipartite graph if:

The vertex set of can be partitioned into two disjoint and independent sets and
All the edges from the edge set have one endpoint vertex from the set and another endpoint vertex from the set

Let’s try to simplify it further. Now in graph , we’ve two partitioned vertex sets V_1 and V_2 . Suppose we’ve an edge $(E_1, E_2) \in E$ . Now according to the definition of a bipartite graph, the edge should connect to one vertex from set V_1 and another from set V_2 .

3. An Example

It’s now time to see an example of a bipartite graph:

first example

Here, we’ve taken a random graph G_1(V, E) . Now, to satisfy the definition of a bipartite graph, the vertex set needs to be partitioned into two sets such that each edge joins the two vertex sets.

Is it possible to partition the vertex set of G_1 so that it satisfies the bipartite graph definition? Let’s find out:

bipartite

This is the same graph G_1 , just with a different representation. Here, we partition the vertex set V=(A, B, C, D, E) into two disjoint vertex sets V_1 = (A, D) and V_2 = (B, C, E) .

Also, we can see the edges from the edge set E = (E_1, E_2, E_3, E_4, E_5, E_6) follows the definition of a bipartite graph. Each edge has one endpoint in V_1 and another endpoint in V_2 . There are no edges whose both endpoints belong to V_1 or V_2 .

Therefore, we can conclude that the graph G_1 is a bipartite graph.

4. Properties

Bipartite graphs have some very interesting properties. In this section, we’ll discuss some important properties of a bipartite graph.

If a graph is a bipartite graph then it’ll never contain odd cycles.

In graph G_1 , a random cycle would be ABDCA . Another one is DEACD .

The length of the cycle is defined as the number of distinct vertices it contains. In both of the above cycles, the number of vertices is . Hence these are even cycles.

The subgraphs of a bipartite graph are also bipartite.

In graph G_1 , let’s select a random subgraph G_S(V_S, E_S) . Here V_S = (A, B, C, D) and E_S = (E_1, E_2, E_4, E_5) . This subgrah G_S of is also a bipartite graph.

A bipartite graph is always 2-colorable, and vice-versa.

In graph coloring problems, 2-colorable denotes that we can color all the vertices of a graph using different colors such that no two adjacent vertices have the same color.

In the case of the bipartite graph G_1 , we have two vertex sets and each edge has one endpoint in each of the vertex sets. Therefore, all the vertices can be colored using different colors and no two adjacent nodes will have the same color.

In an undirected bipartite graph, the degree of each vertex partition set is always equal.

In the example graph G_1 , the partitions are: V_1 = (A, D) and V_2 = (B, C, E) . Now the sum of degrees of vertices and will be the degree of the set V_1 . and both are of degree . Hence, the degree of V_1 is .

The degree of V_2 is the sum of degrees of vertices , , and . The vertices , , and are of degree each. Hence, the degree of the set V_2 is . So as G_1 is a bipartite graph, the degree of the two vertex partition sets are of equal degree.

5. Algorithm

In this section, we’ll present an algorithm that will determine whether a given graph is a bipartite graph or not.

algorithm IsBipartite(G(V, E), S):
    // INPUT
    //     G(V, E) = a graph with vertices V and edges E
    //     S = starting vertex
    // OUTPUT
    //     Flag indicating if if the graph is bipartite

    r <- create an empty queue
    color[S] <- RED
    r.enqueue(S)

    while r is not empty:
        n1 <- r.dequeue()
        for each n2 in n1.Adj():
            if color[n2] = null:
                if color[n1] = RED:
                    color[n2] = BLUE
                else:
                    color[n2] = RED
                r.enqueue(n2)
            else:
                if color[n2] = color[n1]:
                    return 'Graph is not Bipartite'

    return 'Graph is Bipartite'

This algorithm uses the concept of graph coloring and BFS to determine a given graph is bipartite or not.

This algorithm takes the graph G(V, E) and a starting vertex as input. The algorithm returns either the input graph is bipartite or the graph is not a bipartite graph.

The steps of this algorithm are:

Assign a red color to the starting vertex
Find the neighbors of the starting vertex and assign a blue color
Find the neighbor’s neighbor and assign a red color
Continue this process until all the vertices in the graph are assigned a color
During this process, if a neighbor vertex and the current vertex have the same color then the algorithm terminates. The algorithm returns that the graph is not a bipartite graph

We’ve used a queue data structure to store and manage all the neighbor vertices.

6. Running the Algorithm on a Graph

In this section, we’ll run the algorithm on a sample graph to verify that the algorithm gives the correct output:

algo1

We’ve taken a sample graph G_2 and vertex set V = (A, B, C, D, E, F) has vertices. Here we’re picking the vertex as the starting vertex. So let’s start the first step:

algo2

So the first step of the algorithm is to fill the starting vertex with the red color. The next step is to find the neighbor vertices of the vertex and fill them with the color blue:

algo3

The vertex has two adjacent vertices: and . The algorithm first checks if the adjacent vertices are already filled with color. In our case, they are not filled. The algorithms fill the vertex and with the blue color.

We then choose any of the newly filled vertices and find the neighbors. Let’s choose the vertex :

algo4

In graph G_2 , the vertex is adjacent to vertex and . Now the algorithm first checks if the vertices are already filled with some color. In our case, the vertices are not filled with color.

Next, the algorithm checks the color of the vertex . As the color of is blue, so the algorithm fills and with red:

algo5

Now, the algorithm checks the adjacent vertices for the . The vertex has two adjacent vertices: and . Again, the algorithm checks whether the vertices already filled with color or not. In this case, the vertex is already filled with color. But the vertex is not filled yet.

The algorithm checks the color of the vertex . As the vertex is filled with the blue color, the algorithm fills the vertex with the red color. The algorithm continues this process until it checks all the vertices and it’s neighbors once.

Now, we can see that in the graph G_1 , no adjacent vertices have the same color. Also, we can see two clear partitions of the vertex set: V_1 = (B, D) and V_2 = (A, C, E, F) .

Therefore, the algorithm returns that the graph G_2 is a bipartite graph.

7. Time Complexity Analysis

In the algorithm, first, we traverse each vertex once. Then for each vertex, we visit each neighbor of a vertex once. The algorithm uses BFS for traversing. BFS takes $\mathcal{O}(V + E)$ time.

For storing the vertices, we can either use an adjacency matrix or an adjacency list.

Now if we use an adjacency matrix, then it takes $\mathcal{O}(V ^2)$ to traverse the vertices in the graph. So, if we use an adjacency matrix, the overall time complexity of the algorithm would be $\mathcal{O}(V ^2)$ .

On the other hand, an adjacency list takes $\mathcal{O}(V + E)$ time to traverse all the vertices and their neighbors in the graph. Therefore, if we use an adjacency list in the algorithm then the overall time complexity will be $\mathcal{O}(V + E)$ .

8. Conclusion

In this tutorial, we’ve discussed the bipartite graph in detail.

We’ve presented a graph coloring based BFS algorithm to determine if a graph is bipartite or not.

Finally, we’ve analyzed the time complexity of the given algorithm.

Persistence

REST

Security