# 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 $(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.

## 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. 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 non-zero entries, in case there are loops.

2. 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

Title adjacency matrix AdjacencyMatrix 2013-03-22 17:22:43 2013-03-22 17:22:43 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 05C50