10-4-aolm-离散数学.ppt

《10-4-aolm-离散数学.ppt》由会员分享，可在线阅读，更多相关《10-4-aolm-离散数学.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、10.4 10.4 图的矩阵表示图的矩阵表示图的矩阵表示图的矩阵表示 计算机科学领域有许多算法涉及图。计算机存储图的计算机科学领域有许多算法涉及图。计算机存储图的计算机科学领域有许多算法涉及图。计算机存储图的计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论阵表格，一般用大写字母表示。（元素、行、列）。图论阵表格，一般用大写字母表示。（元素、行、列）。

2、图论阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具有效地利用了矩阵，将其作为表达图及其性质的有效工具有效地利用了矩阵，将其作为表达图及其性质的有效工具有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。和手段。和手段。和手段。定义定义定义定义10.18 10.18 设设设设 GG(VV,E E)为简单图，它有为简单图，它有为简单图，它有为简单图，它有 n n 个结点个结点个结点个结点 VV v v1 1,v v2 2,v vn n，则，则，则，则 n n 阶方阵阶方阵阶方阵阶方阵 称为称为称为称为 G G 的邻接矩阵。的邻接矩阵。的邻

3、接矩阵。的邻接矩阵。其中其中其中其中 v v2 2v v4 4v v5 5v v3 3v v1 1v v2 2v v4 4v v5 5v v3 3v v1 1无向图无向图无向图无向图有向图有向图有向图有向图 如果给定的图是零图，则其对应的矩阵中所有的元素都为零，如果给定的图是零图，则其对应的矩阵中所有的元素都为零，如果给定的图是零图，则其对应的矩阵中所有的元素都为零，如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是它是一个零矩阵，反之

4、亦然，即邻接矩阵为零矩阵的图必是零图。零图。零图。零图。v v1 1v v2 2v v4 4v v3 3GG1 1v v2 2v v1 1v v4 4v v3 3GG2 2 用用用用图图图图形形形形表表表表示示示示图图图图的的的的方方方方法法法法，关关关关于于于于结结结结点点点点间间间间的的的的通通通通路路路路很很很很容容容容易易易易在在在在图图图图形形形形中中中中看看看看出出出出来来来来，但但但但在在在在邻邻邻邻接接接接矩矩矩矩阵阵阵阵中中中中就就就就需需需需经经经经过过过过计计计计算算算算。设设设设有有有有向向向向图图图图 G G 的的的的结结结结点集点集点集点集 VV v v1 1,v

5、v2 2,v vn n，它的邻接矩阵为：，它的邻接矩阵为：，它的邻接矩阵为：，它的邻接矩阵为：AA(GG)(a aijij)n nn n，现现现现在在在在我我我我们们们们来来来来计计计计算算算算从从从从结结结结点点点点 v vi i 到到到到结结结结点点点点 v vj j 的的的的长长长长度度度度为为为为 2 2 的的的的路路路路的的的的数数数数目目目目。注注注注意意意意到到到到每每每每条条条条从从从从结结结结点点点点 v vi i 到到到到结结结结点点点点 v vj j 的的的的长长长长度度度度为为为为2 2的的的的路路路路的的的的中中中中间间间间必必必必经经经经过过过过一一一一个个个个结结

