图与网络模型的算法及其应用.docVIP

图与网络模型的算法及其应用 摘 要 本文介绍了图论的基本方法和几个基本的网络优化问题的算法，并且介绍了几个基本的网络优化问题的算法在解决实际问题中的应用. 关键字 图与网络 算法 应用 1 前言 在现实生活中，我们会遇到很多复杂的问题，我们希望用一种巧妙的办法去简化它，优化它和解决它，图就是一个有效的工具.把实际问题化为图后，我们能清楚地观察到整个局面，方便我们进行具体分析.所以研究和总结图的应用算法是件有意义且必要的事情. 图论的问题基本上有两大类，一是存在性问题，一是最优化问题.图论是一种较为直接明了的算法，此外图论涵盖的范围很广,内容也很丰富, 单就学术方面而言, 已有很大的发展空间和研究价值.在日常生活中, 我们经常可以找到与图论息息相关的内容, 利用图论我们可以更有效地解决问题. 2 图论基本概念 2.1 图的定义 有序三元组称为一个图, 其中:(1)是有穷非空集, 称为顶点集,其元素叫做图的顶点;(2) 称为边集, 其元素叫做图的边;(3)是从边集到顶点集的有序或者无序对集合的影射, 称为关联函数. 2.2 图的分类 在图中, 与中的有序偶对应的边e称为图的有向边(或弧), 而与中顶点的无序偶对应的边称为图形的无向边, 每一条边都是无向边的图, 叫做无向图, 记为;每一条边都是有向边的图叫做有向图, 记为; 既有无向边又有有向边的图叫做混合图. 2.3 子图 设是一个图，并设和，如果对中任意的一条边，都有和，则称是的一个子图.若，则称为的支撑子图. 2.4 权 如果图中任意一条边上都附有一个数,则称这样的图为赋权图,称为边上的权. 3 最小树问题 最小树是网络优化中一个重要概念，它在交通网、电力网、电话网、管道网等设计中均有广泛的应用. 3.1 定义 定义1 一个连通且无回路的图叫做树. 定义2 给定图和的一个支撑子图，若是一个树，则称为的一个支撑数. 定义3 给定网络，设为的一个支撑数，令 则称为的权.中最小的支撑树称为的最小树. 3.2 求最小树的算法 3.21 求最小树的Kruskal算法 Kruskal算法是1956年首次提出的球最小树的算法，其基本思路是从的条边中选取条权尽量小的边，并且使得不构成回路，从而构成一个最小树.具体算法： 第1步 把图的边按权的大小有小到大的排列起来，即将图的边排序为 ,使得，置. 第2步 若,则停止.这时即为所求；否则转向第3步. 第3步 若不够成回路，则置 转向第2步. 3.22 求最小树的prim算法 设置两个集合和,其中用于存放 的最小生成树中的顶点，集合存放的最小生成树中的边.令集合的初值为 （假设构造最小生成树时，从顶点出发），集合的初值为.prim算法的思想是，从所有的边中，选取具有最小权值的边，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到 时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边. prim算法如下： 第1步 第2步 如果则，，. 3.23 求最小树的Dijkstra算法 Dijkstra算法的基本思路是从图的个独立割集中的每一个都选取一条权最小的边，从而构成一个最小树，具体算法为： 第1步 置 第2步 取，置 第3步 若，则停止；否则，置，返回第2步 3.24 求最小树的管梅谷算法 第1步 令赋权图，在中取一圈，去掉这个圈中全最大的一条边，得一子图; 第2步 在中取一圈，去掉这个圈中全最大的一条边，得一子图； 第3步 在中取一圈，去掉这个圈中全最大的一条边，得一子图； 第4步 如此继续下去，直到剩下的子图不含圈，所得到的子图就是所要求的最小树. 3.3 最小生成树的应用 在现实社会中可以看到，在交通网，通信网，电路网，通风网等建设中，都涉及到如何建造一个网络，使得任意两个地点可达且建造费用最小，也就是求这个网络中最小生成树的问题. 例1 假设要建造连接8个城镇的通信网络，每条线路的造价如图所示，设计一个总造价最小的通信网络. 图1 分析 设计总造价最小的通信网络即找出以上赋权图的最小树. 解 用Kruskal算法求解： 把边按权的递增顺序排列 取则构成的生成树就是一棵最小树（图2），它的权值是16. 图2 用管梅谷算法求解： 在图中取回路，去掉，得一子图； 在中取回路，去掉，得一子图； 在中取回路，去掉，得一子图； 在中取回路，去掉，得一子图； 在中取回路，去掉，得一子图； 在中取回路，去掉，得一子图； 在中取回路，去掉，得一子图； 图3 在中取回路