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

《离散数学 图论-矩阵表示.pptx》由会员分享，可在线阅读，更多相关《离散数学 图论-矩阵表示.pptx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图图的矩阵表示的矩阵表示14.4 14.4 图的图的矩阵表示矩阵表示n图可用集合或图形表示，也可用矩阵表示，便于用代图可用集合或图形表示，也可用矩阵表示，便于用代数方法研究图的性质。数方法研究图的性质。n用用矩阵表示图之前，必须将图的顶点或边矩阵表示图之前，必须将图的顶点或边标定顺序标定顺序，使其成为标定图使其成为标定图1 1、无向图的、无向图的关联矩阵关联矩阵1 1）定义：设定义：设无向图无向图G GVE，V Vvv1 1,v,v2 2,，v vn n。E=eE=e1 1,e,e2 2,e,e3 3，e em m,令令m mijij为顶点为顶点v vi i与边与边e ej j的关联次数的关联

2、次数，则称则称(m(mijij)nxmnxm为为G G的关联矩阵，记作的关联矩阵，记作 M(G)M(G)2 2）性质）性质:关联矩阵关联矩阵是是n n行（结点数）行（结点数）m m列（边数）列（边数）的矩阵的矩阵3 3）M(G)M(G)每列元素之和均为每列元素之和均为2 2，这正说明每条边关联两个顶，这正说明每条边关联两个顶点点(环所关联的两个端点重合环所关联的两个端点重合)i i m mijij =2 =2 (j=1j=1，2 2，m)m)4 4）M(G)M(G)第第i i行元素之和为结点行元素之和为结点vivi的的度数度数，j j m mijij =d(vi)(i d(vi)(i=1=1，

3、2 2，n)n)5 5)所有行的和（即矩阵所有元素之和）等于边数的所有行的和（即矩阵所有元素之和）等于边数的2 2倍倍 d(vi)d(vi)m mijij 2m2m，（即各顶点的度数之和等于边数的（即各顶点的度数之和等于边数的2 2倍）倍）6 6）第）第j j列与第列与第k k列相同，当且仅当边列相同，当且仅当边ejej与与ekek是平行边是平行边7 7）j j m mijij=0,0,第第i i行行元素元素和和为为0,0,当且仅当当且仅当vivi是是孤立点孤立点,2 1 1 1 0M(G)=0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 v4v1v2v3e1e2e3e4e52 2

4、、有向图的、有向图的关联矩阵关联矩阵1)1)定义：定义：设有向图设有向图D DVE中无环，中无环，V Vvv1 1，v v2 2，v vn n,E,Eeel l，e e2 2,，e em m，令令 1 v1 vi i为边为边e ej j的的起点起点(始点始点)m mijij=0 v0 vi i为边为边e ej j不关联不关联 1 v1 vi i为边为边e ej j的的终点终点则则称称(m(mijij)nxmnxm，为，为D D的关联矩阵，记作的关联矩阵，记作M(DM(D）2)2)有向图关联矩阵的性质有向图关联矩阵的性质(1)1)每列恰好一个每列恰好一个+1+1和一个和一个-1-1；j j m

