您现在的位置:首页 > >

第5章图与网络分析

发布时间:

第5章 图与网络分析 ( Graph Theory and Network Analysis ) 图的基本概念与模型 树 最短路问题 网络的最大流 最小费用流 应用举例 第一节 图的基本概念与模型 *代图论的历史可追溯到18世纪的七桥问题—穿过 K?nigsberg城的七座桥,要求每座桥通过一次且仅通过一次。 这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不 可能存在这样的路线。 K? nigsberg桥对应的图 一、图基本概念 例1、有甲、乙、丙、丁、戊五个球队, 它们之间比赛的情况也可以用图表示出来。 V5 e5 e4 e6 e7 e2 e3 V3 V4 V1 e1 V2 例2 某单位储存八种化学药品,其中某些 药品是不能存放在同一个库房里的。为了反映 这个情况可以用点V1,V2,……V8分别代表这八 种药品,若药品Vi和药品Vj是不能存放在同 一个库房的,则在Vi和Vj之间连一条线。 V2 ? ? V1 ?· V8 ?V3 ? V4 ? V5 ? V6 ? V7 一般地,当用图论研究一个实际问题时, 常以顶点(Vertex)表示要研究的对象,以 它们之间的连线,表示某种关系,这种连线 称为边(Edge),目的是为了解决某个极值 问题。图中的点用v表示,边用e表示。对每 条边可用它所连接的点表示, 记作:e1=[v1,v1]; e2=[v1,v2]; 图的表示方法: G ? {V , E } 运筹学中研究的图具有下列特征: 强调点与点之间的关联关系,不讲究图的比例大 小与形状; 每条边上赋有一个权; 建立网络模型,求最大值或最小值。 下图可以提出很多极值问题 2 1 6 3 3 1 3 1 2 3 7 7 6 4 8 6 4 6 5 6 7 二、关于图的另外一些名称和术语: 端点,关联边,相邻 e1 若有边e可表示为e=[vi,vj],称vi和vj 是边e的端点,反之称边e为点vi或vj 的关联边。若点vi、vj与同一条边关 联,称点vi和vj相邻;若边ei和ej具 有公共的端点,称边ei和ej相邻。 v2 e2 v1 e4 e5 e3 v3 e6 e7 e8 v4 v5 环, 多重边, 简单图 如果边e的两个端点相重,称该边为 环。如右图中边e1为环。如果两个点 之间多于一条,称为多重边,如右图 v2 e2 e1 v1 e4 e5 e3 v3 中的e4和e5,对无环、无多重边的图 称作简单图。 e6 e7 e8 v4 v5 次,奇点,偶点,孤立点 与某一个点vi相关联的边的数目称为 点vi的次(也叫做度),记作d(vi)。 右图中d(v1)=4,d(v3)=5,d(v5)=1。次 为奇数的点称作奇点,次为偶数的 v2 e1 e2 v1 e4 e5 e3 v3 e6 e7 e8 点称作偶点,次为1的点称为悬挂点, 次为0的点称作孤立点。 v4 v5 图的次: 一个图的次等于各点的次之和。 定理1 任何图中,顶点次数之和等于所有边数的2倍。 证明:由于每条边必与两个顶点关联,在计算点的次时,每条边 均被计算了两次,所以顶点次数的总和等于边数的2倍。 定理2 任何图中,次为奇数的顶点必为偶数个。 证明:设V1和V2分别为图G中奇点与偶点的集合。由定理1可得: v?V1 ? d ( v ) ? ? d ( v ) ? ? d ( v ) ? 2m v?V2 v?V v?V1 2m为偶数,且偶点的次之和 ? d (v ) 也为偶数,所以 ? d (v ) 必为偶 v?V2 数,即奇数点的个数必为偶数。 链,圈,连通图 图中某些点和边的交替序列,若其 中各边互不相同,且对任意vi,t-1和 vit均相邻称为链。用μ表示: e2 v2 e1 v1 e4 e5 e6 e3 v3 e8 ? ? {v 0 , e1 , v1 ,?, e k , v k } 起点与终点重合的链称作圈。如 果每一对顶点之间至少存在一条 链,称这样的图为连通图,否则 称图不连通。 e7 v4 v5 子图,部分图(支撑子图) 图G1={V1、E1}和图G2={V2,E2}如果有 V1 ? V2 和E1 ? E 2 称G1是G2的一个子图。 若有 V1=V2,E1 ? E 2 ,则称G1是G2的一 v2 e2 e1 v1 e4 e5 e6 e3 v3 e7 e8 e3 v3 个部分图(支撑子图)。 e4 v2 e5 e6 e8 v3 v1 e2 e4 v2 e6 v4 (G图) v5 e7 e8 v4 (a) v5 v4 (b) v5 网络(赋权图) 赋权图):权可以代表距离、费用、通过能力(容量)等等。 无向网络:端点无序的赋权图称为. 有向网络:端点有序的赋权图称为。 ② 9 ① 20 ③ 10 19 7 15 ④ 14 6 ⑤ ⑥ 25 图的矩阵描述: 邻接矩阵、关联矩阵、权矩阵等。 1. 邻接矩阵 对于图G=(V,E),| V |=n, | E |=m,有n?n阶方矩阵 A=(aij) n?n,其中 v i 与v j之 间 有 关 联 边 时 ?1 当 且 仅 档 a ij ? ? ?0 其 它 图的基本概念与模型 例6.2 下图所表示的图可以构造邻接矩阵A如下 v1 3 v6 3 6 3 4 7 v2 2 v3 5 v1 v2 v3 v4 v5 v6 v1 ?0 v 2 ?1 ? v3 ?0 ? ? v 4 ?1 v5 ?1 ? v6 ? ?1 1 0 1 1 1? 0 1 1 0 0? ? 1 0 1 0 1? ? 1 1 0 1 0? 0 0 1 0 1? ? 0 1 0 1 0? ? 4 2 v5 v4 A6?6 2. 权矩阵 对于赋权图G=(V,E), 其中边 (vi , v j )有权 w i j ,


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报