图的基本概念演示文稿

图的基本概念演示文稿目前一页\总数五十页\编于二十一点图的基本概念目前二页\总数五十页\编于二十一点一、涉及图论的历年数学建模题目7、99B钻井布局：最大完全子图8、00B管道订购：最短路9、01B公交车调度10、02D赛程安排11、04A奥运会临时超市网点设计12、07乘公交，看奥运目前三页\总数五十页\编于二十一点一、涉及图论的历年数学建模题目13、08C地面搜索14、08DNBA赛程的分析与评价目前四页\总数五十页\编于二十一点1.问题引入与分析1)98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线”中的前两个问题是这样的：目前五页\总数五十页\编于二十一点1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.目前六页\总数五十页\编于二十一点公路边的数字为该路段的公里数.目前七页\总数五十页\编于二十一点2)问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条再回到点O，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次目前八页\总数五十页\编于二十一点二、图论简介图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。目前九页\总数五十页\编于二十一点例如：在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设，交通网络的合理分布等。目前十页\总数五十页\编于二十一点图论是运筹学的一个经典和重要的分支，它起源于18世纪欧拉（Euler）对七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（König）出版了图论的第一部专著《有限图与无限图理论》，竖立了图论发展的第一座里程碑。目前十一页\总数五十页\编于二十一点几个著名的图论问题：2.1七桥问题（Euler）18世纪东普鲁士有一个城市称为哥尼斯堡，它位于普雷格尔河畔，河中有两个小岛，通过七座桥彼此相联（如图2.1）。当时有人提出：

能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？DABC图2.1目前十二页\总数五十页\编于二十一点DABCABCD建模：点——陆地岛屿边——桥Euler的做法：图2.1图2.2目前十三页\总数五十页\编于二十一点2.2Hamilton周游世界问题1859年Hamilton提出这样一个问题：一个正十二面体有20个顶点，它们代表世界上20个重要城市。正十二面体的每个面均为五边形，若两个顶点之间有边相连，则表示相应的城市之间有航线相通。Hamilton提出“能否从某城市出发经过每个城市一次且仅一次然后返回出发点？”目前十四页\总数五十页\编于二十一点十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？目前十五页\总数五十页\编于二十一点2.3四色问题（猜想）四色问题又称四色猜想、四色定理，是世界近代三大数学难题之一。地图四色定理(Fourcolortheorem)最先是由一位叫古德里（FrancisGuthrie）的英国大学生提出来的。德·摩根（AugustusDeMorgan）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。目前十六页\总数五十页\编于二十一点德·摩尔根致哈密顿的信（1852年10月23日）

我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了。下图是需要四种颜色的例子（图1）。目前十七页\总数五十页\编于二十一点1890年希五德（Heawood）指出“4换为5”猜想成立。1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）在两台百万次的电子计算机上花了1200小时，作了100亿判断，证明了猜想成立。猜想成为定理。目前十八页\总数五十页\编于二十一点2.4中国邮路问题或中国邮递员问题（CPP－ChinesePostmanProblem）1962年中国数学家管梅谷提出：一个邮递员从邮局出发递送邮件，要求对他所负责的辖区的每条街至少走一次，问如何选取路程最短的路线？国际上称之为中国邮递员问题。目前十九页\总数五十页\编于二十一点其它相关问题2.5最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。目前二十页\总数五十页\编于二十一点2.6旅行商问题（TSP－travelingsalesmanproblem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。2.7指派问题（assignmentproblem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？目前二十一页\总数五十页\编于二十一点2.8运输问题（transportationproblem）某种原材料有个产地，现在需要将原材料从产地运往各个使用这些原材料的工厂。假定每个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低?目前二十二页\总数五十页\编于二十一点例1我国北京、上海等十城市间的铁路交通图北京天津济南青岛郑州徐州连云港南京上海..........武汉一、图论的基本概念目前二十三页\总数五十页\编于二十一点例28种化学品，某些药品不能存放在同一个库房里，求库房最少。图示：目前二十四页\总数五十页\编于二十一点例3有5个球队，他们之间的比赛情况，可以用图表示出来。。。。。。目前二十五页\总数五十页\编于二十一点共同特征：用点与点的联线构成图，去反映实际生活中某些对象之间的特定关系。点：代表研究对象；联线：两个对象之间的特定关系；目前二十六页\总数五十页\编于二十一点1)图的概念

定义

一个图G是指一个二元组(V(G),E(G))，其中:其中元素称为图G的顶点.组成的集合，即称为边集,其中元素称为边.

