S7.3图的矩阵表示1.无向图的关联矩阵设无向图G=<V，E>，V={V1,...,VnJ,N2en}，令m;为顶点v,与边e;的EF[e1, e2' ...,关联次数，则称(mi)nxm为G的关联矩阵。记作M(G)v;与e;不关联0m;的取值为：v;与e;关联次数为12v;与e;关联次数为2
§7.3 图的矩阵表示 1.无向图的关联矩阵 设无向图G=<V，E>，V={v1，v2，.，vn }， E ={e1，e2，.，en }，令mij为顶点vi与边ej的 关联次数，则称(mij)nxm为G的关联矩阵。记作 M(G) 0 vi与ej不关联 1 vi与ej关联次数为1 2 vi与ej关联次数为2 mij的取值为：
S7.3图的矩阵表示1.无向图的关联矩阵1SM/(G) =图7-10关联矩阵
§7.3 图的矩阵表示 1.无向图的关联矩阵 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0 M（G）= 关联矩阵 v2 v1 v3 v4 e1 e2 e3 e4 图7-10 e5
S7.3图的矩阵表示1.无向图的关联矩阵关联矩阵性质：每一列恰好有两个1或一个22第i行元素之和为v的度数（3）所有元素之和等于2m。(4)第i行之和等于0，v,是孤立点。(5)第j列与第k列相同，e;与e为平行边
§7.3 图的矩阵表示 1.无向图的关联矩阵 关联矩阵性质： （1）每一列恰好有两个1或一个2 （2）第i行元素之和为vi的度数。 （3）所有元素之和等于2m。 （4）第i行之和等于0，vi是孤立点。 （5）第j列与第k列相同， ej与ek为平行边
S7.3图的矩阵表示2.有向图的关联矩阵设有向图D=<V,E>，V={V1，V2'.，Vn}令：E[e1, e2' ...,enl,1，v为e;的始点0，v;与e;不关联mi-1，v;为e;的终点则称(m;)nxm为D的关联矩阵。记作M(D)
§7.3 图的矩阵表示 2.有向图的关联矩阵 则称(mij)nxm为D的关联矩阵。记作M(D) 1，vi为ej的始点 0，vi与ej不关联 -1，vi为ej的终点 mij = 设有向图D=<V，E>，V={v1，v2，.，vn }， E ={e1，e2，.，en }，令：