《运筹学_4图与网络分析课件》由会员分享，可在线阅读，更多相关《运筹学_4图与网络分析课件（17页珍藏版）》请在金锄头文库上搜索。
1、5 图与网络分析 5.1 图的基本概念 5.2 树 4.2.1 树与支撑树 4.2.2 最小支撑树问题 5.3 最短路问题 5.4 网络最大流问题,5.1 图的基本概念,图: 由点和点与点之间的连线组成。若点与点之间的连线没有方向，称为边，由此构成的图为无向图。 G=（V，E）,端点 相邻 关联边 环 多重边 简单图 多重图,次：一个点关联的边数称为该点的次。,链：是一个点、边交错序列, 如（ v1,e2,v2,e3,v4). 中间点,圈：链中，若起始点和终了点是同一个点，则称为圈。例如(v1,e2,v2, e3,v4,e4,v3,e1,v1)。,奇点 偶点 悬挂点 悬挂边 孤立点,例,v1,
2、v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,e9,e10,连通图 不连通图 连通分图 支撑子图,若点与点之间的连线有方向，称为弧，由此构成的图为有向图。 D=（V，A）,基础图 始点 终点 路 回路,v1,v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,v7,v8,e9,e10,v1,v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,例,例,树：一个无圈的连通图称为树。树图G=（V,E）的点数记为p，边数记为q，则q=p-1。,例如,支撑树：图T=（V，E）是图G=（V，E）的支撑子图，若图T是一个树，
3、则称T是G的一个支撑树。,5.2 树 5.2.1 树与支撑树,例,图G有支撑树，当且仅当图G是连通的。求连通图的支撑树的方法有“破圈法”和“避圈法”。,v1,v2,v3,v5,e2,e3,e5,e1,e6,e7,e8,破圈法,v1,v2,e1,v3,e2,e4,e4,v4,v4,v5,e6,避圈法,v2,e2,e3,e5,e4,v4,v1,v3,v5,e1,e6,e7,e8,5.2 树 5.2.2 最小支撑树问题,给图G中的每一条边vi，vj一个相应的数ij，则称G为赋权图。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。求赋权图G的最小支撑树的方法也有两种,“破圈发
4、”和“避圈法”。,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,v3,v2,1,v4,2,v5,3,v6,4,v1,5,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。,5.3 最短路问题,对于有向图D(V,A)，给其每一个弧(vi,vj)一 个相应的权值wij，D就成为赋权有向图。给定赋权有向图D中的两个顶点vs和vt，设P是由vs到vt的一
5、条路，把P中所有弧的权之和称为路P的权，记为w(P)。如果路P*的权w(P*)是由vs到vt的所有路的权中的最小者，则称P*是从vs到vt的最短路。最短路P*的权w(P*)称为从vs到vt的距离，记为d(vs,vt)。,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,2,2,3,1,10,6,4,10,2,4,3,2,6,3,-,0,(v1,),(v1,),(v1,),(v1,1),v1,1,(v1,6),(v1,6),(v1,3),(v1,),(v1,),(v4,11),(v1,),(v1,),(v1,),(v1,3),v1,3,(v1,),(v1,),(v1,),(v1,),
6、(v3,5),v3,5,(v4,11),(v4,11),(v1,),(v1,),(v2,6),v2,6,(v1,),(v5,9),v5,9,(v5,10),(v5,12),(v1,),(v5,10),v5,10,(v5,12),(v1,),(v1,),(v5,12),v5,12,(v1,),(v1,),v1,对无向图，与此方法类似。,在所有弧的权都非负的情况下，目前公认最好的求最短路的方法是Dijkstra标号法。用实例介绍如下：,例 求上图中v1到v8的最短路。,v1,v2,v3,v4,v5,v6,v7,v8,v9,6,1,2,2,3,1,10,6,4,10,2,4,3,2,6,3,给一个有
7、向图D(V,A)，指定两个点，一个点称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。,5.4 最大流问题 5.4.1基本概念和定理,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,对于D中的每一个弧(vi,vj)，相应地给一个数cij（cij0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为D(V,A,C)。,所谓网络上的流，是指定义在弧集A上的函数ff(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。,可行流、可行流的流量、最大流。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,
8、2,1,vs,v2,v1,v3,v4,vt,给定容量网络D(V,A,C)，若点集V被剖分为两个非空集合V1和V2，使 vsV1 ，vtV2，则把弧集(V1,V2)称为（分离vs和vt的）截集。,显然，若把某一截集的弧从网络中去掉，则从vs到vt便不存在路。所以，直观上说，截集是从vs到vt的必经之路。,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,截集的容量(简称截量) 最小截集,对于可行流ffij，我们把网络中使fijcij的弧称为饱和弧，使fij0的弧称为非零流弧。,设f是一个可行流，是从vs到vt的一条链，若满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称是
9、（可行流f的）一条增广链。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,若是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。,对最大流问题有下列定理： 定理1 可行流f*fij*是最大流，当且仅当D中不存在关于f*的增广链。 定理2（最大流最小截定理）任一网络中，最大流的流量等于最小截集的截量。,5.4 最大流问题 5.4.2 求最大流的标号法,标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链；经过调整过程沿增广链增加可行流的流量，得新
10、的可行流。重复这一过程，直到可行流无增广链，得到最大流。,标号过程: (1)给vs标号(-,+)，vs成为已标号未检查的点，其余都是未标号点。 (2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)，则vj标号(vi,l(vj)，其中l(vj)minl(vi),cij-fij，vj成为已标号未检查的点；若有非零弧(vj,vi)，则vj标号(-vi,l(vj)，其中l(vj)minl(vi),fji，vj成为已标号未检查的点。vi成为已标号已检查的点。 (3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调
11、整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。 调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)。,下面用实例说明具体的操作方法：例,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,在图中给出的可行流的基础上，求vs到vt的最大流。,(-,+),(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),(3,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),vs,v2,v1,v3,v4,vt,(vs,3),(-,+),得增广链，标号结束，进入调整过程,无增广链，标号结束，得最大流。同时得最小截。,
