离散数学第七章第三节

1、1第7-3讲 图的矩阵表示1. 邻接矩阵2. 可达性矩阵和连通矩阵3. 关联矩阵4. 课堂练习5. 第7-3讲 作业21、邻接矩阵（1）定义1 设设G=简单图简单图,它有它有n个结点个结点v1, v2,vn V， 则则n阶阶方阵方阵A(G)=(aij)称为称为G的邻接矩阵，这里的邻接矩阵，这里例如，左下图的例如，左下图的邻接矩阵邻接矩阵列于右侧：列于右侧：jivvvvajijiij或不邻接邻接010001101111000010)(GA31、邻接矩阵（2） 图的邻接矩阵显然与图的邻接矩阵显然与n个结点的标定次序有关，因而同一个个结点的标定次序有关，因而同一个图可得出不同的邻接矩阵。不过这些矩阵

2、可以通过交换行和图可得出不同的邻接矩阵。不过这些矩阵可以通过交换行和列而相互得出。具有这样性质的矩阵称它们列而相互得出。具有这样性质的矩阵称它们置换等价。 例如，左下图的两个例如，左下图的两个置换等价邻接矩阵置换等价邻接矩阵：0001101111000010)(GA010000011101101041324132vvvvvvvv 置换等价是置换等价是n阶布尔矩阵集合上的一个等价关系。阶布尔矩阵集合上的一个等价关系。 我们忽略邻接矩阵的多样性，可取图我们忽略邻接矩阵的多样性，可取图G的任一邻接矩阵视为的任一邻接矩阵视为该图的邻接矩阵该图的邻接矩阵41、邻接矩阵（3） 简单有向图简单有向图G的邻接

3、矩阵的邻接矩阵A(G)=(aij)n n的第的第i行元素之和等于行元素之和等于vi的出度。第的出度。第j列元素之和等于列元素之和等于vj的入度。的入度。 例如，左下有向图中，例如，左下有向图中， v3的出度的出度=1+1+0+1=3， v3的入度的入度=0+1+0+0=10001101111000010)(GA010000011101101041324132vvvvvvvv51、邻接矩阵（4）定理1 设简单有向图设简单有向图G=的邻接矩阵为的邻接矩阵为A，则矩阵，则矩阵Ak中的中的第第i行第行第j列元素等于列元素等于G中连结中连结vi与与vj长度为长度为k的路的数目的路的数目 。 例如，左下有

4、向图，例如，左下有向图， A2中的第中的第2行第行第1列元素等于列元素等于2，说明连，说明连结结v2与与v1长度为长度为2的路的有两条：的路的有两条： v2 v4 v1 ， v2 v3 v1 。0001101111000010)(GA00101111101211002A分析分析: a21(2)= a21a11+a22a21+ a23a31+a24a41=00+00+11+11=2注意从注意从v2到到v1长度为长度为2的路中间必经由一个结点的路中间必经由一个结点vk,即即v2 vk v1(1 k 4)。K=3时，时，a23 a31= 11表示表示v2到到v3、v3到到v1有路有路(边边)。61、

5、邻接矩阵（5）定理1 设简单有向图设简单有向图G=的邻接矩阵为的邻接矩阵为A，则矩阵，则矩阵Ak中的中的第第i行第行第j列元素等于列元素等于G中连结中连结vi与与vj长度为长度为k的路的数目的路的数目 。 证明思路分析：对此定理不作全面证明。从对此定理不作全面证明。从A A2 2为例作一些说为例作一些说明。计算明。计算连结连结vi与与vj长度为长度为2的路的数目，注意从的路的数目，注意从vi到到vj长度为长度为2的路中间必经由一个结点的路中间必经由一个结点vk,即即vi vk vj(1 k n)，而且，而且aik=akj=1，那么，那么aikakj=1。反之，如果不存在路径。反之，如果不存在路

6、径vi vk vj，则，则aik=0或或akj=0，从而，从而aikakj=0。所以从。所以从vi到到vj长度为长度为2的路径的的路径的数目等于数目等于nkkjiknjinjijijkijnijijiaaaaaaaavvvvvvvvvvvv1221121.按矩阵的乘法法则，此和式恰好是按矩阵的乘法法则，此和式恰好是A2中中第第i行第行第j列元素列元素aij(2)。71、邻接矩阵（6）定理1 设简单有向图设简单有向图G=的邻接矩阵为的邻接矩阵为A，则矩阵，则矩阵Ak中的中的第第i行第行第j列元素等于列元素等于G中连结中连结vi与与vj长度为长度为k的路的数目的路的数目 。 证明思路分析(续)：计

7、算计算连结连结vi与与vj长度为长度为3的路径的数目，的路径的数目，注意从注意从vi到到vj长度为长度为3的路径可视为从的路径可视为从vi 到中间结点到中间结点vk长度为长度为1的路径，再加上从的路径，再加上从vk到到vj长度为长度为2的路径，所以从的路径，所以从vi到到vj长度为长度为3的路径的数目等于的路径的数目等于23)3(1)2()3()(AAAaaaannijnkkjikij那么0001101111000010A00101111101211002A11002122112110123A82、可达性矩阵和连通矩阵(1)定义2 设G=为简单有向图，V=v1,v2,vn，定义矩阵P=（pij

8、）,其中 有向图有向图G G中从中从v vi i到到v vj j是否有路可达可通过矩阵运算而得到。是否有路可达可通过矩阵运算而得到。 由图G的邻接矩阵A可得可达性矩阵P，令，令 Bn=A+A2+An=(bij)n nBn中的元素中的元素bij表示表示从从v vi i到到v vj j是长度等于或小于是长度等于或小于n n的路径数。若的路径数。若bij 0，则表示，则表示从从v vi i到到v vj j可达。这样，将可达。这样，将Bn中不为零的元素全中不为零的元素全部换成部换成1，而等于零的元素保持不变，即得可达矩阵。，而等于零的元素保持不变，即得可达矩阵。不存在路到从至少存在一条路到从jiji0

9、1vvvvpijP称为图G的可达性矩阵。92、可达性矩阵和连通矩阵(2)求可达性矩阵可简化为：(1) 由图G的邻接矩阵A求可达性矩阵P: P=A(1) A(2) A(n) 其中的元素其中的元素A(i)表示表示Ai对应的布尔对应的布尔矩阵矩阵。(2)用Warshall算法计算： 因为有向简单图的邻接矩阵因为有向简单图的邻接矩阵A A可视为具有可视为具有n n个结点的集合个结点的集合V V 上上的邻接关系的邻接关系R R的关系矩阵，而可达矩阵可视为邻接关系的关系矩阵，而可达矩阵可视为邻接关系R R的传递的传递闭包所对应的矩阵。闭包所对应的矩阵。 设设A=(aA=(aijij) )n n、 B=(b

10、B=(bijij) )n n是是布尔矩阵，令布尔矩阵，令C=AC=A B=(cB=(cijij) )n n，称为称为布尔矩阵求“和”；令令D=AD=A B=(dB=(dijij) )n n，称为，称为布尔矩阵求“积”。其中：其中：kjiknkijijijijbadbac1102、可达性矩阵和连通矩阵(3)方法方法1：先由邻接矩阵A求B4, B4=A+A2+A3+A4然后写出可达矩阵然后写出可达矩阵P。 计算可达矩阵举例:0000101111001010A00002110101111002A00002111211010113A00003121211121104A00001111111111110

11、0008353633252314PB00001111111111110000111111111110000011111110101100001110101111000000101111001010p方法方法2：将A、A2、A3、A4转换为布尔矩阵A(1)、A(2)、A(3)、A(4)， 则则 P=A(1) A(2) A(3) A(4)。 112、可达性矩阵和连通矩阵(4)(3)用Warshall算法计算:计算可达矩阵举例（续）:0000101111001010A00002110101111002A00002111211010113A00003121211121104A4321000011111

12、1111111:0000111111111111:0000111111001110:0000101111001010:0000101111001010:iiiiAPM123、关联矩阵(1)定义3 设G=为无向图，V=v1,v2,vp， E=e1,e2,eq，定义矩阵M(G)=(mij)pq,其中例如，写出下图的关联矩阵。例如，写出下图的关联矩阵。jiji01evevmij不关联关联M(G)称为图G的完全关联矩阵。000000011000101100000111110011)(54321654321vvvvveeeeeeGM133、关联矩阵(2)从完全关联矩阵可得出图的有关信息：从完全关联矩阵可

13、得出图的有关信息： (1)(1)因每边只关联两个结点，故每列有且只有两个因每边只关联两个结点，故每列有且只有两个1 1，其余，其余为为0 0。 (2)(2)每行各元素之和即相应结点的度数。每行各元素之和即相应结点的度数。 (3)(3)若某行各元素皆为若某行各元素皆为0 0，则相应结点为孤立结点。，则相应结点为孤立结点。 (4)(4)平行边所对应的列完全相同。平行边所对应的列完全相同。 (5)(5)同一个图取不同的点、边序列，其对应的关联矩阵仅同一个图取不同的点、边序列，其对应的关联矩阵仅存在行序和列序的差异。存在行序和列序的差异。000000011000101100000111110011)(

14、54321654321vvvvveeeeeeGM143、关联矩阵(3)定义4 设G=为简单有向图，V=v1,v2,vp， E=e1,e2,eq，定义矩阵M(G)=(mij)pq,其中例如，写出如下简单有向图的关联矩阵。例如，写出如下简单有向图的关联矩阵。不关联与的终点是的起点是jijiji011evevevmijM(G)称为有向图G的完全关联矩阵。00110000101100100011000000111110001)(543217654321vvvvveeeeeeeGM153、关联矩阵(4)从有向图的完全关联矩阵可得出图的有关信息：从有向图的完全关联矩阵可得出图的有关信息： (1) (1)

15、每边关联一个始点，一个终点。故每列只有一个元素为每边关联一个始点，一个终点。故每列只有一个元素为1 1，一个元素为一个元素为-1-1，其余为，其余为0 0。 (2)(2)每行的每行的1 1之和即相应结点的出度，之和即相应结点的出度，-1-1之和即相应结点的入之和即相应结点的入度。度。 (3)(3)若某行各元素皆为若某行各元素皆为0 0，则相应结点为孤立结点。，则相应结点为孤立结点。 (4)(4)平行边所对应的列完全相同。平行边所对应的列完全相同。 00110000101100100011000000111110001)(543217654321vvvvveeeeeeeGM163、关联矩阵(5)

16、定理2 设连通图G有r个结点，则其完全关联矩阵的秩为r-1。 (证明从略)两个关于关联矩阵的秩的结论：推 论 设图G有r个结点，w个最大连通子图，则图G的完全关联矩阵的秩为r-w。注：(1) 矩阵中的任意矩阵中的任意k阶方阵的行列式该矩阵的阶方阵的行列式该矩阵的k阶子式。阶子式。(2) 矩阵矩阵A中不为中不为0的子式的最大阶数的子式的最大阶数r叫叫A的秩。的秩。(3) 交换矩阵中两行或两列；用非零数乘矩阵的某行或某列；交换矩阵中两行或两列；用非零数乘矩阵的某行或某列；用非零数乘矩阵的某行或某列后再加到另一行或列的对应元素上。以用非零数乘矩阵的某行或某列后再加到另一行或列的对应元素上。以上三种变换叫矩阵的初等变换。初等变换不改变矩阵的秩。上三种变换叫矩阵的初等变换。初