图与网络模型

图与网络模型第一页，共三十三页，2022年，8月28日§1图与网络的基本概念一、图的三要素

顶点无序的图为无向图。顶点有序的图为有向图。二、链

一个由点和边的交替序列。三、回路(圈)若链的第一个点和最后一个点相同，则该路为回路(圈)。2第二页，共三十三页，2022年，8月28日§1图与网络的基本概念四、连通图

对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。五、子图及生成子图1．子图设无向图G=（V、E），若2．生成子图3第三页，共三十三页，2022年，8月28日§1图与网络的基本概念六、赋权图对一个无向图G的每一条边(Vi,Vj)，相应地有一个数Cij，则称图G为赋权图，Cij称为边(Vi,Vj)上的权。七、网络在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。4第四页，共三十三页，2022年，8月28日§2最小生成树问题一、树的概念１、树一个无圈的连通图称为树。在自然科学和社会科学中有广泛的应用。如组织结构、比赛图等。２、生成树若T是无向图G的生成子图，且T又是树，称T为G的生成树３、最小生成树(MinimumSpannirngTree)

就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。

5第五页，共三十三页，2022年，8月28日§2最小生成树问题二、求解最小生成树的破圈算法算法步骤：1、在给定的赋权的连通无向图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第１步。6第六页，共三十三页，2022年，8月28日§2最小生成树问题三、应用

例、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7

表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短(单位:百米)。v1331728541034v7v6v5v4v2v37第七页，共三十三页，2022年，8月28日§2最小生成树问题

例用破圈算法求图（a）中的一个最小生成树v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)8第八页，共三十三页，2022年，8月28日作业:求下图的最小树V9V1V2V3V6V5V8V7V46758344239165479第九页，共三十三页，2022年，8月28日§3最短路问题一、最短路问题：对一个赋权的有向图D(或无向图)中指定的两个点Vs和Vt找到一条从Vs

到Vt

的路，使得这条路上所有弧(或边)的权数的总和最小，这条路被称之为从Vs到Vt的最短路。在线路安排、管道铺设、设备更新和厂区布局中有广泛的应用。10第十页，共三十三页，2022年，8月28日§3最短路问题例1电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。

V1（甲地）15176244431065v2V7（乙地）v3v4v5v611第十一页，共三十三页，2022年，8月28日§3最短路问题12第十二页，共三十三页，2022年，8月28日三、基本方法有两个方法１、Dijkstra法(1959提出适用：Cij≥0）解决两指定点间的最短路或指定点到任意点的最短路。

Dijkstra，（1930年5月11日~2002年8月6日）荷兰人。计算机科学家。13第十三页，共三十三页，2022年，8月28日§3最短路问题Dijkstra算法：①从起点标号，标号有两个内容（aj,bj），aj表示从起点到该点的最小距离，bj表示此最小距离链的紧前一个顶点的足标。起点的标号为（0、0）。②从已标号的顶点出发，找出与这些已标号的顶点紧邻的所有顶点的距离，并选最小值进行标号。直到所有顶点都标号完为止。14第十四页，共三十三页，2022年，8月28日§3最短路问题例２.求V１至各点的最短路6V４V2V３V５V６V７V１１０10203015829583215第十五页，共三十三页，2022年，8月28日§3最短路问题例３.求V１至各点的最短路V４V2V３V５V６V７V１１０106203015829583216第十六页，共三十三页，2022年，8月28日§3最短路问题

例4：求V１至各点的最短路V2８－55V1V317第十七页，共三十三页，2022年，8月28日§3最短路问题2、逐次逼近法（适用某些Cij<0）解决指定点到任意点的最短路或两指定点间最短路。算法：1．先赋予起点标号（0、0）及与起点邻近点的标号（Cij、1），其它标号为（∞，1）2．检查各顶点标号是否得到最小值，否则，逐个调整。18第十八页，共三十三页，2022年，8月28日

例6.求

V１至各点的最短路§3最短路问题V1V2V4V6V3V53-434-2-25219第十九页，共三十三页，2022年，8月28日§3最短路问题例7.求

V１至各点的最短路V1V2V4V6V3V53-434-6-25220第二十页，共三十三页，2022年，8月28日§3最短路问题

循环，路长单调下降而趋向-∞，无结果。回路上的权值之和为正数或零，可求得结果。回路上的权值之和为负数时，此法失效。

21第二十一页，共三十三页，2022年，8月28日§3最短路问题四、应用举例例７已知某地区的交通网络如下图所示,其中点代表居民小区,边表示公路,问区中心医院应建在哪个小区,可使离医院最远的小区居民就诊时所走的路程最短。22第二十二页，共三十三页，2022年，8月28日V7V130302520V215V61518V4§3最短路问题V5v55v1v3v2v4V^v7602030203025181515V56020V323第二十三页，共三十三页，2022年，8月28日§3最短路问题小区号V1V2V3V4V5V6V7D(VI)V1030506393456093V2300203363153063V3502002050254050V4633320030183363V5936350300486393V6451525184801548V760304033631506324第二十四页，共三十三页，2022年，8月28日§4最大流问题

在交通运输、物资供应中，经常会遇到人流、车流、信息流、物流、现金流，称“网络流理论”。二十世纪中叶以后，Ford和Fulkerson建立了网络流理论。一、最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。

25第二十五页，共三十三页，2022年，8月28日§4最大流问题例1某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？63522241263v1v2v7v4v3v6v526第二十六页，共三十三页，2022年，8月28日§4最大流问题

Ford—Fulkerson算法二、概念及原理1．可行流:满足约束条件式o≤fij≤cij的fij称为一组可行流。可行流总是存在的，如取所有fij=027第二十七页，共三十三页，2022年，8月28日§4最大流问题2．增值链：设fij是一组可行流，如果存在一条从V1到Vn的初等链，在这条链上所有的前向弧fij<cij，在所有的后向弧上所有的fij>0，则称这条链是一条关于可行流fij的可扩充链。在所有前向弧上计算在所有后向弧上计算调整量28第二十八页，共三十三页，2022年，8月28日§4最大流问题新的可行流

在V1→Vn间增加了一个流量，直至找不到可扩充链为止，就得到了最大流。3．原理:在发点和收点之间是否存在增值链。29第二十九页，共三十三页，2022年，8月28日§4最大流问题三、计算（标号法）1．给出第1个可行流令2．寻找增值链，若无，则取得最大流。否则，确定调整量，将调整为一个更大的可行流，直到得到最大流为止。例2．求下图的最大流．1246532315284430第三十页，共三十三页，2022年，8月28日例3.求下图的最大流．１257643325543432152§4最大流问题31第三