一、图的邻接矩阵

定义：设G为n阶图，$V={v_1, v_2, …, v_n}$V=v1​,v2​,…,vn​,邻接矩阵$A(G)=(a_{ij})$A(G)=(aij​),其中$a_{ij}=\left\{ \begin{aligned} &l ,v_i和v_j间边数 \\ &0 , v_i和v_j不邻接 \end{aligned} \right.$aij​={​l,vi​和vj​间边数0,vi​和vj​不邻接​示例如下：

定理：设$A^k(G)=(a_{ij}^{(k)})$Ak(G)=(aij(k)​)，则$(a_{ij}^{(k)})$(aij(k)​)表示顶点$v_i$vi​到顶点$v_j$vj​的途径长度为k的途径条数。
推论：$A_2$A2​的元素$a_{ii}^{(2)}$aii(2)​是$v_i$vi​的度数

二、图的关联矩阵

定义：若G是(n, m) 图。定义G的关联矩阵：$M(G)=(a_{ij})_{n*m}$M(G)=(aij​)n∗m​，其中$a_{ij}=l, v_i与e_i关联的次数(0,1,或2(环))$aij​=l,vi​与ei​关联的次数(0,1,或2(环))