图论的应用李婷婷

《图论的应用李婷婷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图论的应用摘要图论从诞生至今已近300年，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，图形是一种描述和解决问题直观有效的手段，这里给出图论在现实牛活中的一些应用。关键词：图论；应用；最小生成树；最短行程1引言图论屮所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系,就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和

2、方法，可以对该模型求解。哥尼斯堡七桥问题（如图1）就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河屮的两个岛及岛与河岸联结起來问题是要从这四块陆地屮的任何一块开始通过每一座桥正好一次，再冋到起点。当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一

3、笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。CAD2几个有趣的问题1.1四色问题为了能够迅速地区分一个平面地图或球面地图上的各个国家（假设这些国家在地图上都是连通的），需要用若干种颜色对这些国家着色，使得具有公共边界的两个国家涂染不同的颜色.那么，要保证毎张地图都能如此着色，最少需要多少种颜色？这个问题是1850年被一名刚毕业的大学生FrancisGuthrie首先提岀的，直到1976

4、年,四色问题被美国Illinois大学的K.Appel和W.Haken用计算机证明是正确的，这个证明令数学界震惊，它用了1200多小时，作出100亿个独立的逻辑判断.尽管有了这个机器证明，但它仍然是数学上未解决的问题之一。1.2HamiIton问题Hamilton问题是图论中一直悬而未解的一大问题。它起源于1856年，当吋英国数学家Hamilton设计了一种名为周游世界的游戏。他在一个实心的正十二面体的十二个顶点上标以世界上著名的二十座城市的名字，要求游戏者沿十二面体的棱从一个城市出发，经过每座城市恰好一次，

5、然后返回到出发点，即“绕行世界”。正十二面体的顶点与棱的关系可以用平面上的图表示，把正十二面体的顶点与棱分别对应图的顶点与边，就得到正十二面体图（如图2）。1.3旅行售货员问题给出城市之间的距离，要求一位推销员从某一城市出发，周游每个城市一次,然后回到出发的城市，并且选的路径最短。这是一个图论优化问题，最早由美国数学家威特涅于1934年在普林斯顿一次讨论班上提出。1954年几位美国数学家写了第一篇论文，用线性方程的方法解决了49个城市的旅行售货员问题。后来也有不少论文讨论这个问题，在理论和应用上都很有价值。3

6、最小生成树有一个石油公司计划为它拥有的许多存储站设计一个管道连接系统，它共有九个存储站，如果两个存储站之间可以修管道，我们就用一条边连接起来，用一个数表示修这两站之间的管道所需的费用，这样这个公司所有的存储站和可能修管道的情况完全可以通过下面这个图表示。图3可能修管道的情况公司设计计划要求：管道网可以把任何两个存储站都连接起来，且装修费用最小.从图论的角连通图，每一个边通常我们称之为是确定出另一个原图的顶点集一度来说，图3是一个都被赋予了一个数，赋权图.我们的目的连通图，其顶点集与样，仅保留原图屮的一部分边，

7、通常我们把这样确定的新图称作原图的生成子图，并且使子图的所有边的权之和最小。我们来简单分析一下子图的属性.首先，我们要找的子图必须不含回路的连通图c易看出树中的顶点类是度数为1的顶挂点，另一类是度数大于1的顶点，称为割点.一旦去掉割点及与之相联的边，图就不连通了.是连通的，直观地说子图具有的边应尽量地少，即这个子图不能含有任何回路，因为去掉回路中的任何边都不会影响它的连通性质，我们把不包含回路的生成子图称为原图的生成树。下面的图（如图4）都是不含回路的连通图，又称为树。图4（树）很容有两类，一点，称为悬我们很

8、容易得出这样一些结论：一个具有n个顶点的连通图，（1）连通子图是生成树的充要条件为它具有n-l条边.（2）子图是生成树的充要条件为它有n-1条边且无回路.简述一下（1）和（2）的证明，实际上只需做这样一循环的推理:生成树二连通图+n~1条边=>n~1条边+无回路=>连通+无回路即生成树.从一个树即无冋路的连通图推出它具有n-l条边，可以用数学归纳法来证明.n=2时结论是显然的.假设对有n个顶点的树结