3. Adjacency Matrix

Adjacency Matrix

To build an adjacency matrix: ?

1. List the vertices in some order horizontally left to right.
2. Then using the same order, list them vertically top to bottom.
3. The entry in the $i^{\text{th}}$ row and the $j^{\text{th}}$ column is the number of edges going from vertex $i$ to vertex $j$.

If the graph is undirected, then the number in the $i^{\text{th}}$ row and the $j^{\text{th}}$ column $=$ the number in the $j^{\text{th}}$ row and the $i^{\text{th}}$ column.

title: Example 1
$$
\begin{array}{c|ccc}
	& x & y & w & z \\
	\hline x & 1 & 1 & 0 & 2 \\
	\hline y & 1 & 0 & 0 & 0 \\
	\hline w & 0 & 0 & 0 & 0 \\
	\hline z & 2 & 0 & 0 & 0 \\
\end{array}
\hspace{48px}
\begin{array}{c|ccc}
	& y & x & w & z \\
	\hline y & 0 & 1 & 0 & 0 \\
	\hline x & 1 & 1 & 0 & 2 \\
	\hline w & 0 & 0 & 0 & 0 \\
	\hline z & 2 & 0 & 0 & 0 \\
\end{array}
$$
 
```graphviz
graph G {
	w
	x--x,y,z,z
}

title: Example 2
$$
\begin{array}{c|ccc}
	& a & b & c & d \\
	\hline a & 1 & 1 & 1 & 1 \\
	\hline b & 1 & 1 & 0 & 1 \\
	\hline c & 0 & 0 & 1 & 0 \\
	\hline d & 0 & 0 & 0 & 0 \\
\end{array}
\hspace{48px}
\begin{array}{c|ccc}
	& b & c & d & a \\
	\hline b & 1 & 0 & 1 & 1 \\
	\hline c & 0 & 1 & 0 & 0 \\
	\hline d & 0 & 0 & 0 & 0 \\
	\hline a & 1 & 1 & 1 & 1 \\
\end{array}
$$
 
```graphviz
digraph G {
	a->a,b,c,d
	b->a,b,d
	c->c
}