数学建模-图论教学幻灯片讲义.ppt

数学建模——图论;一、涉及图论的历年数学建模题目 二、图论简介 三、图论的基本概念 四、最短路问题及其算法 五、最小生成树及其算法 六、几个可以用图论解决的范例;;一、涉及图论的历年数学建模题目;一、涉及图论的历年数学建模题目;二、图论简介;图论是运筹学的一个经典和重要的分支，它起源于18世纪欧拉（Euler）对七桥问题的抽象和论证。 1936年，匈牙利数学家柯尼希（K?nig）出版了图论的第一部专著《有限图与无限图理论》，竖立了图论发展的第一座里程碑。;几个著名的图论问题：;D;2.2 Hamilton 周游世界问题 1859年 Hamilton 提出这样一个问题：一个正十二面体有20个顶点，它们代表世界上20个重要城市。正十二面体的每个面均为五边形，若两个顶点之间有边相连，则表示相应的城市之间有航线相通。 Hamilton 提出 “能否从某城市出发经过每个城市一次且仅一次然后返回出发点？”;其它相关问题;2.6旅行商问题（TSP－traveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。 2.7 指派问题（assignment problem） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？;2.8 运输问题（transportation problem） 某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低?;三、图论的基本概念;3.1 图(Graph)的定义;?G是从 E(G) 到V(G)?V(G) 的一个映射，它指定 E(G) 中的每条边与 V(G) 中的点组成的无序点对相对应。 若用小圆点表示点集 V(G) 中的点，连线表示边集 E(G) 中的边，则可用图形将图表示出来，称之为图的图形。我们常用图的图形代表图本身。; 定义3.2 设e = uv 为图 G 的一条边，我们称 u、v 是 e 的端点，u 与 v 相邻，边 e 与点 u（或v??相关联；称 u 是 e 的起点，v 是 e 的终点。若两条边 e1 与 e2 有共同的端点，则称边 e1与 e2 相邻； 称有相同起点和终点的两条边为重边； 称两端点均相同的边为环； 称不与任何边相关联的点为孤立点。 ;简单图;例3.1 设 V = {v1, v2, v3, v4}，E = {e1, e2, e3, e4, e5}，?：E?V?V 定义为?(e1) = v1v2，?(e2) = v2v3， ?(e3) = v2v3，?(e4) = v3v4，?(e5) = v4v4， 则G = {V, E} 是一个图，其图形如图3.1所示。;例3.2 设 V = {v1, v2, v3, v4}，E = {v1v2, v1v2, v2v3}， 则G = {V, E} 是一个图，其图形如图3.2所示。;例 3.1 和例 3.2 都不是简单图，因为例3.1 中既含重边（e2 与 e3）又含环（e5），而例 3.2 中含重边（v1v2）。下图3.3给出了一个简单图。; 任意两点均相邻的简单图称之为完全图。 n 个点的完全图记为 Kn，图 3.4 中给出的分别是 K2，K3，K4。; 如果图 G 的各条边都被赋予了方向，则称图 G 为有向图。如果图 G 的每条边 e 都附有一个实数 w(e)，则称图 G 为赋权图，实数 w(e) 称为边 e 的权（值）。 图 3.5 和图 3.6 分别给出了有向图和赋权图的例子；而图 3.7 则给出了有向赋权图的例子。;图 3.6：赋权图; 设 v 为图 G 的点，G 中与 v 相关联的边的条数（环计算两次）称为点 v 的度，记为dG(v)，简记为 d(v)。; 定理 3.1（图论第一定理：握手定理） Euler提出 设 G 是具有 n 个顶点 m 条边的图，则顶点度数的总和等于边数的 2 倍，即 证明：因图 G 的任一条边均有两个端点 (可以相同)，在计算度时恰被计算两次 (每个端点各被计算了一次)，所以各点的度数之和恰好为边数的两倍，即定理成立。 推论3.1：图G中度数