Bipartite Graphs

Computer Science Level 2

Which of the following adjacency matrices represent a bipartite graph?

$\text{A} = \left(\begin{array}{ccccc}0 & \color{#D61F06}{1} & \color{#D61F06}{1} & 0 & 0 \\ \color{#D61F06}{1} & 0 & 0 & \color{#D61F06}{1} & 0 \\\color{#D61F06}{1} & 0 & 0 & 0 & 0 \\0 & \color{#D61F06}{1} & 0 & 0 & \color{#D61F06}{1} \\0 & 0 & 0 & \color{#D61F06}{1} & 0\end{array}\right), \quad \text{B} = \left(\begin{array}{ccccc}0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1}& 0 \\ \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} \\0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0 \\ \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} \\0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0\end{array}\right)$

$\text{C} = \left(\begin{array}{ccccc}0 & 0 & \color{#20A900}{1} & 0 & 0 \\0 & 0 & \color{#20A900}{1} & 0 & 0 \\\color{#20A900}{1} & \color{#20A900}{1} & 0 & \color{#20A900}{1} & \color{#20A900}{1} \\0 & 0 & \color{#20A900}{1} & 0 & 0 \\0 & 0 & \color{#20A900}{1} & 0 & 0\end{array}\right)$

Only A and B Only A Only A and C Only B and C Only B A, B, and C Only C None of these

1 solution

Pranshu Gaba
Feb 17, 2016

Bipartite graphs are graphs whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in one set and the other endpoint in the other set. The figure at the beginning of the problem is an example of a bipartite graph. For every edge in the graph, we can see that one endpoint is blue and the other endpoint is green.

We will now identify which graphs out of A, B and C are bipartite. A simple way to do this is to draw the graphs. We are given adjacency matrices , in which row $i$ and column $i$ correspond to vertex $i$ . The element $a_{i, j }$ in the matrix represents the number of edges connecting vertices $i$ and $j$ . For example, if $a_{2,3} = 5$ , then it means that 5 edges connect vertices labeled $2$ and $3$ .

We will read the given adjacency matrices row by row and draw the corresponding graphs. Since the matrices are symmetric, the graphs are undirected and we need to only consider the upper (or lower) triangular parts of the matrices. The following matrix is upper triangular matrix of A.

$\text{A} = \left(\begin{array}{ccccc}0 & \color{#D61F06}{1} & \color{#D61F06}{1} & 0 & 0 \\ 0 & 0 & 0 & \color{#D61F06}{1} & 0 \\ 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & \color{#D61F06}{1} \\0 & 0 & 0 & 0 & 0\end{array}\right)$

In matrix A,

row 1 has "1"'s in columns 2 and 3, therefore we draw one edge between vertices 1 and 2 and we draw one edge between vertices 1 and 3.
In row 2, there is a "1" in column 4, therefore we must draw one edge between vertices 2 and 4.
In row 4, there is a "1" in column 5, therefore we must draw one edge between vertices 4 and 5.

We obtain the following graph. Note that we can color the graphs using two colors such that each edge has one blue endpoint and one green endpoint. Therefore, Graph A is bipartite.

Graph A Graph A

We can draw graphs for matrices B and C in a similar way.

Graph B Graph B

Graph C Graph C

We see that in all three graphs, we can color vertices using two colors such that each edge has one blue endpoint and one green endpoint. Therefore all three graphs are bipartite. $_\square$

Moderator note:

A purely computational approach would be to consider the matrix $A^2 + A^4 + A^6 + \ldots$ for enough terms. What can we say about it?

Is there a way to solve this without drawing each graph?

Agil Saelan - 5 years, 3 months ago

A purely computational approach would be to consider the matrix $A^2 + A^4 + A^6 + \ldots$ for enough terms. What can we say about it?

Calvin Lin Staff - 5 years, 3 months ago

Another necessary and sufficient characterization of the bipartite graph is that it contains no odd cycles. Hence if $\text{Trace}(A^{2k+1})=0$ for all $k \leq \lfloor n/2\rfloor$ , where $n$ is the number of nodes in the graph, then the graph is bipartite.

Abhishek Sinha - 5 years, 2 months ago

Certainly! An adjacency matrix $A$ represents a bipartite graph if and only if there exists a permutation $P$ such that

$P A P = \left( \begin{array}{cc} \textbf{0} & B \\ B^{T} & \textbf{0} \end{array}\right)$

where $\textbf{0}$ is a zero matrix and $B$ is a non-zero matrix.

For example, for matrix A in the problem, a possible permutation matrix is

$P = \left(\begin{array} {ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} \right)$

We see that

$P A P = \left(\begin{array} {ccccc} 0 & 0 & \color{#3D99F6}{0} & \color{#3D99F6}{1} & \color{#3D99F6}{1} \\ 0 & 0 & \color{#3D99F6}{1} & \color{#3D99F6}{1} & \color{#3D99F6}{0} \\ \color{#3D99F6}{0} & \color{#3D99F6}{1} & 0 & 0 & 0 \\ \color{#3D99F6}{1} & \color{#3D99F6}{1} & 0 & 0 & 0 \\ \color{#3D99F6}{1} & \color{#3D99F6}{0} & 0 & 0 & 0 \\ \end{array} \right)$

Here $B = \left( \begin{array} {ccc} 0 & 1 & 1 \\ 1 & 1 & 0 \end{array}\right)$ . Since a permutation matrix satisfying the required condition exists, the matrix represents a bipartite graph.

Pranshu Gaba - 5 years, 3 months ago

Bipartite Graphs

1 solution

Moderator note:

0 pending reports