贡献者： 零穹
将图的点集和边集的关系用矩阵来体现，就是所谓的图的矩阵表示。体现点与点相邻关系的矩阵称为邻接矩阵；体现点与边关联关系的矩阵称为关联矩阵。当对某个图选定了权函数成为赋权图时，体现权函数的矩阵称为赋权矩阵。
1. 邻接矩阵
邻接矩阵是用来体现点点相邻关系的，具体地，设图 $G$ 的点集为 $V(G)=\{v_1,\cdots,v_n\}$。若 $G$ 是无向图，则邻接矩阵的第 $(i,j)$ 个元反映了连接 $v_i,v_j$ 的边数。若 $G$ 是有向图，则邻接矩阵的第 $(i,j)$ 个元反映了以 $v_i$ 为起点，$v_j$ 为终点的有向边数。
定义 1 邻接矩阵
设 $G$ 是图，$V(G)=\{v_1,\cdots,v_n\}$，$A=(a_{ij})$ 是 $n$ 阶矩阵。若 $G$ 是无向图，$a_{ij}$ 等于连接 $v_i,v_j$ 的边数；若 $G$ 是有向图，$a_{ij}$ 等于以 $v_i$ 为起点，$v_j$ 为终点的有向边数。则称 $A$ 为 $G$ 的邻接矩阵（adjacency matrix）。
定理 1
设 $A$ 是有向图 $G$ 的邻接矩阵，$V(G)=\{v_1,\cdots,v_n\}$。则 $A^k$ 中的第 $(i,j)$ 元是 $G$ 中长度为 $k$ 的从 $v_i$ 到 $v_j$ 的有向链的数目。
2. 关联矩阵
关联矩阵是用来体现点边的关联关系的，具体地，设图 $G$ 的点集和边集分别为
\begin{equation}
V(G)=\{v_1,\cdots,v_n\},E(G)=\{e_1,\cdots,e_m\}.~
\end{equation}
若 $G$ 是无向图，则关联矩阵的第 $(i,j)$ 个元反映了 $v_i,e_j$ 是否关联。若 $G$ 是有向图，则关联矩阵的第 $(i,j)$ 个元反映了以 $v_i$ 是 $e_j$ 的起点还是终点。
定义 2 关联矩阵
设 $G$ 是图，$V(G)=\{v_1,\cdots,v_n\},E(G)=\{e_1,\cdots,e_m\}$，$A=(a_{ij})$ 是 $n\times m$ 的矩阵。若 $G$ 是无向图，
\begin{equation}
a_{ij}=\left\{\begin{aligned}
&1, v_i\in e_j,\\
&0, v_i\not\in e_j;
\end{aligned}\right.~
\end{equation}
若 $G$ 是有向图，
\begin{equation}
a_{ij}=\left\{\begin{aligned}
&1, &v_i\text{是} e_j\text{起点} ,\\
&-1, &v_i\text{是} e_j\text{终点} ,\\
&0,&v_i\not\in e_j.
\end{aligned}\right.~
\end{equation}
则称 $A$ 为 $G$ 的
关联矩阵（incidence matrix）。
3. 赋权矩阵
赋权矩阵是用来体现赋权函数的，其有不同的定义方式。例如，设图 $G$ 的点集为 $V(G)=\{v_1,\cdots,v_n\}$，则赋权矩阵是一个 $n$ 阶矩阵。若 $G$ 为有向图，则其第 $(i,j)$ 个元反映了以 $v_i$ 为起点 $v_j$ 为终点的所有边的权值之和；若 $G$ 为无向图，则其第 $(i,j)$ 个元反映了连接 $v_i,v_j$ 的所有边的权值之和。
定义 3 赋权矩阵
若 $G$ 是图，$\omega$ 是其上的权函数。则给出权函数的矩阵称为赋权矩阵。