运筹学-图与网络模型以及最小费用最大流讲述.ppt

Chapter11 图与网络分析( Graph Theory and Network Analysis ) 图与网络的基本概念与模型 最短路问题 最小生成树问题 最大流问题 最小费用最大流问题 图与网络的基本概念与模型 长 江 汉 江 武昌 汉口 汉阳 您能从武汉理工大学出发走过每座桥且只走一次然后回到学校吗? 近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。 图与网络的基本概念与模型 K?nigsberg桥对应的图 图与网络的基本概念与模型 图论中图是由点和边构成，可以反映一些对象之间的关系。 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。 图的定义(P230) 若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作： 其中: V——点集 E——边集 ※ 图G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。 图与网络的基本概念与模型 可见图论中的图与几何图、工程图是不一样的。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示。 §1　图与网络的基本概念 6 如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。 图与网络的基本概念与模型 定义: 图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=[v1,v1]; e2=[v1,v2]; 端点,关联边,相邻 若有边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。 图与网络的基本概念与模型 环, 多重边, 简单图 如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。 图与网络的基本概念与模型 链，圈，连通图(P231) 图中某些点和边的交替序列，若其中各边互不相同，且对任意Vi-1,Vi 和vi+1均相邻称为链。用μ表示： 起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。 图与网络的基本概念与模型 网络（赋权图）(P232) 设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。 权可以代表距离、费用、通过能力(容量)等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。 图与网络的基本概念与模型 主要概念(p231-p232) 无向图：由点和边构成的图，记作G=（V，E）。 有向图：由点和弧构成的图，记作D=（V，A）。 连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。 回路：若路的第一个点和最后一个点相同，则该路为回路。 赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。 11 最短路问题 如何用最短的线路将三部电话连起来？ 此问题可抽象为设△ABC为等边三角形，，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。 A B C 最短路问题 A B C P 但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。 最短路问题 问题描述： 要求：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 最短路问题 例 渡河游戏 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要