一、图的邻接矩阵

定义：设G为n阶图，$V=v_1,v_2,\dots ,v_n$,邻接矩阵$A(G)=(a_{ij})$,其中$$a_{ij}=\{\begin{array}{rl}& l,v_i和v_j间边数\\ & 0,v_i和v_j不邻接\end{array}$$示例如下： 定理：设$A^k(G)=(a_{ij}^{(k)})$，则$(a_{ij}^{(k)})$表示顶点$v_i$到顶点$v_j$的途径长度为k的途径条数。 推论：$A_2$的元素$a_{ii}^{(2)}$是$v_i$的度数

二、图的关联矩阵

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