图与网络分析课件

图与网络分析

引论哥尼斯堡七桥问题ABDCABCD简捷表示事物之间的本质联系，归纳事物之间的一般规律OR31引论图的用处A、B、C、D、E某公司的五支球队进行循环赛组织机构设置图ABCDE总公司分公司工厂或办事处OR328.1图的基本概念图是由点和线构成的。点的集合V表示，V={vi}不带箭头的连线叫做边(edge)，边的集合记为E={ej}

，一条边可以用两点[vi,vj]表示,ej=[vi,vj].带箭头的连线叫做弧(arc),弧的集合记为A，A={ak},一条弧也是用两点表示，ak=[vi,vj],弧有方向：vi为始点，vj为终点OR33图的基本概念(续)由点和边组成的图叫做无向图，记为G=（V，E）由点和弧组成的图叫做有向图，记为D=（V，A）例1.v1v2v3v4v1v2v3v4v5v6v7e1e2e3e4e5e6e7a1a2a8a4a3a5a6a9a7a10a11无向图：点集、边集有向图：点集、弧集OR34图的基本概念(续)以点u为端点的边的条数，叫做点u的次

次为1的点叫做悬挂点；次为0的点叫做孤立点；次为奇数则称奇点；次为偶数则称偶点。点弧交替序列称为链；闭合的链称为圈首尾相接的链称为路；闭合的路称回路任意两点之间都有边相连，称为连通图OR358.2树无圈的连通图称之为树赋权无向图G=（V，E）的最小基干称为最小支撑树赋权有向图D=（V，A），从始点到终点的权值最小的路称为最短路OR368.3最短路问题例6某交通网络如下图，求v1到v8的最短路线解：用双标号法v1v2v4v3v5v6v7v86312216104310446v1V2(v3,5)V3(v1,3)V4(v1,1)V5(v2,6)V6(v5,10)V7(v5,9)V8(v5,12)6312216104104364V2(v1,6）OR378.4最大流问题引例：如下输水网络，南水北调工程，从vs到vt送水，弧旁数字前者为管道容量，后者为现行流量，如何调整输水最多？vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)OR38最大流问题的相关概念网络：给定了弧的容量C（vi,vj）的有向图D=（V，A，C）叫做一个网络。可行流：各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流截集：分离始点vs和终点vt的弧的集合，叫做截集截量：截集的容量叫做截量增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为增广链OR39求最大流的方法方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。寻找增广链的标号法：先给vs标号（0，+∞）,而后依次审查各条弧（vi,vj）：对前向弧，饱和否？不饱和，给vj点标号（vi，l(vj));对后向弧，可否减少？可，给vj标号（-vi,l(vj)

）,直到给vt标上号，就得到了增广链。OR310解水网最大流问题.vsV2(0,+∞)V1(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(5,3)(2,1)V4V3Vt(vs,4)(-v1,1)(-v2,1)(v3,1)(v2,1)OR311此题最大流图沿增广链进行调整，前向弧增加l(vj)，后向弧减少l(vj)vsV2V1V3V4Vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(0,+∞)(vs,3)OR312习题：p312－8.4，求最大流给出任意可行流找到一条增广链调整可行流注：’＝1，#＝1，$＝2，*=1vsv1v2v3v4v5vt（4,3）’（10,4）$*（3,2）#