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

《离散数学 图论-矩阵表示.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的矩阵表示§14.4图的矩阵表示图可用集合或图形表示，也可用矩阵表示，便于用代数方法研究图的性质。用矩阵表示图之前，必须将图的顶点或边标定顺序，使其成为标定图1、无向图的关联矩阵1）定义：设无向图G＝，V＝{v1,v2,…，vn}。E={e1,e2,e3，…em},令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的关联矩阵，记作M(G)．2）性质:关联矩阵是n行（结点数）m列（边数）的矩阵3）M(G)每列元素之和均为2，这正说明每条边关联两个顶点(环所关联的两个端点重合)．∑imij=2(j=1，2，…，m)4）M(G)第i行元素之和为结点vi的度数，∑jmij=d

2、(vi)(i=1，2，…，n)5)所有行的和（即矩阵所有元素之和）等于边数的2倍∑d(vi)＝∑∑mij＝2m，（即各顶点的度数之和等于边数的2倍）．6）第j列与第k列相同，当且仅当边ej与ek是平行边．7）∑jmij=0,第i行元素和为0,当且仅当vi是孤立点,21110M(G)=011000001100001v4v1v2v3e1e2e3e4e52、有向图的关联矩阵1)定义：设有向图D＝中无环，V＝{v1，v2，…，vn},E＝{el，e2,…，em}，令1vi为边ej的起点(始点)mij=0vi为边ej不关联－1vi为边ej的终点则称(mij)nxm，为D的关联矩阵，记作M(D

3、）2)有向图关联矩阵的性质(1)每列恰好一个+1和一个-1；∑jmij=0，j＝1，2，…，m，从而∑∑mij=0这说明M(D)中所有元素之和为0(2)M(D)中，负1的个数等于正1的个数，都等于边数m，这正是有向图握手定理的内容（入度之和等于出度之和）(3)第i行中，正1的个数等于d+(vi)（结点的出度），负1的个数等于d-(vi)（结点的入度）．（4）平行边所对应的列相同e5v1v2v3e1e2e3e4v4-11000M(D)=1-11000001100-1-1-13、有向图的邻接矩阵1）定义：设有向图D＝，V＝{v1，v2，…，vn}，E＝{e1，e2，…，em}令：aij

4、为顶点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的环的条数。利用A(D)确定D中长度为L的通路数和回路数,就需要用到邻接矩阵的幂次运算（4）A2中的元素值bij是结点vi到vj长度为2的通路

5、条数;说明：由矩阵的乘积定义bij=∑kaik*akj由此可推断，A3矩阵中的cij元素值，表示从vi到vj到长度恰为3的通路数;（5）定理14.11设A为有向图D的邻接矩阵，V＝{v1，v2，…，vn}为D的顶点集，则A的L次幂AL(L≥1)中元素cij为D中vi到vj长度为L的通路数，其中cii为vi到自身长度为L的回路数,∑∑cij(所有元素之和)为D中长度为L的通路总数，其中∑cii为D中长度为L的回路总数．推论:设BL＝A+A2十…+AL(L≥1)，则BL中元素bij为D中从vi到vj长度小于或等于L的通路数，其中主对角线上元素值为D中长度小于或等于L的回路数。4、有向图的可达矩阵

6、1）定义：设D＝为有向图,V＝{v1，v2，…，vn}令1vi可达vjpij＝0否则称(pij)nxn为D的可达矩阵，记作P(D)，简记为P2）可达矩阵的性质（1）主对角线元素均为1（每个结点自身可达）（2）可通过图的邻接矩阵A的n-1次幂An-1得到（将其非零元素换为1，主对角线元素均设为1即可）例：给定有向图D，4个顶点7条边邻接矩阵为0100A=0011110110004*4矩阵中有7个1（边）0011A2=210111110100反映图中任意两个顶点间有多少长度为2的通路2101A3=121122120011反映图中任意两个顶点间有多少长度为3的通路1211A4=22233

7、3232101反映图中任意两个顶点间有多少长度为4的通路返回3423B4=554677473212反映图中任意两个顶点间有多少长度为小于等于4的通路返回返回1)确定该有向图的邻接矩阵A（D）2)D中v2到v4长度为1，2，3，4的通路分别为条．3)v4到自身长度为1，2，3，4的回路分别为条.4)D中v3到v4长度小于或等于4的通路有条.5)D中v1到v4长度小于或等于4的通路有条.返回小结无向图的关联矩阵有