贡献者： 零穹
将图的点集和边集的关系用矩阵来体现，就是所谓的图的矩阵表示。体现点与点相邻关系的矩阵称为邻接矩阵；体现点与边关联关系的矩阵称为关联矩阵。当对某个图选定了权函数成为赋权图时，体现权函数的矩阵称为赋权矩阵。
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$ 是其上的权函数。则给出权函数的矩阵称为赋权矩阵。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。