图的矩阵表示幻灯片.ppt

《图的矩阵表示幻灯片.ppt》由会员分享，可在线阅读，更多相关《图的矩阵表示幻灯片.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的矩阵表示第1页，共26页，编辑于2022年，星期五定义定义定义定义1 1 设设设设 GG(VV,E E)为简单图，它有为简单图，它有为简单图，它有为简单图，它有 n n 个结点个结点个结点个结点 VV v v1 1,v v2 2,v vn n，则，则，则，则 n n 阶方阵阶方阵阶方阵阶方阵 称为称为称为称为 G G 的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵。其中其中其中其中 v v2 2v v4 4v v5 5v v3 3v v1 1v v2 2v v4 4v v5 5v v3 3v v1 1无向图无向图无向图无向图第2页，共26页，编辑于2022年，星期五有向图有向图有向图有向图 如果

2、给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。v v1 1v v2 2v v4 4v v3 3GG1 1v v2 2v v1 1v v4 4v v3 3GG2 2第3页，共26页，编辑于2022年，星期

3、五 用用用用图图图图形形形形表表表表示示示示图图图图的的的的方方方方法法法法，关关关关于于于于结结结结点点点点间间间间的的的的通通通通路路路路很很很很容容容容易易易易在在在在图图图图形形形形中中中中看看看看出出出出来来来来，但但但但在在在在邻邻邻邻接接接接矩矩矩矩阵阵阵阵中中中中就就就就需需需需经经经经过过过过计计计计算算算算。设设设设有有有有向向向向图图图图 G G 的的的的结结结结点点点点集集集集 VV v v1 1,v v2 2,v vn n，它的，它的，它的，它的邻接矩阵邻接矩阵邻接矩阵邻接矩阵为：为：为：为：AA(GG)(a aijij)n nn n，现现现现在在在在我我我我们们们们

