运筹学-图与网络模型以及最小费用最大流.详解课件.ppt

《运筹学-图与网络模型以及最小费用最大流.详解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter11图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本概念与模型最短路问题最小生成树问题最大流问题最小费用最大流问题本章主要内容：图与网络的基本概念与模型长江汉江武昌汉口汉阳您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗?近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。图与网络的基本概念与模型Königsberg桥对应的图图与

2、网络的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图的定义(P230)若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：其中:V——点集E——边集※图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。图与网络的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周

3、(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。§1图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。

4、6图与网络的基本概念与模型定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。图与网络的基本概念与模型环,多重边,简单图如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为

5、多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5图与网络的基本概念与模型链，圈，连通图(P231)图中某些点和边的交替序列，若其中各边互不相同，且对任意Vi-1,Vi和vi+1均相邻称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。图与网络的基本概念与模型网络（赋权图）(P232)设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij

6、，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256图与网络的基本概念与模型主要概念(p231-p232)无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，

7、相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。11最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC最短路问题ABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O

8、要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题问题描述：要求：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因