图论的应用李婷婷.doc

图论的应用 摘 要 图论从诞生至今已近300年，但很多问题一直没有很好地解决。随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，图形是一种描述和解决问题直观有效的手段，这里给出图论在现实生活中的一些应用。 关键词：图论；应用；最小生成树；最短行程 引言 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题（如图1）就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图1 哥尼斯堡七桥问题 几个有趣的问题 四色问题 为了能够迅速地区分一个平面地图或球面地图上的各个国家（假设这些国家在地图上都是连通的），需要用若干种颜色对这些国家着色，使得具有公共边界的两个国家涂染不同的颜色.那么，要保证每张地图都能如此着色，最少需要多少种颜色？这个问题是1850年被一名刚毕业的大学生Francis Guthrie首先提出的，直到1976年，四色问题被美国Illinois大学的K.Appel和W.Haken用计算机证明是正确的，这个证明令数学界震惊，它用了1200多小时，作出100亿个独立的逻辑判断.尽管有了这个机器证明，但它仍然是数学上未解决的问题之一 。 Hamilton问题 Hamilton问题是图论中一直悬而未解的一大问题。它起源于1856年，当时英国数学家Hamilton设计了一种名为周游世界的游戏。他在一个实心的正十二面体的十二个顶点上标以世界上著名的二十座城市的名字，要求游戏者沿十二面体的棱从一个城市出发，经过每座城市恰好一次，然后返回到出发点，即“绕行世界”。 正十二面体的顶点与棱的关系可以用平面上的图表示，把正十二面体的顶点与棱分别对应图的顶点与边，就得到正十二面体图（如图2）。 图2 正十二面体 Peterson图 旅行售货员问题 给出城市之间的距离，要求一位推销员从某一城市出发，周游每个城市一次，然后回到出发的城市，并且选的路径最短。 这是一个图论优化问题，最早由美国数学家威特涅于1934年在普林斯顿一次讨论班上提出。1954年几位美国数学家写了第一篇论文，用线性方程的方法解决了49个城市的旅行售货员问题。后来也有不少论文讨论这个问题，在理论和应用上都很有价值。 最小生成树 有一个石油公司计划为它拥有的许多存储站设计一个管道连接系统，它共有九个存储站，如果两个存储站之间可以修管道，我们就用一条边连接起来，用一个数表示修这两站之间的管道所需的费用，这样这个公司所有的存储站和可能修管道的情况完全可以通过下面这个图表示 图3 可能修管道的情况公司设计计划要求：管道网可以把任何两个存储站都连接起来，且装修费用最小从图论的角度来说，图是一个连通图，每一个边都被赋予了一个数，通常我们称之为赋权图．我们的目的是确定出另一个连通图，其顶点集与原图的顶点集一样，仅保留原图中的一部分边，通常我们把这样确定的新图称作原图的生成子图，并且使子图的所有边的权之和最小我们来简单分析一下子图的属性．首先，我们要找的子图必须是连通的，直观地说子图具有的边应尽量地少，即这个子图不能含有任何回路，因为去掉回路中的任何边都不会影响它的连通性质，我们把不包含回路的生成子图称为原图的生成树下面的图都是不含回路的连通图，又称为树 图4 不含回路的连通图（树） 很容易看出树中的顶点有两类，一类是度数为1的顶点，称为悬挂点，另一类是度数大于1的顶点，称为割点．一旦去掉割点及与之相联的边，图就不连通了． 我们很容易得出这样一些结论：一个具有n个顶点的连通图，(1)连通子图是生成树的充要条件为它具有n－1条边．(2)子图是生成树的充要条件为它有n－1条边且无回路． 简述一下(1)和(2)的证明，实际上只需做这样一循环的推理： n－1条边，可以用数学归纳法来证明．n＝2时结论是显然的．假设对有n个顶