第7章+图论-3(图的矩阵表示).ppt

《第7章+图论-3(图的矩阵表示).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、P，使得：A1＝PA2P。其中A1，A2分别是G1，G2的邻接矩阵。如何判断两图同构是图论中一个困难问题v1v2v3v4图G1vavbvcvd图G20111101111011110A1＝12340111101111011110A2＝abcdv1<->vav2<->vbv3<->vcv4<->vd7.3.1邻接矩阵在邻接矩阵A的幂A2，A3，…矩阵中，每个元素有特定的含义。定理:设G是具有n个结点集｛v1，v2，…，vn｝的图，其邻接矩阵为A，则Al（l＝1，2，…）的（i，j）项元素a(l)ij是从vi到vj的长度等于l的路的总数。证明:归纳法当

4、l＝1时，A1＝A，由A的定义，定理显然成立。若l＝k时定理成立，则当l＝k＋1时，Ak+1＝A·Ak，所以aij(1)等于G中联结vi与vj的长度为1的路径条数。naij(l+1)=aik×akj(l)k=1vkvivj长度=1长度=l共akj(l)条7.3.1邻接矩阵结论：(1)如果对l＝1，2，…，n-1，Al的（i，j）项元素（i≠j）都为零，那么vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属于G的不同的连通分支。(2)结点vi到vj（i≠j）间的距离d（vi，vj）是使Al（l＝1，2，…，n-1）的（i，j）

5、项元素不为零的最小整数l。(3)Al的（i，i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。7.3.1邻接矩阵例1图G＝（V，E）的图形如图，求邻接矩阵A和A2，A3，A4，并分析其元素的图论意义。解7.3.1邻接矩阵(1)由A中a(1)12＝1知，v1和v2是邻接的；由A3中a(3)12＝2知，v1到v2长度为3的路有两条，从图中可看出是v1v2v1v2和v1v2v3v2。(2)由A2的主对角线上元素知，每个结点都有长度为２的回路，其中结点v2有两条：v2v1v2和v2v3v2，其余结点只有一条。(3)由于A3的主对角线上元素全

6、为零，所以G中没有长度为３的回路。(4)由于a（１）34＝a（２）34＝a（３）34＝a（４）34＝０，所以结点v3和v4间无路，它们属于不同的连通分支。(5)d（v1，v3）＝２。对其他元素读者自己可以找出它的意义。7.3.1邻接矩阵设图Ｇ＝＜Ｖ，Ｅ＞如下图所示讨论（1）图G的邻接矩阵中的元素为0和1，∴又称为布尔矩阵；（2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行、列和列的交换，则得到相同矩阵。∴若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（3）

7、当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（5）在图的邻接矩阵中，①行中1的个数就是行中相应结点的引出次数②列中1的个数就是列中相应结点的引入次数7.3.1邻接矩阵矩阵的计算：主对角线上的数表示结点i（或j）的引出次数。主对角线上的数表示结点i（或j）的引入次数。7.3.1邻接矩阵表示i和j之间具有长度为2的通路数，表示i和j之间具有长度为3的通路数，表示i和j之间具有长度为4的通路数，7.3.1邻接矩阵bij表示从结点vi到vj有长度分别为1，2，3，4的不同通路总数。此时，b

8、ij0，表示从vi到vj是可达的。7.3.1邻接矩阵2.有向图的邻接矩阵1、设有向图，，的邻接矩阵，，其中指邻接到的边的条数(非负整数