第16章图论模型.doc

第七部分 图论方法 第十六章 图论模型 图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等． 这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一， 图论模型属于离散类数学模型，是数学模型中比较容易为学生接受的一类模型，具有直观性、趣味性和简洁性，深得大学生的青睐。另外，图论模型属于较为近代的前沿性数学知识，又具有强烈的，易于为学生接受的数学建模味道，对于培养学生通过建模解决实际问题的能力与学习兴趣都是不可多得的知识内容，因此越来越受到数学家和建模工作者的喜爱．我们所学的这一章只是介绍一些基本概念、原理以及一些典型的应用实例，目的是在今后的学习研究时，可以把图论的基本知识、方法作为工具． 本章先介绍图论的基本概念，然后通过哥尼斯堡七桥问题、最短路径问题、中国邮递员问题、人员分派问题、稳定匹配问题、竞赛图等例子介绍图论的具体应用。 16.1 图的基本概念 图是一个有序对V，E，V是结点集，E是边集，以表示结点数目，表示边的数目，则当(V(和(E(有限时，V,E称为有限图；否则称无限图. 无向边, 与无序结点对(v, u)相关联的边； 有向边，与有序结点对v, u相关联的边； 无向图，每条边都是无向边的图，记作G＝V,E; 有向图，每条边都是有向边的图，记作D＝V,E. 混合图，既有有向边，也有无向边的图. 平凡图，仅有一个结点的图；零图，边集为空集的图V, (，即仅有结点的图. 自回路(环)，关联于同一个结点的边. 无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边. 简单图，不含平行边和自回路的图. 在有向图D＝V,E中，以v((V)为起点的边之条数为出度deg＋(v)；以v((V)为终点的边之条数为入度deg－(v). 在无向图G＝V,E中，与结点v((V)关联的边数，即为结点度数deg(v)或d(v).；在有向图中，结点v的出度和入度之和为度数. 最大度数，((G)＝max{deg(v)(v(V}；最小度数，((G)=min{deg(v)(v(V} 有n个结点的且每对结点都有边相连的无向简单图，称为无向完全图.此时有；有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图. 此时有。 设G＝V,E, V，E的子集V(,E(构成的图G(=V(,E(是图G的子图；若G((G且G((G，(V((V或E((E)，G(是G的真子图. 生成子图，设图G＝V,E, 若E((E, 则图V,E(是图V,E的生成子图，即结点与原图G相同的子图. 16.2 哥尼斯堡世纪城今俄罗斯加里宁格勒的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图所示。城中的居民经常沿河过桥散步提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2所示。于是“七桥问题”就等价于图中所画图形的一笔画问题了。欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须偶数个才能完成一笔画。图的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。哥尼斯堡，令； （2）设已经行遍，按下面方法从中选取： （a）与相关联； （b）除非无别的边可供行遍，否则不应该为中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c）当（b）不能再进行时，算法停止。 此算法称为Fleury算法。 例1 图3是否为欧拉图，并求出一条欧拉回路。 图3 解：图中奇点数量为零，由定理1得，该图为欧拉图。由Fleury算法，AFEDCBAFECFBA就是该图的一条欧拉回路。 16.3最短路径问题 假设要在计算机上建立一个交通咨询系统，则可以采用图的结构来表示实际的交通网络。用顶点表示城市，边表示城市间的交通联系。这个咨询系统可以回答旅客提出的各种问题。如，给定连接若干城市的铁路网，找一条给定两城市间的最短线路，此即所谓最短线路问题。有时，对于旅客来说，可能更关心的