1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ When we have a bipartite graph, often it is convenient to refer to the biadjacency matrix $B$. Then an adjacency matrix would take the form $\begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$. Are you familiar with this convention? $\endgroup$ – hardmath Jan 24 '16 at 18:12
  • $\begingroup$ @hardmath Actually I don't have much background of linear algebra so no. I'm sorry if my question is too easy or obvious. $\endgroup$ – Wise Jan 24 '16 at 18:15
3
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.