离散数学图论-矩阵表示.pptx

图图的矩阵表示的矩阵表示 14.4 图的矩阵表示 n 图可用集合或图形表示，也可用矩阵表示，便于用代 数方法研究图的性质。 n 用矩阵表示图之前，必须将图的顶点或边标定顺序， 使其成为标定图 1、无向图的关联矩阵 1）定义：设无向图G，Vv1,v2,，vn。 E=e1,e2,e3，em,令mij为顶点vi与边ej的关联次数， 则称(mij)nxm为G的关联矩阵，记作 M(G) 2）性质: 关联矩阵是n行（结点数）m列（边数）的矩阵 3）M(G)每列元素之和均为2，这正说明每条边关联两个顶 点(环所关联的两个端点重合) i mij = 2 (j = 1，2，m) 4）M(G)第i行元素之和为结点vi的度数， j mij = d(vi) (i = 1，2，n) 5) 所有行的和（即矩阵所有元素之和）等于边数的2倍 d(vi)mij 2m， （即各顶点的度数之和等于边数的2倍） 6）第j列与第k列相同，当且仅当边ej与ek是平行边 7）j mij =0,第i行元素和为0,当且仅当vi是孤立点, 2 1 1 1 0 M(G)= 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 v4 v1 v2v3 e1 e2 e3 e4e5 2、有向图的关联矩阵 1)定义：设有向图D中无环， Vv1，v2，vn, Eel，e2,，em， 令 1 vi为边ej的起点(始点) mij = 0 vi为边ej不关联 1 vi为边ej的终点 则称(mij)nxm，为D的关联矩阵，记作M(D） 2)有向图关联矩阵的性质 (1)每列恰好一个+1和一个-1； j mij= 0，j1，2，m，从而 mij=0 这说明M(D)中所有元素之和为0 (2) M(D)中，负1的个数等于正1的个数，都等于 边数m，这正是有向图握手定理的内容（入 度之和等于出度之和） (3)第i行中，正1的个数等于d+(vi)（结点的出度 ），负1的个数等于d-(vi)（结点的入度） （4）平行边所对应的列相同 e5 v1 v2 v3 e1 e2 e3 e4 v4 -1 1 0 0 0 M(D)= 1 -1 1 0 0 0 0 0 1 1 0 0 -1 -1 -1 3、有向图的邻接矩阵 1）定义：设有向图D，Vv1，v2，vn，Ee1， e2，em 令： aij为顶点vi邻接到顶点vj边的条数 称(aij)nxn为D的邻接矩阵，记作A(D)，或简记为A 2）邻接矩阵的性质 （1）每列元素之和为结点的入度， 即 jaij = d-(vi)，i=1，2，n 所有列的和 aij d-(vi) m ，等于边数 每行元素之和为结点的出度，所有行的和也等于边数 （2）邻接矩阵中元素 aij 反映了有向图中结点vi到vj通路长度为 1的条数 （3）A(D)中所有元素之和为D中长度为1的（边）通路总条数。 主对角线的元素值为图中结点vi长度为1 的环的条数。 n 利用A(D)确定D中长度为L的通路数和回路数,就需要用到邻接矩 阵的幂次运算 （4）A2中的元素值bij是结点vi到vj长度为2 的通路条数; 说明：由矩阵的乘积定义 bij = k aik * akj 由此可推断， A3矩阵中的cij元素值，表示从 vi到vj 到长度恰为3的通路数; （5）定理14.11 设A为有向图D的邻接矩阵，Vv1，v2，vn 为D的顶点集， 则A的L次幂AL(L1)中元素cij为D中vi到vj长度为L的通路数， 其中cii为vi到自身长度为L的回路数, cij(所有元素之和)为D中长度为L的通路总数， 其中 cii为D中长度为L的回路总数 推论: 设BLA + A2十+AL (L1)， 则BL中元素 bij为D中从 vi到vj 长度小于或等于L的通路数， 其中主对角线上元素值为D中长度小于或等于L的回路数。 4、有向图的可达矩阵 1）定义：设D为有向图, Vv1，v2，vn 令 1 vi可达vj pij 0 否则 称(pij)nxn为D的可达矩阵，记作P(D)，简记为P 2）可达矩阵的性质 （1）主对角线元素均为1 （每个结点自身可达） （2）可通过图的邻接矩阵A的n-1次幂An-1得到 （将其非零元素换为1，主对角线元素均设为1即可） 例：给定有向图D，4个顶点7条边 邻接矩阵为 0 1 0 0 A= 0 0 1 1 1 1 0 1 1 0 0 0 4*4矩阵中有7个1（边） 0 0 1 1 A2= 2 1 0 1 1 1 1 1 0 1 0 0 反映图中任意两个顶点间 有多少长度为2的通路 2 1 0 1 A3= 1 2 1 1 2 2 1 2 0 0 1 1 反映图中任意两个顶点间 有多少长度为3的通路 1 2 1 1 A4= 2 2 2 3 3 3 2 3 2 1 0 1 反映图中任意两个顶点间 有多少长度为4的通路 返回 3 4 2 3 B4= 5 5 4 6 7 7 4 7 3 2 1 2 反映图中任意两个顶点间 有多少长度为小于等于 4的通路 返回返回 1)确定该有向图的邻接矩阵A（D） 2)D中v2到v4长度为1，2，3，4的通路分别为 条 3)v4到自身长度为1，2，3，4的回路分别为 条. 4)D中v3到v4长度小