对称矩阵在数据结构图中的应用 毕业论文.doc

存档编号_ _赣南师范学院科技学院学士学位论文对称矩阵在数据结构图中的应用系 别 届 别 专 业 学 号 姓 名 指导老师 完成日期 21目 录内容摘要1关键词1abstract1key words11 引言22 数据结构中图的概念及其邻接矩阵表示法22.1 有向图和无向图的概念22.2 图的邻接矩阵表示法53 图的邻接矩阵关于对称的特征83.1 邻接矩阵的结构特征83.2 有向图邻接矩阵为对称矩阵的前提93.3 邻接矩阵中邻接点的查找103.4 邻接矩阵中关于度的计算114 利用对称的邻接矩阵判断无向图同构115 邻接矩阵在现实问题中的应用146 总结17参考文献18内容摘要：本文研究了图的邻接矩阵及其应用。首先从定义和结构出发，在引入了图的定义及其邻接矩阵存储方式后，分析了无向图的邻接矩阵的对称性，发现无向图的邻接矩阵皆为对称矩阵，而有向图的邻接矩阵只有在满足一定条件下才会对称，探讨了利用无向图的对称邻接矩阵解决其关于同构的问题，在本文最后还利用邻接矩阵对商人过河的问题进行讨论。关键词：对称矩阵 有向图 无向图 邻接矩阵 abstract：this paper studies the adjacency matrix of graphs and its applications. first from defines and structure departure, in introduced has figure of defines and adjacent matrix storage way hou, analysis without to figure of adjacent matrix of symmetric sexual, found no to figure of adjacent matrix are for symmetric matrix, and has to figure of adjacent matrix only in meet must conditions xia only will symmetric, discussion has uses no to figure of symmetric adjacent matrix settlement its on isomorphism of problem, in this last also uses adjacent matrix on businessman river of problem for discussion.key words: symmetric matrix digraph undigraph adjacency matrix 1 引言图是一种重要的数据结构。图的结点之间关系是任意的，图中任意的两个结点之间都可能相关。因此，图有着广泛的用途,在计算机科学，运筹学和控制论中都有着广泛的应用。而图的邻接表示法所产生的矩阵在数学领域内的应用也变得越来越受重视。在本文讨论了传统的图的存储结构中关于邻接矩阵对称的特点。事实上，我们利用邻接矩阵的对称性,不仅可以方便地判定任意两个结点之间是否有弧相连,还可以轻易地找到任意结点的后继邻接点集合、前驱邻接点集合以及某一结点的出度和入度。利用邻接矩阵分析了图的基础结构问题后，更进一步地利用对称的邻接矩阵来判断一般无向图是否同构。到目前为止，对于判断两个无向图是否同构没有一般方法，一般只能用定义判断，有时判断过程也过于繁琐。本文在借鉴了杨世辉的关于完备三分图的同构因子分解中关于特殊图的同构问题和马千里等人的树的一种矩阵判断方法中用邻接矩阵判断树的问题的基础上，讨论一般无向图的同构问题。其方法简洁新颖，而且便于计算机计算。在文中的最后还讨论了邻接矩阵在现实生活中的某些应用。2 数据结构中图的概念及其邻接矩阵表示法2.1 有向图和无向图的概念定义1：在图中的数据元素通常称做顶点，是顶点的有穷非空集合；是两个顶点之间的关系的集合。若，则表示从到的一条弧，且称为弧尾或初始点，称为弧头或终端点，此时的图称为有向图。若必有，即是对称的，则以无序对代替这两个有序对，表示到之间的一条边，此时的图称为无向图。例1 如下图所示 图1 有向图和无向图则中的是有向图，定义此图的谓词则表示从到的一条单向通路。其中: 而中为无向图。其中 定义2：图是由顶点的有限集合（顶点数）与边的集合（顶点之间的关系）构成的，可形成化地定义如下：其中， 其中，数据元素称为顶点；表示在顶点到之间有一条连线，这样一条连线可用顶点的偶对来表示。若是顶点的有序偶对，则称为有向图；否则，若对任意的，必有，并且偶对中顶点的前后顺序不限，则称为无向图。例2 如下图所示 图2 有向图和无向图图2中的为有向图，中的是无向图。其中，的点集和边集分别是：的点集和边集分别为：总结：直观地看，有向图中点的连线是带有箭头（具有方向性）的，如图1中的和图2中的为有向图；而无向图中点的连线是不带箭头（没有方向）的，如图1的和图2中的均为无向图。 2.1.1 顶点的度、入度、出度在无向图中顶点的度定义为以该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为.如图1的中顶点v3的度为3，顶点v5的度为2；图2中顶点1的度为2，顶点2的度为4. 而在有向图中顶点的度有入度和出度之分。入度是该顶点的入边的数目；出度是该顶点的出边的数目，顶点的度等于它的入度和出度之和。如图1中中顶点v1的入度为1，出度为2，度为3；顶点v2的入度为1，出度为0，度为1；图2中的顶点1的入度为0，出度为2，度为2；顶点5的入度为1，出度为2，度为3.2.1.2 权和网在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边的权。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长度；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；对于一个反映工序流程的图，边上的权可表示从前一工序到后一工序所需要的天数。边上带有权的图就称作带权图，也常称作网。例3 下图3中的分别表示了一个无向带权图和一个有向带权图。 无向带权图 有向带权图图3 带权图2.2 图的邻接矩阵表示法图是由点和点与点之间的连线构成的。若图中共有个点，则其中每个点都有可能和其他的点发生关系。即用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（弧）的信息。因此，我们可以定义一个的矩阵，并利用矩阵元素来记录相应的点与点之间的联系。在这个矩阵中的元素非0即1，其含义是：若顶点和之间没有弧，则第行第列的矩阵元素为0，否则为1.对于无向图，也可以用类似的方法来表示。我们将这种记录了顶点之间关系的矩阵称为邻接矩阵，其定义是：若图是一个有个顶点的图，则的邻接矩阵是一个的二维数组，且规定，当时，.如果必要的话，我们还可以在邻接矩阵的基础上再加上一个具有个元素的线性表来记录个顶点的信息，这样就得到了图的邻接矩阵的表示。对于带权图（网），我们也可以用邻接矩阵来表示，只需将邻接矩阵元素的定义加以修改，让其记录相应顶点之间边的权重：规定，当时，.符号在数学上表示无穷大，在计算机中可用一个足够大的数代替，以与边的权重相区别.例4 如下图是有向图.图4 有向图则其邻接矩阵可以表示为：例5 下图为无向图 .图5 无向图则其邻接矩阵可以表示为：例6 下图为带权图.图6 带权图则其邻接矩阵表示为：3 图的邻接矩阵关于对称的特征3.1 邻接矩阵的结构特征在例题1、例题2、例题4和例题6中，我们发现这些有向图的邻接矩阵都不对称，而对于例题5中的无向图我们可以容易看出其邻接矩阵是一个对称矩阵。那接下来我们可以猜想一下：是不是所有无向图的邻接矩阵都为对称矩阵?猜想：所有无向图的邻接矩阵都为对称矩阵。证明：设无向图有个顶点，其各边权重关系为：规定，当时，.特别地，当为无权无向图时，为1.在无向图中，我们知道从顶点到顶点之间边上的权重和从顶点到顶点之间的权重是相等的，即，而且两顶点间存在双向路径，则用邻接矩阵表示，为如下所示：其中 ，根据对称矩阵的定义可知，此邻接矩阵为对称矩阵。接下来我们来举例验证，例如例题1图1的其邻接矩阵，如下容易看出，无向图的邻接矩阵也是一个对称矩阵。图2中无向图的邻接矩阵为：可看出，其也为对称矩阵。3.2 有向图邻接矩阵为对称矩阵的前提从前面的例题，明显可以发现，一般情况下，有向图的邻接矩阵为非对称矩阵，那么在怎样的条件下其邻接矩阵才能对称呢？根据无向图邻接矩阵对称的有关含义，我们发现有向图的邻接矩阵为对称矩阵的前提条件是：在无权的有向图中，若对于每一对，从到和从到都存在直接路径，即为严格强连通图时，其邻接矩阵为对称矩阵。而对带权的有向图而言，其条件更为严格，从到和从到不仅要存在直接路径，而且两条边上所带的权值也需相等时，其邻接矩阵才能成为对称矩阵。例7 下图是具有前提条件的有向图.图7 有向图则此时的邻接矩阵为此时的有向图和结构相似的无向图的邻接矩阵就具有一样的特点。3.3 邻接矩阵中邻接点的查找从邻接矩阵的定义出发，我们可以利用其对称性，方便地判定图中任意两个结点之间是否有弧相连,而且还可以容易找到任意结点的后继邻接点集合、前驱邻接点集合。对于无向图查找其顶点的邻接点时，由于无向图的邻接矩阵一定是一个对称矩阵，所以根据对称性，只需搜索其邻接矩阵中相应的行或列中的非0或非元素即可。 例如，在图5的无向图的邻接矩阵中，顶点1所在行中非0元素为顶点2和顶点3，所以顶点1的邻接点为顶点2和顶点3，从顶点1所在的列查找非0的元素也是顶点2和顶点3，同样的方法，根据邻接矩阵可以看出顶点2的邻接点为顶点1,3,4,5. 而对于有向图，寻找一个顶点的邻接点时，则需搜索其在邻接矩阵中相应的行和列的非0或非元素的个数，其最终的邻接点是两者元素的集合。例如，要寻找图4中有向图的顶点2的邻接点，首先观察其在邻接矩阵中对应的行中非0元素为顶点4和5，对应的列中非0元素为顶点1和3，所以顶点2的邻接点是顶点1,3,4,5.3.4 邻接矩阵中关于度的计算同样地，利用邻接矩阵的对称性，也能方便地求出结点的出度和入度。对于有向图，邻接矩阵的第行非0或非元素的个数即是顶点的出度；第列非0或非元素的个数即是顶点的入度，顶点的度是入度和出度之和。例如，图4中的顶点1在邻接矩阵中所在行的非0个数为2，即出度为2，所在列的非0个数为0，即入度为0，故其度为2.而对于无向图，由于邻接矩阵是对称的，故第行非0或非元素的个数即是顶点的度。例如，图5中的无向图中顶点1在邻接矩阵中所在行的非0个数为2，即其度为2.4 利用对称的邻接矩阵判断无向图同构在利用邻接矩阵分析了图的基础结构问题后，我们进一步来研究一下其关于无向图同构问题的应用。用表示图的邻接矩阵,用表示图的关联矩阵。若第行与第行对换，同时，第列与第列对换，则记.首先要注意到一个事实：交换一个无向图的两个顶点的顺序， 相当于的邻接矩阵交换一次相应的行，也同时交换一次相应的列。 对一个矩阵的行作一次初等变换，同时对的列作相同的初等变换称为对矩阵作合同变换。定义3：设,为两个无向图，若存在双射函数：对于,当且仅当，并且与的重数相同，则称与同构，记作.定理1：两个无向图同构当且仅当其中一个图的邻接矩阵可经一系列合同变换化为另一个图的邻接矩阵，并且图的重数相同。证明：若图，则有双射,使得当且仅当，且与的重数相同 。不妨对两个图重新标记和标号设，即由于每个置换必可写成一系列对换的乘积,所以,的顶点集可经一系列顶点的对换成为的顶点集,由之前所述事实：交换一个无向图的两个顶点的顺序相当于的邻接矩阵交换一次相应的行，也同时交换一次相应的列。从而可经一系列合同变换化为另一个图的邻接矩阵.反之，设与是两个无向图，且可经一系列合同变换化为另一个图的邻接矩阵。设化为的经过一系列合同变换为：，（这里是指的行交换，同时交换对应的列）则这一系列合同变换等价于的顶点经过相应的顶点顺序交换成为，从而可知.推论：若图与同构，它们的邻接矩阵分别是，则在实数域上有（1）与相似（当然特征值也相同）;（2）它们的秩相同且符号差相同。证明：由定理，由初等变换与初等矩阵的关系，可设存在一系列初等矩阵，使得令，而（其中），从而得，故(1)成立。由于无向图的邻接矩阵是对称矩阵，并且合同，故(2)成立。例8 判断下面两个图是否同构。图8 无向图（左）和无向图（右）解:两个图的邻接矩阵为经计算，得的特征值为-2，-2，0，0，1，3,的特征值为-3，0，0，0，0，3，从而两个图不同构。也可以用它们的秩和符号差来判断：，符号差为零。,符号差为零。由推论知，和不同构。例9 判断例8中的无向图与下图的无向图是否同构。图9 无向图解:的邻接矩阵为由此容易看出，经交换1，4行，同时交换1，4列，则得到，从而与同构。需要注意的是推论中的(1)(2)都仅是图同构的必要条件，而非充分，如下图所示：图10 四阶圈图和星型图与的邻接矩阵分别为由于它们的秩均为2，且符号差相等，所以这两个矩阵是合同的，但由于与的边数不同，即维数不一样，所以它们不同构。5 邻接矩阵在现实问题中的应用在讨论了图的同构问题后，接下来将邻接矩阵的应用领域扩充至现实生活中，来解决一个商人过河的问题。问题：三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行。随从们密约，若在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河由商人决定，试给出一个商人安全渡河的方案。分析及求解：假设渡河是从南岸到北岸，表示南岸有个商人，个随从，则全部的允许状态共有10个：以为图的顶点集，其中为初始状态，为最终状态。因为当船行驶奇数次时是从南岸驶向北岸，偶数次时是由北岸驶回南岸，所以我们建立两个邻接矩阵表示从南岸到北岸过河的图的邻接矩阵，=表示从北岸到南岸过河的图的邻接矩阵。其中矩阵中的非0元素表示的是允许的转换状态，例如第一行中第二列和第三列非0，即状态可以转移成或.选择的具体过程如下：只考虑从南岸到北岸的行驶方案，从中的第一行开始，先选择第一种可行状态，即第二列的非0元，发现这样的话，下一步就会回到起始状态，所以我们先从第三列开始，发现可行，将其圈起，继而将其所在列的非0元素划去（若不存在其他非0元素，则直接在下一列继续选择），并在划去的第一个元素所在的行选择可行路径，反复如此，可得2种渡河方案。可行方案：，均为奇数次乘船状态。翻译成渡河方案为：（3,3）（3,1）（3,2）（3,0）（3,1）（1,1）（2,2）（0,2）(0,3) （0,1）（0,2）（0,0）方案：，均为奇数次乘船状态。翻译成渡河方案为：（3,3）（3,1）（3,2）（3,0）（3,1）（1,1）（2,2）（0,2）(0,3) （0,1）（1,1）（0,0）前面两种是从第一行第三列开始决策的，即是先过两个随从后制定两种方案，接下来是从一行第五列开始决策，得到如下两种方案：方案：，均为奇数次乘船状态。翻译成渡河方案为：（3,3）（2,2）（3,2）（3,0）（3,1）（1,1）（2,2）（0,2）(0,3) （0,1）（0,2）（0,0）方案：，均为奇数次乘船状态。翻译成渡河方案为：（3,3）（2,2）（3,2）（3,0）（3,