5、mijij=0=0，j j1 1，2 2，m m，从而，从而 m mijij=0=0 这说明这说明M(D)M(D)中所有元素之和为中所有元素之和为0 0(2)M(D)(2)M(D)中，负中，负1 1的个数等于正的个数等于正1 1的个数，都等于的个数，都等于边数边数m m，这正是有向图握手定理的内容（入，这正是有向图握手定理的内容（入度之和等于出度之和）度之和等于出度之和）(3)(3)第第i i行中，正行中，正1 1的个数等于的个数等于d d+(v(vi i)（结点的出度）（结点的出度），负，负1 1的个数等于的个数等于d d-(v(vi i)（结点的（结点的入度入度）（4 4）平行边所对应的列

6、相同）平行边所对应的列相同 e5v1v2v3e1e2e3 e4v4 -1 1 0 0 0M(D)=1 -1 1 0 0 0 0 0 1 1 0 0 -1 -1-1 3 3、有向图的、有向图的邻接矩阵邻接矩阵 1 1）定义：设有向图）定义：设有向图D DVE，V Vvv1 1，v v2 2，v vn n，E Eee1 1，e e2 2，e em m 令：令：a aijij为顶点为顶点v vi i邻接到顶点邻接到顶点v vj j边的条数边的条数 称称(a aijij)nxnnxn为为D D的邻接矩阵，记作的邻接矩阵，记作A(D)A(D)，或简记为或简记为A A 2 2）邻接矩阵的性质）邻接矩阵的性

7、质 （1 1）每列元素之和每列元素之和为结点的为结点的入度入度，即即 j ja aijij=d d-(v vi i)，i=1i=1，2 2，n n 所有所有列的和列的和 a aijij d d-(v(vi i)m m，等于边数等于边数 每每行元素之和行元素之和为结点的为结点的出度出度，所有行的和也等于边数，所有行的和也等于边数 （2 2）邻接矩阵中元素）邻接矩阵中元素 a aijij 反映了反映了有向图中结点有向图中结点v vi i到到v vj j通路长度为通路长度为1 1的条数的条数 （3 3）A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的（边）通路总条数的（

8、边）通路总条数。主主对角线的元素值为图中结点对角线的元素值为图中结点v vi i长度为长度为1 1 的的环的条环的条数。数。n利用利用A(D)A(D)确定确定D D中长度为中长度为L L的通路数和回路数的通路数和回路数,就需要用到邻接矩就需要用到邻接矩阵的幂次阵的幂次运算运算（4 4）A A2 2中的元素值中的元素值b bijij是结点是结点v vi i到到v vj j长度为长度为2 2 的通路条的通路条数数;说明：由矩阵的乘积定义说明：由矩阵的乘积定义 b bijij=k k a aikik*a*akjkj 由此可推断，由此可推断，A A3 3矩阵中矩阵中的的c cijij元素值，表示从元素

9、值，表示从 v vi i到到v vj j 到长度恰为到长度恰为3 3的的通路通路数数;（5 5）定理）定理1414.11 11 设设A A为有向图为有向图D D的邻接矩阵，的邻接矩阵，V Vvv1 1，v v2 2，v vn n 为为D D的顶点集，的顶点集，则则A A的的L L次幂次幂A AL L(L1)(L1)中元素中元素c cijij为为D D中中v vi i到到v vj j长度为长度为L L的通路数的通路数，其中其中c ciiii为为v vi i到自身长度为到自身长度为L L的回路的回路数数,c cijij(所有元素之和所有元素之和)为为D D中长度为中长度为L L的的通路总数通路总数

10、，其中其中 c ciiii为为D D中长度为中长度为L L的的回路总数回路总数推论推论:设设B BL LA+AA+A2 2十十+A+AL L(L1)(L1)，则则B BL L中元素中元素 b bijij为为D D中中从从 v vi i到到v vj j 长度小于或等于长度小于或等于L L的的通路数通路数，其中主对角线上元素值为其中主对角线上元素值为D D中长度小于或等于中长度小于或等于L L的的回路回路数数。4 4、有向图的可达矩阵、有向图的可达矩阵 1 1）定义：设）定义：设D DVE为有向图为有向图,V,Vvv1 1，v v2 2，v vn n 令令 1 1 vivi可达可达vjvj p p

11、ijij 0 0 否则否则 称称(p(pijij)nxnnxn为为D D的的可达矩阵可达矩阵，记作，记作P(D)P(D)，简记为，简记为P P 2 2）可达矩阵的性质）可达矩阵的性质 （1 1）主对角线元素均为）主对角线元素均为1 1（每个结点自身可达）（每个结点自身可达）（2 2）可通过图的邻接矩阵可通过图的邻接矩阵A A的的n-1n-1次次幂幂A An-1n-1得到得到 （将其非零元素换为将其非零元素换为1 1，主对角线元素均设为，主对角线元素均设为1 1即可）即可）例：给定有向图D，4个顶点7条边 邻接矩阵为 0 1 0 0A=0 0 1 1 1 1 0 1 1 0 0 0 4*4矩阵中

12、有7个1（边）0 0 1 1A2=2 1 0 1 1 1 1 1 0 1 0 0 反映图中任意两个顶点间有多少长度为长度为2的通路的通路 2 1 0 1A3=1 2 1 1 2 2 1 2 0 0 1 1 反映图中任意两个顶点间有多少长度为长度为3的通路的通路 1 2 1 1A4=2 2 2 3 3 3 2 3 2 1 0 1 反映图中任意两个顶点间有多少长度为长度为4的通路的通路返回返回 3 4 2 3B4=5 5 4 6 7 7 4 7 3 2 1 2 反映图中任意两个顶点间有多少长度为小于等于长度为小于等于4的通路的通路返回返回返回返回1)1)确定该有向图的邻接矩阵确定该有向图的邻接矩阵A A（D D）2)D2)D中中v2v2到到v4v4长度为长度为1 1，2 2，3 3，4 4的通路分别的通路分别为为 条条3 3)v)v4 4到自身长度为到自身长度为1 1，2 2，3 3，4 4的回路分别为的回路分别为 条条.4)D4)D中中v3v3到到v4v4长度小于或等于长度小于或等于4 4的通路有的通路有 条条.5)D5)D中中v1v1到到v4v4长度小于或等于长度小于或等于4 4的通路有的通路有 条条.返回小结n无向图的关联矩阵n有向图的关联矩阵n有向图的邻接矩阵幂运算求长度L的通路数n有向图的可达矩阵邻接矩阵A的n-1n-1次幂次幂A An-1n-1得到得到