运筹学图和网网络模型以及最小费用最大流.ppt

Chapterll图与网络分析 Graph Theory and Network Analysis 本章主要内容: 图与网络的基本概念与模型 最短路问题 最小生成树问题 最大流问题 9最小费用最大流问题  图与网络的基本概念与模型 汉 汉阳 汉口 长 江 您能从武汉理工大学出发走过 每座桥且只走一次然后回到学 武昌 校吗?  图与网络的基本概念与模型 近代图论的历史可追溯到18世纪的七桥问题一穿过 Konigsberg 城的七座桥,要求每座桥通过一次且仅通过一次。这就是著名 的“哥尼斯堡7桥”难题。 Euler1736年证明了不可能存在这样 的路线。 三H 月1 K6 nigsberg桥对应的图  图与网络的基本概念与模型 ·图论中图是由点和边构成,可以反映一些对象之间的关系。 般情况下图中点的相对位置如何、点与点之间联线的长短曲 直,对于反映对象之间的关系并不是重要的 图的定义P230) 若用点表示研究的对象,用边表示这些对象之间的联系,则图 G可以定义为点和边的集合,记作: G=,EN 其中:V——点集E—边集 ※图G区别于几何学中的图。这里只关心图中有多少个点以及哪 些点之间有连线。  图与网络的基本概念与模型 例如:在一个人群中,对相互认识这个关系我们可以用图来 表示。 (v7)陈 (v6)吴 (v2)钱 李 (v2)钱孙(v3)李(v)周(vs) 吴(v6) 可见图论中的图与几何图、工程图是不一样的。  §1图与网络的基本概念 如果我们把上面例子中的“相互认识”关系改为“认识” 的关系,那么只用两点之间的联线就很难刻画他们之间的关 系了,这是我们引入一个带箭头的联线,称为弧。图11-3就 是一个反映这七人“认识”关系的图。相互认识用两条反向 的弧表示。 ()钱 (v1) a14a15 李 (v3)孙 (V7)陈 (s)大 10(V 6吴 周 6 图113  图与网络的基本概念与模型 定义:图中的点用V表示,边用e表示。对每条边可用它所 连接的点表示,记作:e1=[1,1:e2=Ⅳ1V2】 Q端点关联边相邻 若有边可表示为e={vy,称和y 是边e的端点,反之称边e为点v或v 的关联边。若点与同一条边关 联,称点v和y相邻;若边和具 有公共的端点,称边e和e相邻。  图与网络的基本概念与模型 φ环多重边简单图 如果边e的两个端点相重,称该边为 环。如右图中边e1为环。如果两个点 之间多于一条,称为多重边,如右图 中的e4和e5,对无环、无多重边的图 称作简单图。  图与网络的基本概念与模型 链,圈,连通图(P231 图中某些点和边的交替序列,若其 中各边互不相同,且对任意v-1,Vi 和ⅵ+1均相邻称为链。用p表示 u=vo, e, V,,A, ek, Vk 起点与终点重合的链称作圈。如 果每一对顶点之间至少存在一条 链,称这样的图为连通图,否则 称图不连通。  图与网络的基本概念与模型 网络(赋权图)(P232 设图G=(V,E),对G的每一条边(vj)相应赋予数量指标 w,w称为边(ⅵ,v的权赋予权的图G称为网络(或赋权图)。 权可以代表距离、费用、通过能力容量)等等 端点无序的赋权图称为无向网络,端点有序的赋权图称为有 向网络。