西大数学建模赛前培训课件--图

1、图的基本概念与模型图的基本概念与模型树树最短路问题最短路问题网络的最大流网络的最大流近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。例例1、有甲、乙、丙、丁、戊五个球队，、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e

2、2e3e6e7一、图基本概念一、图基本概念强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边上赋有一个权；建立网络模型，求最大值或最小值。142653876 63162 7 433716 图的矩阵描述：图的矩阵描述： 邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1. 邻接矩阵邻接矩阵对于图对于图G=（V，E），），| V |=n， | E |=m，有，有n n阶方阶方矩阵矩阵A=(aij) n n，其中其中 其它其它之间有关联边时之间有关联边时与与当且仅档当且仅档0vv1jiijav5v1v2v3v4v64332256437 0101011010010101111010

3、10001101111010 65432166654321vvvvvvAvvvvvv例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下对于赋权图对于赋权图G=(V,E), 其中边其中边 有权有权 , 构造矩阵构造矩阵B=(bij) n n 其中：其中：),(jivvjiw EvvEvvwbjijijiji),(0),(654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下

4、:第二节第二节 树树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员例例6.3 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科 树：无圈的连通图即为树

5、树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是

6、是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2 例如，图例如，图4-18（a）是一个有四个顶点（）是一个有四个顶点（n=4）的连通图，它共有的连通图，它共有 nn-2=42=16个生成树。个生成树。V1V2V3V4图图4-18（a）破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v

7、2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15 1某一点到另一点的最短路的某一

8、点到另一点的最短路的狄克斯屈拉狄克斯屈拉（ Dijkstra）法）法2所有点对间的最短路所有点对间的最短路第三节 最短路问题就是从给定的网络图中找出一点到各点或任意两点之间就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。 里特城里特城 （Littletown）是一个乡

9、村的小镇。它的）是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以灾发生点的主要因素，所以消防队队长希望事先能消防队队长希望事先能够确定从消防站到每一个农场社区的最短路够确定从消防站到每一个农场社区的最短路。例子：里特城例子：里特城 的消防队问题的消防队问题最短路：最短路：O A B E F T 19 英里英里1、算法的基本思想、算法的基

10、本思想一种标号的迭代过程具体算法是在图上进行的最短路是到的最短路是到则的最短路是到则的最短路经过点到终点若起点nnnnnnnnnnsvvpvvvvvpvvvvvvpvvvvvvv,3333222321113212.有向图的狄克斯屈拉有向图的狄克斯屈拉(Dijkstra)标号算法步骤标号算法步骤点标号：点标号：p(vj) 起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：a(i，j)=p(i)+lij，步骤：步骤：(1)令起点的标号；令起点的标号； p(vs) 0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是vs ,终点是终点是vt ,以以vi为起为起点

11、点vj为终点的弧记为（为终点的弧记为（i，j）,距离为距离为lij (2)找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 Ai=(i，j)，如果这，如果这样的弧不存在或样的弧不存在或vt已标号则计算结束；已标号则计算结束；(3)计算集合计算集合Ai中弧中弧的标号：的标号：a(i，j)= p(i)+lij(4)选一个点标号选一个点标号 返回到第返回到第(2)步。步。)(,),( | ),(min)(kpvAijijiavpkjk处标号在终点610123214675811165图图519【例【例5-1】图】图51中的权中的权cij表示表示vi到到vj的距离（费用、时间），从的距离

12、（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离，如何选择一条路线使距离最短，建立该问题的网络数学模型。最短，建立该问题的网络数学模型。【解】【解】 设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不，不选择弧选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：( , )12( , )( , )57131467min102,3,610( , )ijiji jEijkii jEk iEijZc xxxxxxixxxi jE或1，6101232146758111

13、65图图51961012920p(9,v2)18P（6, V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例【例5-1】用】用Dijkstra算法求图算法求图51 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1, v2, v3, v5, v7，最短路长为，最短路长为L17=29 14P（0,V1）610123214675811165图图51961012920p(9,v2)18P（6, V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)v1 到到v7的

14、最短路为：的最短路为：p17=v1, v2, v3, v5, v7，最短路长为，最短路长为L17=29 14P（0,V1）从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最短路到该点的最短路线及最短距离，因此可以将每个点标号，求出线及最短距离，因此可以将每个点标号，求出vs到任意点的最短到任意点的最短路线，如果某个点路线，如果某个点vj不能标号，说明不能标号，说明vs不可不可达达vj 。二、 所有点对间的最短路Floyd算法 1、 写出图的权矩阵写出图的权矩阵 )()(不存在到的直达路线距离到jijiijijvvvvldnnijdD)(、输入权矩阵（

15、）；、 对n个顶点的图G,该方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(k)按下式选取 dij(k) =mindij(k-1),dik(k-1）+dkj(k-1）其中，i,j=1,2,3,n。但当i=k或j=k时，dij(k)=dij(k-1).。、（）中的元素就是到的最短路长。如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。一、基本概念：一、基本概念：对网络上的每条弧对网络上的每条弧(vi,vj)都给出一个最大的通都给出一个最大的通过能力，称为该弧的过能力，称为该弧的，简记为，简记为cij。容量网络中通常规定。容量网络中通常规定一个一个(也称源点，记为也称源点，记为s)和一个和一个(也称汇点，记为也称汇点，记为t)，网络中其他点称为网络中其他点称为。st48441226792. 网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3. 流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，记为是指加在网络各条弧上的实际流量，记为fij。若若fij=0，称为零流。，称为零流。在网络中满足