数学建模培训班的图论课件(李德英).pptVIP

　 　 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 1 概论 图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 例1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？（最小生成树 ） 例3 指派问题（assignment problem） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？（二部图的匹配） 例4 中国邮递员问题（CPP－chinese postman problem） 一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。 例5 旅行商问题（TSP－traveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。 例6 运输问题（transportation problem） 某种原材料有多个产地，现在需要将原材料从产地运往多个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？ 上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。 § 2．图的定义与记号 (3)每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；我们仅讨论无向图和有向图。 (4)不与任何结点邻接的顶点称为孤立点，全为孤立点组成的图(无向图和有向图均可)称为空图。(5) 在无向图中两顶点间(包括顶点自身)若多于一条边，则称这几条边为重边.在有向图中若同始点和同终点的边多于一条,则称这几条边为重边. 定义2 子图：给定两个无(有)向图 G=（V,E）， G?=（V?,E?）。 (1)若 V??V 和 E??E，则称 G?是G的子图； (2)若 V??V，E??E，且 G??G，则称 G?是 G 的真子图； (3)若 V?=V 和 E??E，则称 G?是 G 的生成子图(支撑子图)。 (4)若子图 G?无孤立点且G?由E?唯一确定，则称G?是由边集E?导出的子图； (5)若对子图 G?=?V?,E??中任二顶点 u,v,(u,v)?E ?(u,v)?E?，则称 G?是由顶点集V?导出的子图(易见:V?导出的子图G?是以V?为其顶点集,所有在G中同时关联于V?中两点的边为其边集). 图的定义与记号 § 3．路径问题与连通问题 定义3 (1) 设 是赋权图G中从u到v的路径，则称