实际应用篇-第14章-图论算法及其MATLAB实现.pptx

第14章 图论算法及其MATLAB实现图论是一门应用广泛且内容丰富的学科,随着计算机和数学软件的发展,图论越来越多地被人们应用到实际生活和生产中,也成为解决众多实际问题的重要工具。图论中的概念和定理均与实际问题有关,并起着关键性作用。本章主要介绍图论的基本概念和性质及几个简单算法的MATLAB实现。14.1 图论的起源图论起源于一个实际问题———柯尼斯堡(Konigsberg)七桥问题。柯尼斯堡位于前苏联的加里宁格勒，普雷格尔河横穿此城堡，河中有两个小岛，记为A 和D，并有七座桥连接岛与河岸、岛与岛(图14-1)。当时居民有个有趣的问题:是否存在这样一种走法，要从这四个河岸中的任何一个河岸开始，通过每座桥且恰巧都经过一次，再回到起点。此问题就是著名的柯尼斯堡七桥问题。1736年，瑞典数学家欧拉(LeonhardEuler)解决了柯尼斯堡问题，由此图论诞生。欧拉认为，此问题关键在于河岸与岛所连接的桥的数目，而与河岸和岛的大小、形状以及桥的长度和曲直无关，他用点表示河岸和岛，用连接相应顶点的线表示各座桥，这样就构成一个图G(图14-2)，此问题就等价于图G 中是否存在经过该图的每一条边一次且仅一次的 “闭路”问题。Euler不仅论证了此走法是不存在的，而且还推广了这个问题，从此开始了图论理论的研究。图14-1 柯尼斯堡七桥问题实际图图14-2 柯尼斯堡七桥问题简化图14.2 相关概念14.2.1 图一个(无向)图G 是指一个有序三元组(V(G),E(G),ψG，),其中V(G)为非空的顶点集,，E(G)为不与V(G)相交的边集,而ψG，是关联函数,使得G 的每条边都对应于G 的无序顶点对，uv(未必互异),简记为图G= (V(G),E(G))或G= (V,E)。14.2.2 特殊图类在研究和描述一般图的性质过程中，特殊图类起着很重要的作用。设两个简单图G=(V,E)和 H=(V′,E′)。若V′?V 和E′?E，则称 H 是G 的子图，记为 H?G。若 H 是G 的子图，并且V(H)=V(G)，则称 H 是G 的生成子图。若 H 是G 的子图，其中V(H)=V(G)和E(H)=E(G)至少有一个不成立，就称 H 是G 的真子图。设图G=(V,E)。假设V′是V 的一个非空真子集，则以G-V′表示从G 中删去V′内的所有顶点以及与这些顶点相关联的边所得到的子图。特别地,当V′={v}时，常把G-{v}简记为G-v，并且用G[V′]表示G-(V-V′)，称为G 的由V′导出的子图。14.2.3 有向图有向图D 是指有序三元组(V(D),A(D),ψD)，其中V(D)是非空的顶点集；A(D)是不与V(D)相交的有向边集；而ψD是关联函数，使得D 的每条有向边对应于D 的一个有序顶点对(不必相异)。若a是D 的一条有边，而u和v 是满足ψD(a)=(u,v)的顶点，则称a为从u连接到v 的一条弧(或有向边)，称u是a 的始点，v是a 的终点，在不产生混淆的情况下，可简记有向边a为uv。若有向图没有环，并且任何两条弧都不具有相同方向和相同端点，则称该有向图是严格的。14.2.4 路在图论理论中,路具有特殊的重要性,古往今来,许多学者均对它进行过深入研究。本节主要介绍简单图G=(V,E)中有关路和连通性的简单性质。 定理14.1 若图G 中有一条(u,v)途径,则G 中也存在一条(u,v)路。 证明:事实上,由u出发沿(u,v)途径走,若遇到相同点,则把相同点间的那段途径去掉,然后继续沿(u,v)途径往下走,一直走到终点v为止。按照此做法可知,最终所得的(u,v)途径即为图G 中的一条(u,v)路。证毕。 定理14.2 设G 为简单图,且最小度δ(G)≥k,则G 中存在长为k 的路。 证明:设P 为简单图G 中的一条最长路，其长为l则lk。进一步设P 为v1v2…vlvl+1，由假设dG(v1)≥δ≥lk,得在P 外存在一个顶点v0与v1邻接,这样就得到v0v1v2…vlvl+1是图G 的另外一条路,并且长于P,这与P 的最长性矛盾。 从上述可知，l≥k，这样，取P 的长为k 的一段作为所求。证毕。14.3 图的矩阵表示图G=(V,E)，一方面，由它的顶点与边之间的关联关系唯一确定，也由它的顶点与顶点之间的邻接关系唯一确定；另一方面,图G=(V,E)在计算机中存储的数据结构必须完全等价于图本身的顶点与边之间的结构关系，而图的矩阵表示就能够承担这种重要的“中介”角色。此外，可通过对图的表示矩阵进行讨论来得到图本身的若干性质。14.3.1 邻接矩阵定义14.1 设(无向)图G=(V,E)，其中顶点集V={v1,v2,…,vn}，边集E={e1,e2,…,eε}。用aij表示顶点vi与顶点vj之间的边数，可能取值为0,1,2,称所得矩阵A