第7章+图论-3(图的矩阵表示)--离散数学-图论课件.ppt

《第7章+图论-3(图的矩阵表示)--离散数学-图论课件.ppt》由会员分享，可在线阅读，更多相关《第7章+图论-3(图的矩阵表示)--离散数学-图论课件.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1返回 结束第七章 图论引言7.1 图的基本概念7.2 7.3 图的矩阵表示7.4 最短路径问题7.5 图的匹配8.1 Euler图和Hamilton图8.2 树8.3 8.4 2返回 结束7.3 图的矩阵表示v图的矩阵表示 图的数学抽象是三元组，其形象直观的表示即图的图形表示。为便于计算，特别为便于用计算机处理图，下面介绍图的第三种表示方法图的矩阵表示。利用矩阵的运算还可以了解到它的一些有关性质。内容：关联矩阵，邻接矩阵，可达矩阵。重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：有向图的可达矩阵。3返回 结束7.3.1 图的矩阵表示邻接矩阵 存储原则:存储结点集和边集的信息.

2、（1）存储结点集；（2）存储边集：存储每两个结点是否有关系。4返回 结束7.3.1 邻接矩阵1.无向图的邻接矩阵定义 1.6.2设 的顶点集为，用 表示 中顶点 与 之间的边数。称矩阵 为 的邻接矩阵。从图的邻接矩阵的定义容易得出以下性质：(1)是一个对称矩阵；(2)若 为无环图。则 中第 行(列)的元素之和等于顶点 的度数；(3)(3)两个图 与 同构的充要条件是存在一个置换矩阵，使得(4)。对应的邻接矩阵例2下图所示 的邻接矩阵为：A(G)A(G)A(G)A(G)A(G)A(G)相当于将单位矩阵中相应的行与行，或者列与列互换的矩阵5返回 结束6返回 结束7.3.1 邻接矩阵v 在邻接矩阵A

3、的幂A2，A3，矩阵中，每个元素有特定的含义。v 定理:设G是具有n个结点集v1，v2，vn 的图，其邻接矩阵为A，则Al（l1，2，）的（i，j）项元素a(l)ij是从vi到vj的长度等于l的路的总数。证明:归纳法 当l1时，A1A，由A的定义，定理显然成立。若lk时定理成立，则当lk1时，A k+1 A Ak，所以 a aij ij(1)(1)等于 等于G G中 中联结 联结vi vi与 与vj vj的长 的长度为 度为1 1的路径条 的路径条数。数。n a aij ij(l+1)(l+1)=a aik ik a akj kj(l)(l)k=1vkvivj长度=1长度=l共 共a akj

4、kj(l)(l)条 条7返回 结束7.3.1 邻接矩阵v结论：(1)如果对l1，2，n-1，Al的（i，j）项元素（ij）都为零，那么vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属于G的不同的连通分支。(2)结点vi 到vj（ij）间的距离d（vi，vj）是使Al（l1，2，n-1）的（i，j）项元素不为零的最小整数l。(3)Al的（i，i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。8返回 结束7.3.1 邻接矩阵例1 图G（V，E）的图形如图，求邻接矩阵A和A2，A3，A4，并分析其元素的图论意义。解 9返回 结束10返回 结束7.3.1 邻接矩阵设

5、图，如下图所示讨论（1）图G的邻接矩阵中的元素为0和1，又称为布尔矩阵；（2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行、列和列的交换，则得到相同矩阵。若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（5）在图的邻接矩阵中，行中1的个数就是行中相应结点的引出次数 列中1的个数就是列中相应结点的引入次数11返回 结束7.3.1 邻接矩阵v矩阵的计算：主对角线上的数表示结点i（或j）的引出次数

6、。主对角线上的数表示结点i（或j）的引入次数。12返回 结束13返回 结束7.3.1 邻接矩阵bij表示从结点vi到vj有长度分别为1，2，3，4的不同通路总数。此时，bij0，表示从vi到vj是可达的。14返回 结束15返回 结束7.3.1 图的矩阵表示有向图的邻接矩阵16返回 结束7.3.2 邻接矩阵v例1 有向图(下图所示)，求。解：17返回 结束18返回 结束7.3.2 关联矩阵v 例1 下图所示 的关联矩阵为：对应的关联矩阵从图的关联矩阵的定义容易得出以下性质：(1)的每一列元素之和均为2；(2)的每一行元素之和等于对应顶点的度数。(3)若某行元素全为0，则对应的顶点为孤立点。(4)

7、重边所对应的列完全相同。=19返回 结束7.3.2 关联矩阵v有向图的关联矩阵1、设有向图，的关联矩阵，其中20返回 结束7.3.2 关联矩阵v例2 有向图(下图所示)，求。解：A(D)A(D)21返回 结束7.3.3 有向图的可达性矩阵v有向图的可达性矩阵。(了解)设 为有向图，令，可达性矩阵其中元素 可由 求得：22返回 结束7.3.3 有向图的可达性矩阵 根据可达性矩阵，可知图中任意两个结点之间是否至少存在一条路以及是否存在回路。v利用有向图的邻接矩阵A，分以下两步可得到可达性矩阵。(1)令BnAA2An,(2)将矩阵 n中不为零的元素均改为，为零的元素不变，所得的矩阵P就是可达性矩阵。当n很大时，这种求可达性矩阵的方法就很复杂。