6、结结点点点点v vk k，即即即即v vi iv vk kv vj j (1(1k kn n)，如如如如果果果果图图图图中中中中有有有有路路路路 v vi iv vk kv 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

7、vi i 到到到到结点结点结点结点 v vj j 的长度为的长度为的长度为的长度为 2 2 的路的数目等于：的路的数目等于：的路的数目等于：的路的数目等于：按照矩阵的乘法规则，这恰好是矩阵中的第按照矩阵的乘法规则，这恰好是矩阵中的第按照矩阵的乘法规则，这恰好是矩阵中的第按照矩阵的乘法规则，这恰好是矩阵中的第 i i 行，行，行，行，第第第第 j j 列的元素。列的元素。列的元素。列的元素。表示从结点表示从结点表示从结点表示从结点 v vi i 到结点到结点到结点到结点 v vj j 的长度为的长度为的长度为的长度为 2 2 的路的数目。的路的数目。的路的数目。的路的数目。表示从结点表示从结点表

8、示从结点表示从结点 v vi i 到结点到结点到结点到结点 v vi i 的长度为的长度为的长度为的长度为 2 2 的回路的数目。的回路的数目。的回路的数目。的回路的数目。从结点从结点从结点从结点 v vi i 到结点到结点到结点到结点 v vj j 的一条长度为的一条长度为的一条长度为的一条长度为 3 3 的路，可以看的路，可以看的路，可以看的路，可以看作从结点作从结点作从结点作从结点 v vi i 到结点到结点到结点到结点 v vk k 的长度为的长度为的长度为的长度为 1 1 的路，和从结点的路，和从结点的路，和从结点的路，和从结点 v vk k 到结点到结点到结点到结点 v vj j

9、的长度为的长度为的长度为的长度为 2 2 的路，故从结点的路，故从结点的路，故从结点的路，故从结点 v vi i 到结点到结点到结点到结点 v vj j 的的的的一条长度为一条长度为一条长度为一条长度为 3 3 的路的数目：的路的数目：的路的数目：的路的数目：即：即：即：即：一般地有一般地有上述这个结论对无向图也成立。上述这个结论对无向图也成立。上述这个结论对无向图也成立。上述这个结论对无向图也成立。定理定理定理定理10.10 10.10 设设设设 A(G)A(G)为图为图为图为图 G G 的邻接矩阵，则的邻接矩阵，则的邻接矩阵，则的邻接矩阵，则 (A(G)A(G)l l 中的中的中的中的 i

10、 i 行行行行 j j 列元素列元素列元素列元素 等于等于等于等于 G G 中连接结点中连接结点中连接结点中连接结点 v vi i 与与与与 v vj j 的长度为的长度为的长度为的长度为 l l 的路的数目。的路的数目。的路的数目。的路的数目。证明：归纳法证明。证明：归纳法证明。证明：归纳法证明。证明：归纳法证明。(1)(1)当当当当 l l2 2 时，由上得知是显然成立。时，由上得知是显然成立。时，由上得知是显然成立。时，由上得知是显然成立。(2)(2)设命题对设命题对设命题对设命题对 l l 成立，由成立，由成立，由成立，由 故故故故 根据邻接矩阵的定义根据邻接矩阵的定义根据邻接矩阵的定

11、义根据邻接矩阵的定义 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 经过长经过长经过长经过长度为度为度为度为 l l 的路到的路到的路到

12、的路到 v vj j 的，总长度为的，总长度为的，总长度为的，总长度为 l l 1 1 的路的数目。对所的路的数目。对所的路的数目。对所的路的数目。对所有的有的有的有的 k k 求和，即是所有从求和，即是所有从求和，即是所有从求和，即是所有从 v vi i 到到到到 v v 的长度为的长度为的长度为的长度为 l l 1 1 的路的路的路的路的数目，故命题对成立。的数目，故命题对成立。的数目，故命题对成立。的数目，故命题对成立。【例例例例10.610.6】给定一图给定一图给定一图给定一图 GG(V,E)(V,E)如下图所示。如下图所示。如下图所示。如下图所示。v v3 3v v1 1v v2 2

13、v 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 的回路。的回路。的回路。的回路。在许多问题中需要判断有向图的一个结点在许多问题中需要判断有向图的一个

14、结点在许多问题中需要判断有向图的一个结点在许多问题中需要判断有向图的一个结点 v vi i 到另到另到另到另一个结点一个结点一个结点一个结点 v vj j 是否存在路的问题。如果利用图是否存在路的问题。如果利用图是否存在路的问题。如果利用图是否存在路的问题。如果利用图 G G 的邻接的邻接的邻接的邻接矩阵矩阵矩阵矩阵 AA，则可计算，则可计算，则可计算，则可计算 AA，AA2 2，AA3 3，AAn n，当发现，当发现，当发现，当发现其中的某个其中的某个其中的某个其中的某个 AAl l 的的的的 a aijij(l)(l)11，就表明结点，就表明结点，就表明结点，就表明结点 v vi i 到到

15、到到 v vj j 可达。可达。可达。可达。但这种计算比较繁琐，且但这种计算比较繁琐，且但这种计算比较繁琐，且但这种计算比较繁琐，且 AAl l 不知计算到何时为止。从不知计算到何时为止。从不知计算到何时为止。从不知计算到何时为止。从前面得知，如果有向图前面得知，如果有向图前面得知，如果有向图前面得知，如果有向图 G G 有有有有 n n 个结点个结点个结点个结点VVvv1 1,v,v2 2,v vn n v vi i 到到到到 v vj j 有一条路，则必有一条长度不超过有一条路，则必有一条长度不超过有一条路，则必有一条长度不超过有一条路，则必有一条长度不超过 n n 的通的通的通的通路，因

16、此只要考察路，因此只要考察路，因此只要考察路，因此只要考察 a aijij(l(l)就可以了，其中就可以了，其中就可以了，其中就可以了，其中 1ln1ln。对。对。对。对于有向图于有向图于有向图于有向图 G G 中任意两个结点之间的可达性，亦可用可中任意两个结点之间的可达性，亦可用可中任意两个结点之间的可达性，亦可用可中任意两个结点之间的可达性，亦可用可达矩阵。达矩阵。达矩阵。达矩阵。定义定义定义定义10.19 10.19 令令令令 GG 是一个简单有向图，是一个简单有向图，是一个简单有向图，是一个简单有向图，假定假定假定假定 G G 的结点已编序，即的结点已编序，即的结点已编序，即的结点已编

17、序，即 VV v v1 1,v v2 2,v vn n，定义一，定义一，定义一，定义一个个个个 n nn n 矩阵矩阵矩阵矩阵 。其中。其中。其中。其中 称矩阵称矩阵称矩阵称矩阵 P P 是图是图是图是图 G G 的的的的可达性矩阵可达性矩阵可达性矩阵可达性矩阵。可达性矩阵表明了图中任意两个结点间是否至少存在可达性矩阵表明了图中任意两个结点间是否至少存在可达性矩阵表明了图中任意两个结点间是否至少存在可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。一条路以及在任何结点上是否存在回路。一条路以及在任何结点上是否存在回路。一条路以及在任何结点上是否存在回路。一般地可

18、由图一般地可由图一般地可由图一般地可由图 G G 的邻接矩阵的邻接矩阵的邻接矩阵的邻接矩阵 A A 得到可达性矩阵得到可达性矩阵得到可达性矩阵得到可达性矩阵 P P。即令即令即令即令 BBn nAA AA2 2 AAn n，在从，在从，在从，在从 BBn n 中将不为中将不为中将不为中将不为 0 0 的元素改的元素改的元素改的元素改为为为为 1 1，而为零的元素不变，这样改换的矩阵即为可达性矩，而为零的元素不变，这样改换的矩阵即为可达性矩，而为零的元素不变，这样改换的矩阵即为可达性矩，而为零的元素不变，这样改换的矩阵即为可达性矩阵阵阵阵 P P。WarshallWarshall 算法可以由邻接

19、矩阵求可达性矩阵算法可以由邻接矩阵求可达性矩阵算法可以由邻接矩阵求可达性矩阵算法可以由邻接矩阵求可达性矩阵 P P。【例例例例10.710.7】求下图的可达性矩阵。求下图的可达性矩阵。求下图的可达性矩阵。求下图的可达性矩阵。p p2 2p p1 1p p3 3p p5 5p p4 4解：解：解：解：同理可证：同理可证：同理可证：同理可证：由此看出，如果把邻接矩阵看作是结点集由此看出，如果把邻接矩阵看作是结点集由此看出，如果把邻接矩阵看作是结点集由此看出，如果把邻接矩阵看作是结点集 V V 上关系上关系上关系上关系 R R 的的的的关系矩阵，则可达性矩阵关系矩阵，则可达性矩阵关系矩阵，则可达性矩

20、阵关系矩阵，则可达性矩阵 P P 即为即为即为即为 ，因此可达矩阵亦，因此可达矩阵亦，因此可达矩阵亦，因此可达矩阵亦可用可用可用可用 WarshallWarshall 算法计算。算法计算。算法计算。算法计算。可达性矩阵的概念可以推广到无向图中，只要将无向可达性矩阵的概念可以推广到无向图中，只要将无向可达性矩阵的概念可以推广到无向图中，只要将无向可达性矩阵的概念可以推广到无向图中，只要将无向图的每一条边看成是具有相反方向的两条边，这样，一个图的每一条边看成是具有相反方向的两条边，这样，一个图的每一条边看成是具有相反方向的两条边，这样，一个图的每一条边看成是具有相反方向的两条边，这样，一个无向图就

21、可以看成是有向图。无向图的邻接矩阵是一个对无向图就可以看成是有向图。无向图的邻接矩阵是一个对无向图就可以看成是有向图。无向图的邻接矩阵是一个对无向图就可以看成是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连通矩阵。称矩阵，其可达矩阵称为连通矩阵。称矩阵，其可达矩阵称为连通矩阵。称矩阵，其可达矩阵称为连通矩阵。对于一个无向图对于一个无向图对于一个无向图对于一个无向图 GG，除了可用邻接矩阵以外，还对应，除了可用邻接矩阵以外，还对应，除了可用邻接矩阵以外，还对应，除了可用邻接矩阵以外，还对应着一个称为图着一个称为图着一个称为图着一个称为图 G G 的完全关联矩阵，假定图的完全关联矩阵，假

22、定图的完全关联矩阵，假定图的完全关联矩阵，假定图 G G 无自回路，如无自回路，如无自回路，如无自回路，如因某种运算得到自回路，则将它删去。因某种运算得到自回路，则将它删去。因某种运算得到自回路，则将它删去。因某种运算得到自回路，则将它删去。定义定义定义定义10.20 10.20 给定无向图给定无向图给定无向图给定无向图 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)，其中，其中，

23、其中，其中称称称称 MM(GG)为完全关联矩阵。为完全关联矩阵。为完全关联矩阵。为完全关联矩阵。无向图及其完全关联矩阵无向图及其完全关联矩阵无向图及其完全关联矩阵无向图及其完全关联矩阵 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 0VV3 30 00 01 11 1v3v3从关联矩阵中可以看出图形的一些性质：从关联矩阵中可以看出图形的一些性质：从关联矩阵中可以看出图形的一些性质：从关联矩阵中可以看出图形的一些性质：（1 1）图中每一边关联两个结点，故

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

25、相同。）两个平行边其对应的两列相同。（5 5）同一图当结点或边的编序不同，其对应）同一图当结点或边的编序不同，其对应）同一图当结点或边的编序不同，其对应）同一图当结点或边的编序不同，其对应 MM(GG)仅有行序、列序的差别。仅有行序、列序的差别。仅有行序、列序的差别。仅有行序、列序的差别。当一个图是有向图时，亦可用结点和边的关联矩当一个图是有向图时，亦可用结点和边的关联矩当一个图是有向图时，亦可用结点和边的关联矩当一个图是有向图时，亦可用结点和边的关联矩阵来表示。阵来表示。阵来表示。阵来表示。定义定义定义定义10.21 10.21 给定简单有向图给定简单有向图给定简单有向图给定简单有向图 GG

26、 ，V V v v1 1,v v2 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 0

27、0 00 0-1-1-1-1简单有向图及其完全关联矩阵简单有向图及其完全关联矩阵简单有向图及其完全关联矩阵简单有向图及其完全关联矩阵 有向图的完全关联矩阵也有类于无向图的一些性质。有向图的完全关联矩阵也有类于无向图的一些性质。有向图的完全关联矩阵也有类于无向图的一些性质。有向图的完全关联矩阵也有类于无向图的一些性质。定义定义定义定义10.22 10.22 对图对图对图对图 G G 的的的的完全关联矩阵中的两行相加完全关联矩阵中的两行相加完全关联矩阵中的两行相加完全关联矩阵中的两行相加如下：若如下：若如下：若如下：若记记记记 v vi i 对应的行为对应的行为对应的行为对应的行为 ，将第，将第，

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

29、点的结点的结点 v vi i 与结与结与结与结点点点点 v vj j 合并。合并。合并。合并。设图设图设图设图 G G 的结点的结点的结点的结点 v vi i 与结点与结点与结点与结点 v vj j 合并得到图合并得到图合并得到图合并得到图 GG，那，那，那，那么么么么 MM(GG)是将是将是将是将 MM(GG)中的第中的第中的第中的第 i i 行与第行与第行与第行与第 j j 行相加而得行相加而得行相加而得行相加而得到。因为若有关项中第到。因为若有关项中第到。因为若有关项中第到。因为若有关项中第 r r 个对应分量有个对应分量有个对应分量有个对应分量有 ，则说明则说明则说明则说明 v vi

30、i 与与与与 v vj j 两者之中只有一个结点是边两者之中只有一个结点是边两者之中只有一个结点是边两者之中只有一个结点是边 e er r 的端点，的端点，的端点，的端点，且将这两个结点合并后的结点且将这两个结点合并后的结点且将这两个结点合并后的结点且将这两个结点合并后的结点 v vi,ji,j 仍是仍是仍是仍是 e er r 的端点。的端点。的端点。的端点。若若若若 则有两种情况：则有两种情况：则有两种情况：则有两种情况：（1 1）v vi i 与与与与 v vj j 都不是边都不是边都不是边都不是边 e er r 的端点，那么的端点，那么的端点，那么的端点，那么 v vi,ji,j 也不是

31、也不是也不是也不是 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)中若有某些列，其元素全为中若有某些列，其元素全为中若有某些列，其元素全为中若有某些列，其元素全为 0 0，说明，说明，说明，说明 G G

32、中的一些结点合并后，消失了一些对应边。中的一些结点合并后，消失了一些对应边。中的一些结点合并后，消失了一些对应边。中的一些结点合并后，消失了一些对应边。【例例例例10.810.8】无向图无向图无向图无向图 (a)(a)中结点中结点中结点中结点 v v4 4 和和和和 v v5 5 合并得到图合并得到图合并得到图合并得到图(b)(b)。解：其关联矩阵解：其关联矩阵解：其关联矩阵解：其关联矩阵 MM(GG)是由关联矩阵是由关联矩阵是由关联矩阵是由关联矩阵 MM(GG)中将第中将第中将第中将第 4 4 行行行行加到第加到第加到第加到第 5 5 行而得到。行而得到。行而得到。行而得到。e e1 1e

33、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 v2 2v v1 1e e3 3e e4 4e e2 2v v3 3e e5 5V V4,54,5e e7 7e

34、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 0VV4,54,50 01 11 10 01 10 01 1（a a）（b b）【例例例例10.910.9】有向图有向图有向图有向图(a)(a)中合并结点中合并结点中合并结点中合并结点 v v2 2 和和和和 v v3 3。解：合并时，删去自回路得图解：合并时，删去自回路得图解：合并时，删去自回路得图解：合并时，删去自回路得图 (b)(b)。其关

35、联矩阵。其关联矩阵。其关联矩阵。其关联矩阵 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 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 0

36、v 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 6v v6 6e e8 8e e3 3e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6E E7 7e e8 8e e9 9v v1

37、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 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 0VV2,32,3-1-

38、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定理定理定理定理10.11 10.11 如果一个连通图如果一个连通图如果一个连通图如果一个连通图 G G 有有有有 r r 个结点，则其完全关联矩阵个结点，则其完全关联矩阵个结点，则其完全关联矩阵个结点，则其完全关联矩阵 MM(GG)的秩为的秩为的秩为的秩为 r r 1 1，即：，即：，即：，即：rankrankMM(GG)r r 1

39、1证明：这里对无向图进行证明。证明：这里对无向图进行证明。证明：这里对无向图进行证明。证明：这里对无向图进行证明。（1 1）由于矩阵）由于矩阵）由于矩阵）由于矩阵 MM(GG)的每一列恰有两个的每一列恰有两个的每一列恰有两个的每一列恰有两个 1 1，若把，若把，若把，若把 MM(GG)的其它所有行加到最后一行上的其它所有行加到最后一行上的其它所有行加到最后一行上的其它所有行加到最后一行上(模模模模 2 2 加法加法加法加法)，得到矩阵，得到矩阵，得到矩阵，得到矩阵 ，它的最后一行全为它的最后一行全为它的最后一行全为它的最后一行全为 0 0，因为，因为，因为，因为 的秩与的秩与的秩与的秩与 MM

40、(GG)的秩相同，的秩相同，的秩相同，的秩相同，故故故故 MM(GG)的秩小于行数，即的秩小于行数，即的秩小于行数，即的秩小于行数，即 rankrankMM(GG)r r 1 1（2 2）设）设）设）设 MM(GG)的第一列对应边的第一列对应边的第一列对应边的第一列对应边 e e，且，且，且，且 e e 的端点为的端点为的端点为的端点为 v vi i 和和和和 v vj j，调整行序使第，调整行序使第，调整行序使第，调整行序使第 i i 行为第一行，这时行为第一行，这时行为第一行，这时行为第一行，这时 MM(GG)的首列仅在第的首列仅在第的首列仅在第的首列仅在第 1 1 行和第行和第行和第行和

41、第 j j 行为行为行为行为 1 1，其余各元素均为，其余各元素均为，其余各元素均为，其余各元素均为 0 0，再把第一行加到第，再把第一行加到第，再把第一行加到第，再把第一行加到第 j j 行上去则得到矩阵行上去则得到矩阵行上去则得到矩阵行上去则得到矩阵 MM(GG)。其中。其中。其中。其中 MM(GG1 1)是是是是 MM(GG)删去第删去第删去第删去第一行和第一列所得到矩阵。一行和第一列所得到矩阵。一行和第一列所得到矩阵。一行和第一列所得到矩阵。由于由于由于由于 MM(GG1 1)是是是是 GG1 1 的完全关联矩阵，而的完全关联矩阵，而的完全关联矩阵，而的完全关联矩阵，而 GG1 1 是

42、由是由是由是由 G G 的两个结点的两个结点的两个结点的两个结点 v vi i 和和和和 v vj j 合并而得到。由于合并而得到。由于合并而得到。由于合并而得到。由于 G G 是连通的，是连通的，是连通的，是连通的，故故故故 GG1 1 必为连通图，必为连通图，必为连通图，必为连通图，MM(GG1 1)也具有连通图完全关联矩阵也具有连通图完全关联矩阵也具有连通图完全关联矩阵也具有连通图完全关联矩阵的所有性质，故的所有性质，故的所有性质，故的所有性质，故 MM(GG1 1)没有全零的行。没有全零的行。没有全零的行。没有全零的行。如果如果如果如果 MM(GG1 1)的第一列全为零，则可将的第一列

43、全为零，则可将的第一列全为零，则可将的第一列全为零，则可将 MM(GG1 1)的的的的非零列与第一列对调，不影响完全关联矩阵的秩数。非零列与第一列对调，不影响完全关联矩阵的秩数。非零列与第一列对调，不影响完全关联矩阵的秩数。非零列与第一列对调，不影响完全关联矩阵的秩数。因此必可以通过调整行序和把一行加到另一行上这两因此必可以通过调整行序和把一行加到另一行上这两因此必可以通过调整行序和把一行加到另一行上这两因此必可以通过调整行序和把一行加到另一行上这两种运算，使种运算，使种运算，使种运算，使 MM(GG1 1)的第一列首项元素为的第一列首项元素为的第一列首项元素为的第一列首项元素为 1 1，得到

44、，得到，得到，得到 继续上述两种运继续上述两种运继续上述两种运继续上述两种运算，并不改变矩阵的算，并不改变矩阵的算，并不改变矩阵的算，并不改变矩阵的秩，经过秩，经过秩，经过秩，经过 r r 1 1 次，次，次，次，最后将最后将最后将最后将 MM(GG)变换变换变换变换成如下矩阵。成如下矩阵。成如下矩阵。成如下矩阵。显然显然显然显然 MM(r r 1)1)(GG)有一个有一个有一个有一个(r r 1)1)阶子阵，其阶子阵，其阶子阵，其阶子阵，其行列式的值不为行列式的值不为行列式的值不为行列式的值不为 0 0，故故故故MM(r r 1)1)(GG)的秩至的秩至的秩至的秩至少为少为少为少为 r r

45、1 1。由由由由 和和和和 可知可知可知可知 rankrankMM(GG)r r 1 1 10.6 10.6 本章小结本章小结本章小结本章小结 本章首先介绍了图的基本概念，包括：点、边、本章首先介绍了图的基本概念，包括：点、边、本章首先介绍了图的基本概念，包括：点、边、本章首先介绍了图的基本概念，包括：点、边、点点点点,边边边边 序偶等，并根据点与点、边与边、边与点之间序偶等，并根据点与点、边与边、边与点之间序偶等，并根据点与点、边与边、边与点之间序偶等，并根据点与点、边与边、边与点之间的关系定义了邻接点、邻接边、结点的度等概念，在这的关系定义了邻接点、邻接边、结点的度等概念，在这的关系定义了

46、邻接点、邻接边、结点的度等概念，在这的关系定义了邻接点、邻接边、结点的度等概念，在这些概念基础上定义了图同构。在图分类中，依据不同的些概念基础上定义了图同构。在图分类中，依据不同的些概念基础上定义了图同构。在图分类中，依据不同的些概念基础上定义了图同构。在图分类中，依据不同的标准可以将图分为简单图和多重图、有向图和无向图等，标准可以将图分为简单图和多重图、有向图和无向图等，标准可以将图分为简单图和多重图、有向图和无向图等，标准可以将图分为简单图和多重图、有向图和无向图等，学习主要以简单图为主。学习主要以简单图为主。学习主要以简单图为主。学习主要以简单图为主。图中的另一个基础就是图的连通性问题，

47、因为图结图中的另一个基础就是图的连通性问题，因为图结图中的另一个基础就是图的连通性问题，因为图结图中的另一个基础就是图的连通性问题，因为图结点之间是否有边连通表明了结点所代表的对象之间是否点之间是否有边连通表明了结点所代表的对象之间是否点之间是否有边连通表明了结点所代表的对象之间是否点之间是否有边连通表明了结点所代表的对象之间是否存在关联关系。路、迹、回路、圈等表明图中的不同连存在关联关系。路、迹、回路、圈等表明图中的不同连存在关联关系。路、迹、回路、圈等表明图中的不同连存在关联关系。路、迹、回路、圈等表明图中的不同连通状况，割点、割边的概念有助于我们认识图中那些对通状况，割点、割边的概念有助

48、于我们认识图中那些对通状况，割点、割边的概念有助于我们认识图中那些对通状况，割点、割边的概念有助于我们认识图中那些对连通性有特殊影响的结点和边。除了图形化的表示方法连通性有特殊影响的结点和边。除了图形化的表示方法连通性有特殊影响的结点和边。除了图形化的表示方法连通性有特殊影响的结点和边。除了图形化的表示方法之外，线性代数中的矩阵概念也可以用来刻画图模型，之外，线性代数中的矩阵概念也可以用来刻画图模型，之外，线性代数中的矩阵概念也可以用来刻画图模型，之外，线性代数中的矩阵概念也可以用来刻画图模型，特别是在计算机领域中，更是将矩阵作为图的一种有效特别是在计算机领域中，更是将矩阵作为图的一种有效特别是在计算机领域中，更是将矩阵作为图的一种有效特别是在计算机领域中，更是将矩阵作为图的一种有效表示方法。图的矩阵表示包括：邻接矩阵、可达矩阵、表示方法。图的矩阵表示包括：邻接矩阵、可达矩阵、表示方法。图的矩阵表示包括：邻接矩阵、可达矩阵、表示方法。图的矩阵表示包括：邻接矩阵、可达矩阵、完全关联矩阵。完全关联矩阵。完全关联矩阵。完全关联矩阵。对图的这些基本概念读者应该熟练掌握，作为深入对图的这些基本概念读者应该熟练掌握，作为深入对图的这些基本概念读者应该熟练掌握，作为深入对图的这些基本概念读者应该熟练掌握，作为深入学习的基础。学习的基础。学习的基础。学习的基础。