图论作业图论的历史及在通信网中的应用

图论的历史及在通信网中的应用 一、图论的起源及发展： 图论，就是关于图的理论。那这里的“图”又是怎样的图呢?要回答这个问题，首先让我们来了解一下《图论》这门学科的起源。众所周知，任何事物的产生都不是凭空臆想出来的，图论的起源也有其现实背景，那就是著名的Konigsberg七桥问题：在一座名为Konigsberg的小城镇，有一条河流穿。这条河名为Pregel河，它将Konigsberg划分成为几部分，而且它们之间有七座桥相互连接。一天，有一个在城中散步的人想出了一个问题，是否能在穿过城镇的散步中，通过Konigsberg城的七座桥，要求每座桥通过一次且只通过一次。这个问题一直没有人能够回答，直到引起大数学家欧拉的注意，问题才有了完美的解答。 1736年，欧拉(Euler)证明了这件事情是无法办到的，在证明过程中，Euler将原来的Konigsberg城七桥问题经过数学抽象划归成为图的形式，而原来的问题也就变成在图中是否能完成“一笔画”的问题。欧拉关于七桥的那篇论文被公认为图论历史上第一篇论文。此后到十九世纪中叶，这时的图论处于萌芽阶段, 多数问题是围绕着游戏产生的。此为图论发展的第一阶段。 第二阶段从十九世纪中叶到1936年。在这段时期中图论问题大量出现, 如四色问题(1852年)和Hamilton问题(1856年)。同时出现了以图为工具去解决其它领域中一些问题的成果。最有代表性的工作是 Kirchhoff(1847年)和Cayley (1857年)分别用树的概念去研究电网络方程组问题和有机化学的分子结构问题。“图(Graph)”这个词第一次出现是在1878年的英国《自然》杂志中。进入本世纪三十年代, 出现了一大批精彩的新理论和结果,如Menger定理(1927年), Kuratowski定理(1930年)和Ramsey定理(1930年)等等。这些理论和结果为图论作为一个数学分支奠定了基础。1936年, 匈牙利数学家D. Konig写 出了第一篇图论论文到1936年第一本图论专著《有限图与无限图的理论》。至此, 图论作为数学的一个分支已基本形成。从1736年的第 一篇图论论文到1936第一本图论专著, 整整经历了二百年。《图论1736～1936》对这段历史作了详尽的回顾与研究。 1936年以后是第三阶段。由于生产管理、电子电路、交通运输、计算机领域和通讯网络等方面的需要提出一系列问题, 尤其是许多离散性问题的出现大大促进了图论的发展。进入七十年代以后, 特别是大型电子计算机的出现, 使大规模问题的求解成为可能, 图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都得到“爆炸性发展。”图论越来越受到全世界数学界和其它科学界的广泛重视。各种国际学术交流活动十分活跃。大型国际会议频频召开, 国际《图论杂志》也于1977年创刊。目前, 发表图论论文的专业杂志有十几份之多, 其论文数目每年呈指数型上升。图论以及应用的专著已多得无法统计。就其图论本身来讲, 现已发展成《代数图论》、《拓扑图论》、《随机图论》、《计数图论》、《算法图论》、《无限图论》等多个分支多个学术派别的现代数学学科。 二、图的基本概念： 图论中的图指的是一个二元组(V，E)，其中V是图的顶点集，它的元素称为图的顶点，而E是图的边集，它的元素称为图的边，用v(G)表示G的顶点集，用E(G)来表示G的边集。一条边e=(u，v)是说e和两个顶点u，v相关联，称u，v为e的端点，u，v是相邻的。如果e有方向，则称其为有向边，反之称为无向边。每条边都有方向的图称为有向图(digraph)；反之，若对图中任意一条边(u，v)=(v，u)，则称为无向图。对任意两个图G和H，如果，，那么我们称H为G的子图；如果H包含G中所有的点，那么我们称H是G的支撑子图。如果点集，由S导出的子图是指:顶点集为S，且S中任意两点相邻当且仅当它们在G中相邻。 三、图论在通信网络中的应用： 最小生成树问题：在通信网络中，需要找到一条从一个节点到其他节点的最短路径。把此问题抽象后，就变成了图论中的最小生成树问题，即：在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。 最小生成树算法:赋权无向图的最小生成树问题作为一个典型的最小生成树算法问题，迄今为止国内外学者己经对其进行了深入的研究。常见的避圈法有1957年Kruskal提出的Kruskal算法，1957年Prim提出的Prim算法、1959年Dijkstra提出的最小生成树算法。1975年管梅谷教授提出了破圈算法，其基本思想是在给定的图中任意找出一个回路，删去该回路中权最大的边，然后在余下的图中再任意找出一个回路，再删去这个新找出的回路中权最大的边，一直重复上述过程，直到剩余的图中没有回路。此时没有回路的剩余图便是需要求解的最小生成树。2006年孙凌宇和薛锦云教授采用PAR方法通过功能归约变换，形式化推导出递推的最小生成树算法，简化了算法程序设计和正确性证明的过程。2008年张充等人将最小生成树算法用于对预分类文本的聚类处理，较好地解决了中文版面横竖混排的问题。对于赋权有向图最小生成树问题，仅有较少的研究。1997年吴文虎通过树形图中有向圈的收缩和展开，求解赋权有向图的最小生成树。1998年冯俊文基于赋权有向图的 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 表示，给出了一种求解最小生成树的表上作业法。一个最小生成树是具有最小权值的生成树。一个最小生成树可以用贪婪的方法来构建，比如Kruskal算法和Prim算法。在改进的最小生成树算法中，我们使用Prim的算法，因为它是使用添加顶点的策略，这样对于完全连接图来说，Prim的算法更快。 Kruskal算法:假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 （1）将所有顶点涂成红色； （2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； （3）重复（2）直到有n-1条红色边，这n-l条红色边便构成最小生成树T的边集合。注意到在算法执行过程中，红色顶点和红色边会形成一个或多个连通分支，它们都是G的子树。一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树。因此判定一条边是否与红色边形成圈，只需判断这条边的两端点是否属于同一个子树。 上述判断可以如此实现:给每个子树一个不同的编号，对每一个顶点引入一个标记t，表示这个顶点所在的子树编号。当加入一条红色边，就会使该边两端点所在的两个子树连接起来，成为一个子树，从而两个子树中的顶点标记要改变成一样。 （1）Prim算法：假设V是图中顶点的集合，E是图中边的集合，TE为最小生成树中的边的集合，则Prim算法通过以下步骤可以得到最小生成树: （2）初始化: ，TE={ }。此步骤设立一个只有结点的结点集和一个空的边集TE作为最小生成树的初始行态，在随后的算法执行中，这个行态会不断的发生变化，直到得到最小生成树为止。 （3）在所有，的边(u，v) E中，找一条权最小的边，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边，要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和中，其次边的权要最小。找到这条边以后，把这条边放到边集TE中，并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次，每执行一次，集合TE和U都将发生变化，分别增加一条边和一个顶点，因此，TE和U是两个动态的集合，这一点在理解算法时要密切注意。 （4）如果U=V，则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当时，步骤2共执行了n-1次(设n为图中顶点的数目)，TE中也增加了n-1条边，这n-1条边就是需要求出的最小生成树的边。 四、结语： 由于图论在表示二元关系方面的简洁性、直观性以及在实际中的实用性，越来越多的学者对图论的研究表现出浓厚的兴趣，进一步推动了图论理论与应用的蓬勃发展。虽然，现在还存在一些NP-完全问题和NP-困难问题。但随着研究的继续深入，相信会得到解决，并在实际中得到更广泛的应用。