You are here
Homeadjacency matrix
Primary tabs
adjacency matrix
Definition
Let $G=(V,E)$ be a graph with vertex set $V=\{v_{1},\ldots,v_{n}\}$ and edge set $E$. The adjacency matrix $M_{G}=(m_{{ij}})$ of $G$ is defined as follows: $M_{G}$ is an $n\times n$ matrix such that
$m_{{ij}}=\left\{\begin{array}[]{ll}1&\textrm{if $\{v_{i},v_{j}\}\in E$}\\ 0&\textrm{otherwise.}\end{array}\right.$ 
In other words, start with the $n\times n$ zero matrix, put a $1$ in cell $(i,j)$ if there is an edge whose endpoints are $v_{i}$ and $v_{j}$.
For example, the adjacency matrix of the following graph
is
$\begin{pmatrix}0&0&1&1&0\\ 0&0&0&1&1\\ 1&0&0&0&1\\ 1&1&0&0&0\\ 0&1&1&0&0\end{pmatrix}.$ 
Remarks. Let $G$ be a graph and $M_{G}$ be its adjacency matrix.

$M_{G}=\mathbf{1}I$ iff $G$ is a complete graph. Here, $\mathbf{1}$ is the matrix whose entries are all $1$ and $I$ is the identity matrix.

If we are given a symmetric matrix $M$ of order $n$ whose entries are either $1$ or $0$ and whose entries in the main diagonal are all $0$, then we can construct a graph $G$ such that $M=M_{G}$.
Generalizations
The above definition of an adjacency matrix can be extended to multigraphs (multiple edges between pairs of vertices allowed), pseudographs (loops allowed), and even directed pseudographs (edges are directional). There are two cases in which we can generalize the definition, depending on whether edges are directional.
1. (Edges are not directional).
Since a multigraph is just a special case of a pseudograph, we will define $M_{G}$ for a pseudograph $G$. Let $G=(V,E)$ be a pseudograph with $V=\{v_{1},\ldots,v_{n}\}$ The adjacency matrix $M_{G}=(m_{{ij}})$ of $G$ is an $n\times n$ matrix such that $m_{{ij}}$ is the number of edges whose endpoints are $v_{i}$ and $v_{j}$. Again, $M_{G}$ is symmetric, but the main diagonal may contain nonzero entries, in case there are loops.
2. (Edges are directional).
Since a digraph is a special case of a directed pseudograph, we again define $M_{G}$ in the most general setting. Let $G=(V,E)$ be a directed pseudograph with $V=\{v_{1},\ldots,v_{n}\}$ and $E\subseteq V\times V\times(\mathbb{N}\cup\{0\})$. The adjacency matrix $M_{G}$ of $G$ is an $n\times n$ matrix such that
$m_{{ij}}=\{k\mid(v_{i},v_{j},k)\in E\}.$ In other words, $m_{{ij}}$ is the number of directed edges from $v_{i}$ to $v_{j}$.
Remarks

If $G$ is a multigraph, then the entries in the main diagonal of $M_{G}$ must be all $0$.

If $G$ is a graph, then $M_{G}$ corresponds to the original definition given in the previous section.

If $G$ is a digraph, then entries $M_{G}$ consists of $0$’s and $1$’s and its main diagonal consists of all $0$’s.

Given any square matrix $M$, there is a directed pseudograph $G$ with $M=M_{G}$. In addition, $M$ corresponds to adjacency matrix of various types of graphs if appropriate conditions are imposed on $M$

Generally, one can derive a pseudograph from a directed pseudograph by “forgetting” the order in the ordered pairs of vertices. If $G$ is a directed pseudograph and $G^{{\prime}}$ is the corresponding derived pseudograph. Let $M_{G}=(m_{{ij}})$ and $M_{{G^{{\prime}}}}=(n_{{ij}})$, then $n_{{ij}}=m_{{ij}}+m_{{ji}}$.
In the language of category theory, the above operation is done via a forgetful functor (from the category of directed pseudographs to the category of pseudographs). Other forgetful functors between categories of various types of graphs are possible. In each case, the forgetful functor has an associated operation on the adjacency matrices of the graphs involved.
Mathematics Subject Classification
05C50 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections