运筹学课件第八章 图与网络分析.ppt

运筹学 第八章 图与网络分析 图的基本知识 最短路径问题 网络最大流问题 网络最小费用流问题 二、连通图 1、链：给定一个图G=(V,E)，一个点边的交错序列(vi1, ei1, vi2, ei2,…,vik-1,eik-1,vik)，如果满足eit=[vit,vit+1] (t=1,2,…,k-1)，则称为一条联结vi1和vik的链，称点vi2, vi3,…,vik-1为链的中间点。 2、圈：链(vi1,vi2,…,vik)中，若vi1=vik,，则称之为一个圈。 3、简单链：若链(vi1,vi2,…,vik)中，点vi1,vi2,…,vik都是不同的，则称之为简单链。 4、连通图：图G中，若任何两个点之间，至少有一条链。 三、树 1、定义：一个无圈的连通图称为树。 2、树的性质： 1）图G是树的充分必要条件是任意两个顶点之间恰有一条链。 2）在树中去掉任意一条边则构成一个不连通图，不再是树；在树中不相邻的两点之间添加一条边，恰好形成了一个圈，也就不再是树。 3）树中顶点的个数为P，则其边数必为P-1。 3、支撑树：设图T=(V,E’) 是图G（V，E）的支撑子图，如果图T=(V, E’) 是一个树，则称T是G的一个支撑树。 4、寻找支撑树的方法 1）破圈法：在图中任取一个圈，从圈中去掉任一边，对余下的图重复上述操作，即可得到一个支撑树。 2）避圈法：每一步选取与已选的边构不成圈的边，直到不能继续为止。 5、最小支撑树 1）赋权图：给图G=(V,E) ，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图G为赋权图，wij称为边[vi,vj]上的权。 2）最小支撑树：如果T=(V,E’) 是G的一个支撑树，称E’中所有边的权之和为支撑树T的权，记为w(T)，即 w(T)=Σ wij (vi,vj)∈T 如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树) w(T*)=min w(T) 3）求最小树的方法： 方法一(避圈法) 开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。 方法二(破圈法) 任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。 四、一笔划问题 1、次：图中的点V，以V为端点的边的个数，称为V的次，记为d(V)。 2、定理1：图G=(V,E)中，所有点的次之和是边数的两倍，即设q边数，则Σd(vi)=2q ，其中vi?V 3、奇点：次为奇数的点。否则称为偶点。 4、任一图中，奇点的个数为偶数。 5、一笔划： 可以一笔划：没有或仅有两个奇次点的图形 如没有奇次点：任取一点，它既是起点又是终点。 两个奇次点：分别选为起点和终点。 五、有向图 1、无向图：G（V，E）点集+边集 2、弧：点与点之间有方向的边，叫做弧。 弧集：A={a1,a1,…,am} 3、有向图：由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。 4、环：某一条孤起点=终点，称为环。 5、基础图：给定一个有向图D=(V,A) ，从D中去掉所有弧上的箭头，所得到的无向图。记之为G(D)。 6、链：设(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。 7、路：如果(vi1,ai1,vi2,ai2,…,vik-1,aik-1,vik)是D中的一条链，并且对t=1,2,…,k-1，均有ait=(vit,vit+1)，称之为从vi1到vik的一条路。 8、回路：若路的第一个点和最后一点相同，则称之为回路。 六、图的矩阵表示 1、网络（赋权图）G=（V，E），其边（vi,vj）有权wij, 构造矩阵A=（aij）n×n,其中： wij（vi,vj）∈E 0 其他 称矩阵A为网络G的权矩阵。 2、对于图G=（V，E）， ∣V ∣=n,构造一个矩阵A=（aij）n×n,其中： wij（vi,vj）∈E 0 其他 称矩阵A为网络G的权。 第二节 最短路问题 一、引例： 如下图中V1：油田，V9：原油加工厂 求使从V1到V9总铺路设管道最短方案。 二、最短路算法 1、情况一： wij≥0(E.W.Eijkstra算法) 原理：Bellman最优性定理 方法：图上作业法（标号法） 标号