Can someone explain to me with an example how to create the adjacency matrix of a bipartite graph? And why the diagonal elements of it are not zero? Thanks.
Graph Theory – Example for Adjacency Matrix of a Bipartite Graph
graph theorylinear algebramatrices
Related Solutions
It is a directed graph, i.e. \begin{equation} \begin{matrix} a & & b\\ \updownarrow & X & \uparrow\\ c &\leftrightarrow & d \end{matrix} \end{equation}
where I used $X$ to denote a double-sided link between $a$-$d$ and $c$-$d$.
The direction of the edges is convention defined and could be reversed.
You can use a quick algorithm to check whether it's bilateral.
You're given an adjacency matrix of order $2n$ (i.e. a representation of a graph with $2n$ vertices.)
Find the column with the most ones in it; suppose it's column $k$. Let $N_k$ be the list of ones in column $k$ (these are the neighbors of vertex $k$). Initialize a partition $P \equiv N_k$, and a partition $Q=\{k\}$.
[Loop.] Iterate over each column $j$ in the matrix:
If $P$ has more than $n$ ones in it, the graph can't be bipartite. In that case, quit and return NOT BIPARTITE.
Compute $N_j$. Now either:
- $P$ and $N_j$ have no ones in common: $P$ is zero whenever $N_j$ is one, and vice versa. In this case, keep going to the next column.
- $P$ and $N_j$ have some ones in common. Update $P = P \cup N_j$, and $Q = Q \cup \{j\}$, and go to the next column.
Once again, if $P$ has more than $n$ members, the graph can't be bipartite—quit and return NOT BIPARTITE.
If the graph really is bipartite, $P$ now contains a complete partition of the graph. Permute the adjacency matrix to put all the members of $P$ first, and all of the members of $Q$ last.
If the matrix is now in the canonical form of a bipartite adjacency matrix (where the upper-left and lower-right blocks are all zero), the graph is bipartite; quit and return BIPARTITE. Otherwise, the graph isn't bipartite — quit and return NOT BIPARTITE.
Here's how to use this algorithm. Take your second graph as an example, which has $2n$ vertices with $n=3$.
- Column 1 has three ones in it. Since this is the maximal number of ones in any column, we can use it as a starting point. Then $N_1 = \{2,4,6\}$, so we initialize $P=\{2,4,6\}$ and $Q=\{1\}$.
- We begin looping over the columns of the matrix.
- Column 1 overlaps with $P$, so $P \leftarrow P\cup N_1 = \{2,4,6\}$, and also $Q \leftarrow Q \cup \{1\} = \{1\}$.
- Column 2 doesn't overlap at all.
- Column 3 overlaps; $Q \leftarrow Q \cup \{3\} = \{1,3\}$.
- Column 4 doesn't.
- Column 5 does. $Q \leftarrow Q \cup \{5\} = \{1,3,5\}$.
- Column 6 doesn't.
- If this graph is bipartite (and it is), $P$ should now contain a partition of the graph. In fact, we know $P=\{2,4,6\}$ and $Q=\{1,3,5\}.$ If we permute the adjacency list to put members of $P$ first and members of $Q$ last, we find that it appears in canonical form.
Best Answer
When a (simple) graph is "bipartite" it means that the edges always have an endpoint in each one of the two "parts". So if the vertices are taken in order, first from one part and then from another, the adjacency matrix will have a block matrix form:
$$ A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix} $$
because the only nonzero entries correspond to edges between the first part and the second part, i.e. entries in the upper right hand block $B$ and its transpose in the lower left hand block.
So all the information about edges is given by block $B$, and provided the author is clear about this form of representation (which part is first, which is second), the adjacency matrix $A$ is reconstructable from $B$ as in the above formula.
Note that while the diagonal of $A$ is all zeros (as typical for an adjacency matrix), the entries in $B$ might all be ones (a so-called complete bipartite graph), or the zero entries in $B$ might appear to be randomly distributed.
For example, suppose we have the "utility graph", $K_{3,3}$, the complete bipartite graph with three nodes in each part. The biadjacency matrix is then all ones:
$$ B = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$
and the $6\times 6$ adjacency matrix is:
$$ A = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{pmatrix} $$