1
$\begingroup$

Given a simple graph with $n$ vertices we can define its adjacency matrix as described here. The article further says that -

"The same concept can be extended to multigraphs and graphs with loops by storing the number of edges between each two vertices in the corresponding matrix element, and by allowing nonzero diagonal elements"

So my questions are the following -

  1. Given an $n\times n$ matrix with non-negative integer entries, can it always be thought of as the adjacency matrix of some directed graph (not necessarily simple)?

  2. Similarly if we are given such a matrix which is also symmetric and with non-negative even integer entries in the diagonal (to keep with the convention mentioned in the wikipedia article), can it be thought of as the adjacency matrix of an undirected graph (not necessarily simple)?

I was wondering if the adjacency matrix should satisfy any other properties or is it just any non-negative integer matrix?

Thank you.

$\endgroup$
  • $\begingroup$ No: $\begin{pmatrix}0&-1\\0&0\end{pmatrix}$ $\endgroup$ – Hagen von Eitzen Sep 20 '16 at 13:14
  • $\begingroup$ Sorry I meant positive integers. I've edited. $\endgroup$ – R_D Sep 20 '16 at 13:20
  • $\begingroup$ Yes to both questions. Entries should be non negative. $\endgroup$ – Shahab Sep 20 '16 at 13:23
  • 1
    $\begingroup$ Yes to both. It is also common to view non 0-1 entries as edge weights (if you want to avoid multiple edges). $\endgroup$ – TravisJ Sep 20 '16 at 13:26
  • $\begingroup$ I see! Thank you both. $\endgroup$ – R_D Sep 20 '16 at 13:27
0
$\begingroup$

Question answered in the comments -

Yes to both. It is also common to view non 0-1 entries as edge weights (if you want to avoid multiple edges). – TravisJ Sep 20 at 13:26

$\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.