2）邻接矩阵的性质:
①若邻接矩阵的元素全为零,则其对应的图是零图 ②若主对角线元素为1,则对应结点上有环(有向图) ③主对角线元素为零外其余元素为1，则为完全图 ④矩阵的行和为某结点出度,列和为入度（有向 图）
例1:右图的邻接矩阵为：
v1
v4
v1 v2 v3 v4
v1 v2 A= v 3 v4
1 0 0 0 2 1 0 1 0 0 0 1 0 0 1 0
v2
v3
有向图与邻接矩阵的对应关系
v1 v2 v1 1
v ?v2 ?A (G) ?
v? ? ?
v2 v3 0 1 0 0 0 ? ? 0 v4
11
1 1 0 0? ? v4
3
v4 v3? 0 0 ?1 0
3） 利用邻接矩阵的幂求图中的通路及回路数
定理 设A为D的邻接矩阵，V={v1, v2, …, vn}为
) 顶点集，则A的k次幂aij (k 为
素 A
D中i v 到j v 长度为k的通路数，其中为vi到自ii
k（k ?1）中元
a
(k )
身
长度为k的回路数。