4、来来来来计计计计算算算算从从从从结结结结点点点点 v vi i 到到到到结结结结点点点点 v vj j 的的的的长长长长度度度度为为为为 2 2 的的的的路路路路的的的的数数数数目目目目。注注注注意意意意到到到到每每每每条条条条从从从从结结结结点点点点 v vi i 到到到到结结结结点点点点 v vj j 的的的的长长长长度度度度为为为为2 2的的的的路路路路的的的的中中中中间间间间必必必必经经经经过过过过一一一一个个个个结结结结点点点点v vk k，即即即即v vi iv vk kv vj j(1(1k kn n)，如如如如果果果果图图图图中中中中有有有有路路路路 v vi iv vk kv

5、 vj j 存存存存在在在在，那那那那么么么么 a aikika akjkj1 1，即即即即 a aikik a akjkj1 1，反反反反之之之之如如如如果果果果图图图图 G G 中中中中不不不不存存存存在在在在路路路路 v vi iv vk kv vj j，那那那那么么么么 a aikik0 0 或或或或 a akjkj0 0，即即即即 a aikik a akjkj0 0，于是从结点，于是从结点，于是从结点，于是从结点 v vi i 到结点到结点到结点到结点 v vj j 的长度为的长度为的长度为的长度为 2 2 的路的数目等于：的路的数目等于：的路的数目等于：的路的数目等于：第4页，共

6、26页，编辑于2022年，星期五 按照矩阵的乘法规则，这恰好是矩阵中的第按照矩阵的乘法规则，这恰好是矩阵中的第按照矩阵的乘法规则，这恰好是矩阵中的第按照矩阵的乘法规则，这恰好是矩阵中的第 i i 行，第行，第行，第行，第 j j 列列列列的元素。的元素。的元素。的元素。表示从结点表示从结点表示从结点表示从结点 v vi i 到结点到结点到结点到结点 v vj j 的长度为的长度为的长度为的长度为 2 2 的路的数目。的路的数目。的路的数目。的路的数目。表示从结点表示从结点表示从结点表示从结点 v vi i 到结点到结点到结点到结点 v vi i 的长度为的长度为的长度为的长度为 2 2 的回路

7、的数目。的回路的数目。的回路的数目。的回路的数目。第5页，共26页，编辑于2022年，星期五 从结点从结点从结点从结点 v vi i 到结点到结点到结点到结点 v vj j 的一条长度为的一条长度为的一条长度为的一条长度为 3 3 的路，可以看作从的路，可以看作从的路，可以看作从的路，可以看作从结点结点结点结点 v vi i 到结点到结点到结点到结点 v vk k 的长度为的长度为的长度为的长度为 1 1 的路，和从结点的路，和从结点的路，和从结点的路，和从结点 v vk k 到结点到结点到结点到结点 v vj j 的长度为的长度为的长度为的长度为 2 2 的路，故从结点的路，故从结点的路，故

8、从结点的路，故从结点 v vi i 到结点到结点到结点到结点 v vj j 的一条长度为的一条长度为的一条长度为的一条长度为 3 3 的路的路的路的路的数目：的数目：的数目：的数目：即：即：即：即：第6页，共26页，编辑于2022年，星期五一般地有一般地有一般地有一般地有上述这个结论对无向图也成立。上述这个结论对无向图也成立。上述这个结论对无向图也成立。上述这个结论对无向图也成立。第7页，共26页，编辑于2022年，星期五定理定理定理定理2 2 设设设设 A(G)A(G)为图为图为图为图 G G 的邻接矩阵，则的邻接矩阵，则的邻接矩阵，则的邻接矩阵，则 (A(G)(A(G)l l 中的中的中的

9、中的 i i 行行行行 j j 列元素列元素列元素列元素 等于等于等于等于 G G 中连接结点中连接结点中连接结点中连接结点 v vi i 与与与与 v vj j 的长度为的长度为的长度为的长度为 l l 的路的数目。的路的数目。的路的数目。的路的数目。证明：归纳法证明。证明：归纳法证明。证明：归纳法证明。证明：归纳法证明。(1)(1)当当当当 l l2 2 时，由上得知是显然成立。时，由上得知是显然成立。时，由上得知是显然成立。时，由上得知是显然成立。(2)(2)设命题对设命题对设命题对设命题对 l l 成立，由成立，由成立，由成立，由 故故故故 第8页，共26页，编辑于2022年，星期五

10、根据邻接矩阵的定义根据邻接矩阵的定义根据邻接矩阵的定义根据邻接矩阵的定义 a aikik 表示连接表示连接表示连接表示连接 v vi i 与与与与 v vk k 长度为长度为长度为长度为 1 1 的路的路的路的路的数目，而的数目，而的数目，而的数目，而 是连接是连接是连接是连接 v vk k 与与与与 v vj j 长度为长度为长度为长度为 l l 的路的数目，式的路的数目，式的路的数目，式的路的数目，式 中每一项表示由中每一项表示由中每一项表示由中每一项表示由 v vi i 经过一条边到经过一条边到经过一条边到经过一条边到 v vk k，再由，再由，再由，再由 v vk k 经过长度为经过长

11、度为经过长度为经过长度为 l l 的的的的路到路到路到路到 v vj j 的，总长度为的，总长度为的，总长度为的，总长度为 l l 1 1 的路的数目。对所有的的路的数目。对所有的的路的数目。对所有的的路的数目。对所有的 k k 求和，求和，求和，求和，即是所有从即是所有从即是所有从即是所有从 v vi i 到到到到 v v 的长度为的长度为的长度为的长度为 l l 1 1 的路的数目，故命题对成的路的数目，故命题对成的路的数目，故命题对成的路的数目，故命题对成立。立。立。立。第9页，共26页，编辑于2022年，星期五【例例例例3 3】给定一图给定一图给定一图给定一图 GG(V,E)(V,E)

12、如下图所示。如下图所示。如下图所示。如下图所示。v v3 3v v1 1v v2 2v v4 4v v5 5解：解：解：解：从矩阵中可以看到，从矩阵中可以看到，从矩阵中可以看到，从矩阵中可以看到，v v1 1 与与与与 v v2 2 之间有两条之间有两条之间有两条之间有两条长度为长度为长度为长度为 3 3 的路，结点的路，结点的路，结点的路，结点 v v1 1 与与与与 v v3 3 之间有一条之间有一条之间有一条之间有一条长度为长度为长度为长度为 2 2 的路，在结的路，在结的路，在结的路，在结点点点点 v v2 2 有四条长度为有四条长度为有四条长度为有四条长度为 4 4 的回路。的回路。

13、的回路。的回路。第10页，共26页，编辑于2022年，星期五 在许多问题中需要判断有向图的一个结点在许多问题中需要判断有向图的一个结点在许多问题中需要判断有向图的一个结点在许多问题中需要判断有向图的一个结点 v vi i 到另一个结点到另一个结点到另一个结点到另一个结点 v vj j 是否存在路的问题。如果利用图是否存在路的问题。如果利用图是否存在路的问题。如果利用图是否存在路的问题。如果利用图 G G 的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵 AA，则可计算，则可计算，则可计算，则可计算 AA，AA2 2，AA3 3，AAn n，当发现其中的某个，当发现其中的某个，当发现其中的某个，当发现其

14、中的某个 AAl l 的的的的 a aijij(l)(l)11，就表明结点，就表明结点，就表明结点，就表明结点 v vi i 到到到到 v vj j 可达。但这种计算比较繁琐，且可达。但这种计算比较繁琐，且可达。但这种计算比较繁琐，且可达。但这种计算比较繁琐，且 AAl l 不不不不知计算到何时为止。从前面得知，如果有向图知计算到何时为止。从前面得知，如果有向图知计算到何时为止。从前面得知，如果有向图知计算到何时为止。从前面得知，如果有向图 G G 有有有有 n n 个结点个结点个结点个结点VVvv1 1,v,v2 2,v,vn n v vi i 到到到到 v vj j 有一条路，则必有一条长

15、度不超过有一条路，则必有一条长度不超过有一条路，则必有一条长度不超过有一条路，则必有一条长度不超过 n n 的通路，的通路，的通路，的通路，因此只要考察因此只要考察因此只要考察因此只要考察 a aijij(l)(l)就可以了，其中就可以了，其中就可以了，其中就可以了，其中 1ln1ln。对于有向图。对于有向图。对于有向图。对于有向图 G G 中任意两个结点之间的可达性，亦可用可达矩阵。中任意两个结点之间的可达性，亦可用可达矩阵。中任意两个结点之间的可达性，亦可用可达矩阵。中任意两个结点之间的可达性，亦可用可达矩阵。第11页，共26页，编辑于2022年，星期五定义定义定义定义4 4 令令令令 G

16、G 是一个简单有向图，是一个简单有向图，是一个简单有向图，是一个简单有向图，假定，假定，假定，假定 VV 的结点已编序，即的结点已编序，即的结点已编序，即的结点已编序，即 VV v v1 1,v v2 2,v vn n，定义一个，定义一个，定义一个，定义一个 n nn n 矩阵矩阵矩阵矩阵 。其中。其中。其中。其中 称矩阵称矩阵称矩阵称矩阵 P P 是图是图是图是图 G G 的的的的可达性矩阵可达性矩阵可达性矩阵可达性矩阵。第12页，共26页，编辑于2022年，星期五 可达性矩阵表明了图中任意两个结点间是否至少存在一条路可达性矩阵表明了图中任意两个结点间是否至少存在一条路可达性矩阵表明了图中任

17、意两个结点间是否至少存在一条路可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。以及在任何结点上是否存在回路。以及在任何结点上是否存在回路。以及在任何结点上是否存在回路。一般地可由图一般地可由图一般地可由图一般地可由图 G G 的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵 A A 得到可达性矩阵得到可达性矩阵得到可达性矩阵得到可达性矩阵 P P。即。即。即。即令令令令 BBn nAA AA2 2 AAn n，在从，在从，在从，在从 BBn n 中将不为中将不为中将不为中将不为 0 0 的元素改为的元素改为的元素改为的元素改为 1 1，而为零的元素不变，这样改换的矩阵

18、即为可达性矩阵而为零的元素不变，这样改换的矩阵即为可达性矩阵而为零的元素不变，这样改换的矩阵即为可达性矩阵而为零的元素不变，这样改换的矩阵即为可达性矩阵 P P。Warshall Warshall 算法可以由邻接矩阵求可达性矩阵算法可以由邻接矩阵求可达性矩阵算法可以由邻接矩阵求可达性矩阵算法可以由邻接矩阵求可达性矩阵 P P。第13页，共26页，编辑于2022年，星期五【例例例例5 5】求下图的可达性矩阵。求下图的可达性矩阵。求下图的可达性矩阵。求下图的可达性矩阵。p p2 2p p1 1p p3 3p p5 5p p4 4解：解：解：解：第14页，共26页，编辑于2022年，星期五同理可得：

19、同理可得：同理可得：同理可得：第15页，共26页，编辑于2022年，星期五 可达性矩阵的概念可以推广到无向图中，只要将无向图的每一可达性矩阵的概念可以推广到无向图中，只要将无向图的每一可达性矩阵的概念可以推广到无向图中，只要将无向图的每一可达性矩阵的概念可以推广到无向图中，只要将无向图的每一条边看成是具有相反方向的两条边，这样，一个无向图就可以看成条边看成是具有相反方向的两条边，这样，一个无向图就可以看成条边看成是具有相反方向的两条边，这样，一个无向图就可以看成条边看成是具有相反方向的两条边，这样，一个无向图就可以看成是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连是有向图。无向图的

20、邻接矩阵是一个对称矩阵，其可达矩阵称为连是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连通矩阵。通矩阵。通矩阵。通矩阵。对于一个无向图对于一个无向图对于一个无向图对于一个无向图 GG，除了可用邻接矩阵以外，还对应着一个，除了可用邻接矩阵以外，还对应着一个，除了可用邻接矩阵以外，还对应着一个，除了可用邻接矩阵以外，还对应着一个称为图称为图称为图称为图 G G 的的的的完全关联矩阵完全关联矩阵完全关联矩阵完全关联矩阵，假定图，假定图，假定图，假定图 G G 无自回路，如因某种运算得无自回路，如因某种运算得无自回路，如因某种运算得无

21、自回路，如因某种运算得到自回路，则将它删去。到自回路，则将它删去。到自回路，则将它删去。到自回路，则将它删去。第16页，共26页，编辑于2022年，星期五定义定义定义定义6 6 给定无向图给定无向图给定无向图给定无向图 GG，令，令，令，令 v v1 1,v v2 2,v vp p 和和和和 e e1 1,e e2 2,e eq q 分别记为分别记为分别记为分别记为 G G 的结点和边，则矩阵的结点和边，则矩阵的结点和边，则矩阵的结点和边，则矩阵 MM(GG)(mmij ij)，其中，其中，其中，其中称称称称 MM(GG)为为为为完全关联矩阵完全关联矩阵完全关联矩阵完全关联矩阵。无向图及其完全

22、关联矩阵无向图及其完全关联矩阵无向图及其完全关联矩阵无向图及其完全关联矩阵 v v2 2v v1 1e e3 3e e4 4e e2 2e e1 1e e1 1e e2 2e e3 3e e4 4v v1 11 11 10 01 1v v2 21 11 11 10 0V V3 30 00 01 11 1v3v3第17页，共26页，编辑于2022年，星期五从关联矩阵中可以看出图形的一些性质：从关联矩阵中可以看出图形的一些性质：从关联矩阵中可以看出图形的一些性质：从关联矩阵中可以看出图形的一些性质：（1 1）图中每一边关联两个结点，故）图中每一边关联两个结点，故）图中每一边关联两个结点，故）图中每

23、一边关联两个结点，故 MM(GG)的每一列只有两的每一列只有两的每一列只有两的每一列只有两个个个个 1 1。（2 2）每一行元素的和数对应于结点的度数。）每一行元素的和数对应于结点的度数。）每一行元素的和数对应于结点的度数。）每一行元素的和数对应于结点的度数。（3 3）一行中的元素全为）一行中的元素全为）一行中的元素全为）一行中的元素全为 0 0，其对应的结点为孤立点。，其对应的结点为孤立点。，其对应的结点为孤立点。，其对应的结点为孤立点。（4 4）两个平行边其对应的两列相同。）两个平行边其对应的两列相同。）两个平行边其对应的两列相同。）两个平行边其对应的两列相同。（5 5）同一图当结点或边的

24、编序不同，其对应）同一图当结点或边的编序不同，其对应）同一图当结点或边的编序不同，其对应）同一图当结点或边的编序不同，其对应 MM(GG)仅有行仅有行仅有行仅有行序、列序的差别。序、列序的差别。序、列序的差别。序、列序的差别。当一个图是有向图时，亦可用结点和边的关联矩阵来表示。当一个图是有向图时，亦可用结点和边的关联矩阵来表示。当一个图是有向图时，亦可用结点和边的关联矩阵来表示。当一个图是有向图时，亦可用结点和边的关联矩阵来表示。第18页，共26页，编辑于2022年，星期五定义定义定义定义7 7 给定简单有向图给定简单有向图给定简单有向图给定简单有向图 GG ，V V v v1 1,v v2

25、2,v vp p，E E e e1 1,e e2 2,e eq q，p p q q 阶矩阵阶矩阵阶矩阵阶矩阵 MM(GG)(mmij ij)，其中，其中，其中，其中称称称称 MM(GG)为为为为 G G 的的的的关联矩阵关联矩阵关联矩阵关联矩阵。v v2 2v v1 1e e3 3e e4 4e e2 2e e1 1v v3 3v v4 4e e5 5e e1 1e e2 2e e3 3e e4 4e e5 5v v1 11 10 01 10 01 1v v2 2-1-11 10 00 00 0v v3 30 0-1-1-1-11 10 0v v4 40 00 00 0-1-1-1-1简单有向

26、图及其完全关联矩阵简单有向图及其完全关联矩阵简单有向图及其完全关联矩阵简单有向图及其完全关联矩阵 第19页，共26页，编辑于2022年，星期五有向图的完全关联矩阵也有类于无向图的一些性质。有向图的完全关联矩阵也有类于无向图的一些性质。有向图的完全关联矩阵也有类于无向图的一些性质。有向图的完全关联矩阵也有类于无向图的一些性质。定义定义定义定义8 8 对图对图对图对图 G G 的的的的完全关联矩阵中的两行相加完全关联矩阵中的两行相加完全关联矩阵中的两行相加完全关联矩阵中的两行相加如下：若记如下：若记如下：若记如下：若记 v vi i 对应的行对应的行对应的行对应的行为为为为 ，将第，将第，将第，将

27、第 i i 行与第行与第行与第行与第 j j 行相加，规定为：对有向图是指对应分量行相加，规定为：对有向图是指对应分量行相加，规定为：对有向图是指对应分量行相加，规定为：对有向图是指对应分量的加法运算，对无向图是指对应分量的的加法运算，对无向图是指对应分量的的加法运算，对无向图是指对应分量的的加法运算，对无向图是指对应分量的模模模模 2 2 的加法运算，把这种的加法运算，把这种的加法运算，把这种的加法运算，把这种运算记作运算记作运算记作运算记作 。执行这个运算实际上是对应于把图执行这个运算实际上是对应于把图执行这个运算实际上是对应于把图执行这个运算实际上是对应于把图 G G 的结点的结点的结点

28、的结点 v vi i 与结点与结点与结点与结点 v vj j 合并合并合并合并。第20页，共26页，编辑于2022年，星期五 设图设图设图设图 G G 的结点的结点的结点的结点 v vi i 与结点与结点与结点与结点 v vj j 合并得到图合并得到图合并得到图合并得到图 GG，那么，那么，那么，那么 MM(GG)是将是将是将是将 MM(GG)中的第中的第中的第中的第 i i 行与第行与第行与第行与第 j j 行相加而得到。因为行相加而得到。因为行相加而得到。因为行相加而得到。因为若有关项中第若有关项中第若有关项中第若有关项中第 r r 个对应分量有个对应分量有个对应分量有个对应分量有 ，则说

29、明，则说明，则说明，则说明 v vi i 与与与与 v vj j 两者之中只有一个结点是边两者之中只有一个结点是边两者之中只有一个结点是边两者之中只有一个结点是边 e er r 的端点，且将这两个结点合的端点，且将这两个结点合的端点，且将这两个结点合的端点，且将这两个结点合并后的结点并后的结点并后的结点并后的结点 v vi,ji,j 仍是仍是仍是仍是 e er r 的端点。的端点。的端点。的端点。第21页，共26页，编辑于2022年，星期五若若若若 则有两种情况：则有两种情况：则有两种情况：则有两种情况：（1 1）v vi i 与与与与 v vj j 都不是边都不是边都不是边都不是边 e er

30、 r 的端点，那么的端点，那么的端点，那么的端点，那么 v vi,ji,j 也不是也不是也不是也不是 e er r 的端点。的端点。的端点。的端点。（2 2）v vi i 与与与与 v vj j 都是边都是边都是边都是边 e er r 的端点，那么合并后在的端点，那么合并后在的端点，那么合并后在的端点，那么合并后在 GG中中中中 e er r成为成为成为成为 v vi,ji,j 的自回路，按规则应该被删去。的自回路，按规则应该被删去。的自回路，按规则应该被删去。的自回路，按规则应该被删去。此外，在此外，在此外，在此外，在 M(G)M(G)中若有某些列，其元素全为中若有某些列，其元素全为中若有某

31、些列，其元素全为中若有某些列，其元素全为 0 0，说明，说明，说明，说明 G G 中中中中的一些结点合并后，消失了一些对应边。的一些结点合并后，消失了一些对应边。的一些结点合并后，消失了一些对应边。的一些结点合并后，消失了一些对应边。第22页，共26页，编辑于2022年，星期五【例例例例9 9】无向图无向图无向图无向图 (a)(a)中结点中结点中结点中结点 v v4 4 和和和和 v v5 5 合并得到图合并得到图合并得到图合并得到图(b)(b)。解：其关联矩阵解：其关联矩阵解：其关联矩阵解：其关联矩阵 MM(GG)是由关联矩阵是由关联矩阵是由关联矩阵是由关联矩阵 MM(GG)中将第中将第中将

32、第中将第 4 4 行加到第行加到第行加到第行加到第 5 5 行而得到。行而得到。行而得到。行而得到。e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e7 7v v1 10 00 00 00 00 01 11 1v v2 20 00 00 01 11 11 10 0v v3 30 01 11 11 10 00 00 0v v4 41 11 10 00 00 00 00 0v v5 51 10 01 10 01 10 01 1v v2 2v v1 1e e3 3e e4 4e e2 2e e1 1v v3 3v v4 4e e5 5v v5 5e e7 7e e6 6v

33、 v2 2v v1 1e e3 3e e4 4e e2 2v v3 3e e5 5V V4,54,5e e7 7e e6 6e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e7 7v v1 10 00 00 00 00 01 11 1v v2 20 00 00 01 11 11 10 0v v3 30 01 11 11 10 00 00 0V V4,54,50 01 11 10 01 10 01 1（a a）（b b）第23页，共26页，编辑于2022年，星期五【例例例例1010】有向图有向图有向图有向图(a)(a)中合并结点中合并结点中合并结点中合并结点 v v2

34、 2 和和和和 v v3 3。解：合并时，删去自回路得图解：合并时，删去自回路得图解：合并时，删去自回路得图解：合并时，删去自回路得图 (b)(b)。其关联矩阵。其关联矩阵。其关联矩阵。其关联矩阵 MM(GG)是由是由是由是由 MM(GG)中将第中将第中将第中将第 2 2 行加到第行加到第行加到第行加到第 3 3 行上面得到的。行上面得到的。行上面得到的。行上面得到的。e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6E E7 7e e8 8e e9 9v v1 11 11 10 00 00 00 00 00 00 0v v2 2-1-10 01 10 00 00 01

35、10 00 0v v3 30 00 0-1-11 10 00 00 0-1-11 1v v4 40 0-1-10 00 00 01 1-1-11 10 0v v5 50 00 00 00 01 1-1-10 00 0-1-1v v6 60 00 00 0-1-1-1-10 00 00 00 0v v1 1e e9 9e e4 4e e2 2e e1 1v v2,32,3v v4 4e e5 5v v5 5e e7 7e e6 6v v6 6e e8 8v v2 2v v1 1e e9 9e e4 4e e2 2e e1 1v v3 3v v4 4e e5 5v v5 5e e7 7e e6 6

36、v v6 6e e8 8e e3 3第24页，共26页，编辑于2022年，星期五e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6E E7 7e e8 8e e9 9v v1 11 11 10 00 00 00 00 00 00 0v v2 2-1-10 01 10 00 00 01 10 00 0v v3 30 00 0-1-11 10 00 00 0-1-11 1v v4 40 0-1-10 00 00 01 1-1-11 10 0v v5 50 00 00 00 01 1-1-10 00 0-1-1v v6 60 00 00 0-1-1-1-10 00 00 00

37、0e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6E E7 7e e8 8e e9 9v v1 11 11 10 00 00 00 00 00 00 0V V2,32,3-1-10 00 01 10 00 01 1-1-11 1v v4 40 0-1-10 00 00 01 1-1-11 10 0v v5 50 00 00 00 01 1-1-10 00 0-1-1v v6 60 00 00 0-1-1-1-10 00 00 00 0第25页，共26页，编辑于2022年，星期五 除了图形化的表示方法之外，线性代数除了图形化的表示方法之外，线性代数中的矩阵概念也可以用来刻画图模型，特中的矩阵概念也可以用来刻画图模型，特别是在计算机领域中，更是将矩阵作为图别是在计算机领域中，更是将矩阵作为图的一种有效表示方法。图的矩阵表示包括：的一种有效表示方法。图的矩阵表示包括：邻接矩阵、可达矩阵、完全关联矩阵。图邻接矩阵、可达矩阵、完全关联矩阵。图中的一个基础就是图的中的一个基础就是图的连通性连通性问题，因为问题，因为图结点之间是否有边连通表明了结点所代图结点之间是否有边连通表明了结点所代表的对象之间是否存在关联关系。表的对象之间是否存在关联关系。第26页，共26页，编辑于2022年，星期五