定义图G的阶是指图的顶点数|V(G)|,用来表示；图的边的数目|E(G)|用来表示.也用来表示边是非空有限集，称为顶点集，1)2)

E(G)是顶点集V(G)中的无序或有序的元素偶对表示图，简记用目前二十七页\总数五十页\编于二十一点

定义若一个图的顶点集和边集都是有限集，则称其为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.目前二十八页\总数五十页\编于二十一点一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.目前二十九页\总数五十页\编于二十一点实际生活中，有许多关系具有不对称性，可以用一条带箭头的联线表示。。。。。。例3（非对称关系图）有5个球队，他们之间的比赛情况，可以用图表示出来。目前三十页\总数五十页\编于二十一点

定义若图G中的边均为有序偶对,称G为有向图边为无向边，称e连接和，顶点和称称边为有向边或弧。称为e的尾，称为e的头.若图G中的边均为无序偶对，称G为无向图.为e的端点.既有无向边又有有向边的图称为混合图.目前三十一页\总数五十页\编于二十一点

常用术语1)边和它的两端点称为互相关联.2)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环，4)若一对顶点之间有两条以上的边联结，则这些边称为重边．目前三十二页\总数五十页\编于二十一点下图3.3给出了一个简单图。图3.35)既没有环也没有重边的图，称为简单图．目前三十三页\总数五十页\编于二十一点6）任意两点均相邻的简单图称之为完全图。n个点的完全图记为Kn，图3.4中给出的分别是K2，K3，K4。图3.4目前三十四页\总数五十页\编于二十一点

定理3.2完全图Kn的边数为

m==n(n1)/2。如果简单图G的每个顶点都有相同的度数k，则称G为k次正则图（或k-正则图）。

目前三十五页\总数五十页\编于二十一点注意：完全图是n-1正则图完全图的每个结点都与其它n-1个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。1、完全图：2、正则图：是3正则图。完全图不是完全图目前三十六页\总数五十页\编于二十一点2)赋权图与子图

定义若图的每一条边e都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图.

定义设和是两个图.1)若,称是的一个子图,记2)若，，则称是的生成子图.

目前三十七页\总数五十页\编于二十一点3)若，且，以为顶点集，以两端点均在中的边的全体为边集的图的子图，称4)若，且，以为边集，以的端点集为顶点集的图的子图，称为的由导出的边导出的子图，记为.为的由导出的子图，记为.目前三十八页\总数五十页\编于二十一点图的顶点度定义1)在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).称度为奇数的顶点为奇点，度为偶数的顶点为偶点.2)在有向图中，从顶点v引出的边的数目称为顶点

v的出度，记为d+(v)，从顶点v引入的边的数目称为

v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的

度或次数．目前三十九页\总数五十页\编于二十一点

定理3.1（图论第一定理：握手定理）Euler提出设G是具有n个顶点m条边的图，则顶点度数的总和等于边数的2倍，即

推论3.1：图G中度数为奇的点的个数为偶数。目前四十页\总数五十页\编于二十一点

例3.4请说明：在任意一次集会中和奇数个人握手的人的个数为偶数个。

目前四十一页\总数五十页\编于二十一点给定一个图：一个点、边的交错序列如果满足则称为一条联结和的链记为称为链的中间点。目前四十二页\总数五十页\编于二十一点链中，若,则称之为一个圈链中，点均不同，称之为初等链链中，均不同，称之为初等圈。若链（圈）中含的边均不相同，称之为简单（链）圈或迹目前四十三页\总数五十页\编于二十一点是一条简单链，不是初等链是一条初等链不存在是简单圈，不是初等圈目前四十四页\总数五十页\编于二十一点路和连通（1）若途径W的顶点和边均互不相同，则称W为路或路径.一条起点为,终点为的路称为路记为（2）若在图G中存在(u,v)路，则称顶点u和v在图G中连通.（3）若在图G中顶点u和v是连通的，则顶点u和v之之间的距离d(u,v)是指图G中最短(u,v)路的长；若没没有路连接u和v，则定义为无穷大.目前四十五页\总数五十页\编于二十一点（4）图G中任意两点皆连通的图称为连通图．

（5）对于有向图G，若，且有类似地，可定义有向迹，有向路和有向圈.头和尾，则称W为有向途径.例在右图中：路或路径：圈或回路：目前四十六页\总数五十页\编于二十一点

例一摆渡人欲将