(图与网络分析)要点

1、第十章图与网络分析精典习题10.1 证明如下序列不可能是某个简单图的次的序列：(1) 7, 6, 5,4, 3,2(2) 6, 6, 5, 4, 3, 2, 1(3) 6, 5, 5, 4, 3, 2,11.1 2已知9个人匕，叭,-,与中，匕和两个人握过手，匕，匕各和四个人握过手， 匕#5#6,匕各和五个人握过手，/，方各和六个人握过手，证明这九个人中一定可以找出 三个人互相握过手。10.3 有八种化学药品a、b、c、d、p、r、s、t要放进储藏室保管。出于安全原因，下 列各组药品不能储存在同一室内:a-r、a-c、at、r-p、ps st、b、t-d、b-d、d-c、 r-s、r-b、p-

2、d、s-c. s-d问储存这八种药品至少需要多少间储藏室。10.4 已知有十六个城市及他们之间的道ffff 路联系(见图10-1)»某旅行者从城市a出发，沿途依次经过 j、n、h、k、g、b、x、i、e、p、 11hhhf、c、l、d、0、c、g、n、h、k、0、d、l、p、e、卜卜”仆i、f、b、j、a,最后到达城市由于疏忽，该 旅行者忘了在图上标明各城市的位置，请应用图<) 的基本概念及理论，在图10-1中标明各城市a、pp .图 10-1 的位置。10.5十名研究生参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表 10-1给出了每个研究生应参加考试的课程(打号

3、的)。规定考试应在三天内结束，每天 上下午各安排一门。研究生们提出希望每人每天最多考一门，又课程a必须安排在每一天上 午考，课程f安排在最后一门，课程b只能安排在中午考，试列出一张满足各方面要求的考 试口程表。1表 10-1图 10.4310. 6用破圈法和避圈法找出图10-2的一个支撑树。图 10-210.7 用破圈法和避圈法求图10-3中各图的最小树。（c）（d）图 10-310.8 已知世界6大城市：（pe）、（n）、（pa）、（l）、（t）、（m）。试在由表101所示交 通网络的数据中确定最小树。表 10-2城市petpamnlpex1351776850t13x60706759pa51

4、60x57362m777057x2055n68673620x31l505925534x10.9 有九个城市匕,l,匕，其公路网如图104所示。弧旁数字是该段公路的长度,有一批货物从匕运到%，问走那条路最短?10. 10用标号法求图10-5中vi到各点的最短路。(a)图 10-510. 11用dijksrea方法求图106中vi到各点的最短距离。图 10-710. 13在图108中(1)用dijkstra方法求从vi到各点的最短路;(2)指出对vi来说那些顶点是不可到达的。v22v3v41v8v7图 10-810. 14已知八口海上油井，相互间距离如表10-2所示。已知1号井离海岸最近，位5 浬

5、。问从海岸经1号井铺设油管将各油井连接起来，应如何铺设使输油管线长度为最短（为 便于计算和检修，油管只准在各井位处分叉）。表10-2各油井间距离单位：km234567811. 32. 10.90. 71.82.01. 520.91.81.22.62.91. 132.61. 72.51.91.040. 71.61.50.950.91. 10.860.61.070. 510.15设某公司在六个城市cl,，c6有分公司，从s到6的直达航线票价记在下 面矩阵的（i，j）位置上（8表明无直达航线，需经其他城市中转）。请帮助该公司设计一 张任意两城市的票价最便宜的路线表。050oc402510500152

6、0co25001501020oc4020100102525co20100551025oc2555010. 16在如图10-9所示的网格中,每弧旁的数字是（cij, g（1）确定所有的数集；(2)求最小截集的容量；(3)证明指出的流是最大流。710.17求如图10-10所示的网络的最大流(每弧旁的数字是(cij, g图 10-1010. 18用ford-fulkerson的标号算法求图10»11中所示各容量网络中从vs到vt的最大流，并标出个网络的最小割集。图中各弧旁数字为容量6j,括弧中为流量fij。2(2)(a)图 10-1110. 19某单位招收懂俄、英、口、德、法文的翻译各一人

7、。有5人应聘。己知乙懂俄文,甲、乙、丙、丁懂英文，甲、丙、丁懂口文，乙、戊懂德文，戊懂法文。问最多有几人能得到招聘，有分别被聘任从事那一文种的翻译。10.20求图10-12中从s-t的最小费用最大流，各弧旁数字为（弓，(b)图 10-1210.21图10t3中，a、b为出发点，分别有50和40单位物资往外发运，d、e为收点,分别需要物资30和60单位，c为中转点,各弧旁数字为（4,求满足上述收发量要求最小费用流。10. 22设g=(v,e)是一个简单图，令6 (g)=斓8(v)(称6 (g)为g的最小次)。证明：(1)若3 (g) > 2,则g必有图；(2)若6 (g) > 2,则

8、g必有包含至少6 (g) +1条边的图。10.23设g是一个连通图，不含奇点。证明：g中不含割边。10. 24给一个联通赋权图g,类似于求g的最小支撑树的kruskal方法，给出一个求g 的最大支撑树的方法。10.25下述论断正确与否：可行流f的流量为零，即v(f)=0,当且仅当f是零流。#习题答案及详解10. 1证明（1）由图的性质定理知，任一个图中，奇点的个数为偶数。7, 6, 5, 4, 3, 2中存在 3个奇数，所以不可能是某个图的次的序列，更不是某个简单图的次的序列。【或者】假设7, 6, 5, 4, 3, 2为某个简单图的次的序列，则图中有6个点，作为简 单图点的最大次数为n-l,

9、即最大次数为5,显然与存在点的次数为7矛盾。所以，7, 6, 5, 4, 3, 2又是简单图的次的序列。（2）由定理知，任一个图g=（v, e）中，所有点的次数之和是边数的两倍，即图中点次 的和为偶数。序列6, 6, 5, 4, 3, 2, 1的和为27,所以它不可能是一个图的次的序列, 更不可能是某个简单图的次的序列。【或者】假设6, 6, 5, 4, 3, 2, 1为某个简单图的次的序列，则图中存在7个点，不 妨设为匕，匕，v3,匕，匕，匕，匕，其中匕，匕次为6,表明匕，匕与除自身外的 剩余6个点均相连。即匕，匕，匕，匕，匕的次不少于2,与匕的次为1矛盾。所以，6, 6, 5, 4, 3,

10、 2, 1不是某个简单图的次的序列。（3）假设6, 5, 4, 3, 2, 1为某个简单图的次的序列，则图中存在7个点，不妨设为 匕，匕，匕，匕，丫5，丫6，匕，因为或匕）二6, d（匕）=1,所以匕与其他6个点相连， 而匕仅与匕相连，又因为d（匕）= "（%） = 5,则匕，匕与除匕和自身之外的所有点相连， 则匕必须与匕，匕相连，所以匕与匕，匕，匕相连，与d（匕）=2矛盾，所以6, 6, 5, 4, 3, 2, 1不是某个简单图的次的序列。10.2 解：设9个人匕，匕，匕为9个点，两人握手设为两点之间存在相连边，握手 问题转化为一个简单图，其中，匕，匕，匕次的序列为2, 4, 4,

11、 5, 5, 5, 5, 6, 6。 这9个人中一定可以找到3个互相握过手，转化为在图中一定存在3个点彼此相连。因为，d（匕）= d（匕）= d（%） = d（匕）= 5,匕，匕，v6,匕之间一定存在两点相连。 假如，匕，匕，匕，匕互相均不相连，因为次均为5,所以匕，匕，v6,匕均与剩余的 4个点匕，匕，v3,匕，匕相连，这与 八匕）=2矛盾。不妨设匕，v5, v6,匕，中存在匕，匕之间相连。必可以找到第三点均与匕，匕相连。假设不存在第3点均与匕，匕相连，匕，匕分别与定义不同的4个点相连，即存在8 个不同的点分别与匕或匕相连，加上匕，匕共计10个点，这与图中9个点矛盾。所以在图中，必存在3个点

12、彼此相连。10.3 解:将8种化学药品a,b,c, d, p, r, s, t设定为8个点， 两种药品不能贮存同一室内状态， 设定为两点之间存在一边相连，画 出药品关系图如下:（图10-3 （a） 在图（a）中，两点之间相连的 药品均不能存贮在一起。对于由点 a, b. c, d, p, r, s, t 的完全 图，求图（a）的补图，得图（b）, 在（b）图中，彼此相连的药品均可以 为存贮庄点，因为d（s） = d（o） = 2, 从s, d开始搜索，（s, a, b）彼此 相连，（d, r）相连，（t, c, p）彼 此相连。(b)图 10-3所以至少需要3间贮存室，存效 组合为（s, a,

13、 b）, （t, c, p）, （d, r）o10.4解：依据旅行者的路线统计城市间的相互关系。点（城市）相邻城市（相邻点）次i11相邻点次aj, m2im, e, f3bg, m, f, j4ja, n, b3cf, l o, g4kh, g, o3dl, o2lc, d, p3el, p2mb, l a3fp, c, l b4nj, h, g3gk, m, c, n4od, c, k3hm, k2pe, f, l3由点的次可知，a, d, e, h为2,则 为4个顶点；b, c, f, g的次为4,则为 4个顶点；某系为边点，城市布局图为图 10-4obfgca mieckod11图 10

14、-410.5 解：将课程a, b, c, d, e, f设定为6个点，同时学生选某课程认为存在相邻边。依据学生1-10的选课划分课程关系图10-5 (a),要求学生一天最多考1门，即图(a)中相连的课程不能排在同一天。对于点abcdef的关系图,求图(a)的补图中)。那么，图(b)中相邻的课程可以安排在同一天，可保证学生一天最多考一门，所以(a,e), (f, d), (c, b)分别各为一天，安排如下：大上午下午1ae2cb3df10.6 解：（破圈法）寻找图中的圈，去掉圈中的一边。圈（匕4%（匕言匕）去掉竹 ；圈（v2e4v4e3v5e6v2 ）去掉的；圈（%匕0%）去掉匕3。（2）圈（匕

15、q匕j匕与匕/匕）去掉g；圈（匕线igcozs匕）去掉备， 得到支撑树（c）。(避圈法)(1)从匕点出发，边相邻边增加边和点，保证不构成回路。匕出发，增加 6，七；弓，匕；07，匕。(2)匕相邻边q，增加匕，匕相邻边6o, 62，增加点1%，%。(3).相邻边%,增加%, 为相邻边耳3，%，增加点%，匕0。将匕匕匕。点均包含在图中，且不存在回路，构成一个支撑树(f)o10.7 解：a)(破圈法)在图中寻找圈，去除圈中权值最大的边(v1 , v： , v3)去除(vi ,v3 )边；(v1 , v4 , v7)去除(v4,v7 )边；( , v5, v8)去除(vvs )边；(v6 , vs ,

16、 v9)去除(v7,vg )边，得到图(a2)(v： , v5 , v3)去除(v2,v5 )边；(v3 , v6 , v4)去除(v3,v6)边；(v5 , v6 ,v8)去除(v5,v6 )边，得到图(a3)(v1 , v2, v3 ,v4)去除(vx ,v2)边，(v3 , v4, v6 ,v§, v5)去除(v4 , v6)边，得到图(a4)o15（v1 , v4, v3 ,v5, vs，v7）去掉（v3,v；）边，得到图（a5），图中不再有回路，则为最小树，其权值和为s = 16(a2)（避圈法）图 10-7(1)17从v1出发,r|1v= vj 其余点为a，v 与m 间有

17、边(v, v2), (v1 , v3), (v1 ,v7）, （v1 ， v4）,权值分别为7, 8, 3, 2,权值最短边为（v1 , v4）o则加粗边（v1 , vq,令匕v与v间最短边为（v】，v7）,加粗边（v1，v7）,令匕uvnv。依次按照上述规则操作，直到认=0。则得到最小树为图（33）,其权值和为16。®5)图 10-7 (2)(b),其权值和为s = 12(b)依图(a)中的步骤,得到图b)的最小树图为10-4(c)依图(a)中的步骤，得到图c)的最小树图为10-7 (c),其权值和为$ = 18(d)依图(a)中的步骤，得到图d)的图 10-7 (d)最小树图为1

18、0-7 (d),其权值和为s = 1710.8 解：6城市(pe), (n), (pa), (l), (t), (m)对应6个点，依表中数据得到交通网络图为:按照避圈法，v= pel, v = t, l, pa, m, n),v与v的最短边为(pe, t),加粗(pe, t)边，tdv=>v,即v= pe. t, v= l, pa, m, n,依次推导。逐次加入边(pe, l), (l, pa), (l, n), (n, m),得到最小树图:109解:利用双标号法,求kf匕的最短路线。(i)从匕出发，匕标号为(匕，0), v = k,其余点为(2)v中点匕相邻的未标号的点有匕, &quo

19、t; = mm4_2,4t = min3,4 = 3 = d_2则对匕进行标号匕(匕，3),令vd匕 = v，v/化=己(3) v中点匕，匕与未标号的匕，匕，匕，匕，kp = imn4 +, l12 + d26, 4 + 45,4 + 4 j =min3 + 3,3+3,3+2,0 + 4 = 4 = 4,给匕标号匕(匕，匕)，令vu化=匕归 化=>v(v2,6)（4）依（3 ）中的原理，v与a相邻边累计最小为（匕，匕），v<jv；=>v,v/v；=>v（5）按照上述原则，依次标号顺序为：给匕标号匕（匕，6）, -=%匕,匕，匕；给匕标号匕（匕，6），丫=%匕，匕，匕，

20、匕;给匕标号匕（匕，7）, v=%匕，匕，匕，匕，匕;给匕标号匕（匕，8.5）, v= ve匕，匕，匕，v6,匕,匕:匕己标号，因此，匕匕的最短路线为匕-匕匕匕，最短路长为8.5。10.10 解：（a）（1）从匕出发，令v=匕,其余点为v,给匕标号为（匕，0）。（2）v与丫相邻边有（匕,匕），（匕,匕）,ar = miiifai + 12, al + 16）= inin30 + 0,20+0 = 4, + di6,给匕标号匕（匕，20）,令 丫=匕（3） v与a相邻边有（匕,匕），（匕,匕），（匕,匕）,（匕,匕）11p = minz11 + dl2,4 + 4;，4 + d659li6+d6

21、2=nan（）+30,20+4,20 + 7,20+20）= ll6 + d67,给匕标号匕（匕,），令匕nv。（4）依次标号：匕（匕,27）, 丫5匕=>丫匕（匕，28）, vu/=>v；匕（匕，29）, v。化 nv匕（匕，30）, 丫5匕nv；匕（匕，31）, 丫5匕 0 丫匕（匕，33）,亿nv；九（匕,34）,九（匕,34）, .（%, 44）,至此，全部点都已标注。匕到各点的最短路只需从该点出发，逆向搜索标号就可得到，且该标号中第2组数字 就是匕到该点的最短距离。匕-匕-% , 5 = 30v1f 匕：匕.匕-%, 5 = 31匕.七匕.匕.匕.匕，s = 29匕>

22、; vf. k > v6 > v5 , s = 27v1f v6: v1f 匕，5 = 20v1f v7： x.匕.匕，5 = 24v1f %: %-匕一匕匕，s = 28v1f v9：匕匕-匕-k-匕，5 = 33v1f %。： k匕一匕-%一%ko，5 = 34kf v： k-k-匕-匕-匕，s = 34v1f v12： k-匕一匕匕一匕几，s = 44(1)从匕出发，令v=匕,其余点为给匕标号为(匕，0)(2) v与a相邻边有(k，匕),(.%),累计距离耳=min. + 4?, 4 + 4) = min0+9,0+8=+ 43 = 4s，给匕标号匕(匕，8),令v=knv(

23、3)按照以上规则，依次标号，直至所有的点均标号为止，匕到某点的最短距离为 沿该点标号逆向追溯。标号顺序为:v3(vp 8), v2(v1，9), v4(v2, 10), v(v4, 13), v5(v2, 11), v6(v5, 14)。匕到各点的最短路见图中粗线o10.11 解:vll(v10,19)（1）从匕出发，令v=匕,其余各点集合为。给匕标号为（匕，0）fv的 所有边为（匕,）,（匕,匕）,累计距离最小为4/> = minl + £?,lh + £j = min0 + 2,0 + 8 = 2 = l1 +几，给匕标号为（匕，2）,令vd匕 = 丫 v/k=&

24、gt;v（2） v fv的所有边为（匕,匕），（匕，匕），（匕,匕）,累计距离最小为% = nnnj + 人5, 4 + zm，l = nun2 + 1,2 +6,0 + 8） = 3 = l12 +/,5, 令人化二忆内匕nw（3）按照标号规则，依次给未标号点标号，直到所有点均已标号，或者vfv不存在 有向边为止。标号顺序为:v5 （v2, 8）, v9（v5, 9）, v4（v1, 8）, v4（v1, 8）, v6（v9, 10）, vs（v9, 11），v7（v6, 14）, v3（v4, 15）, vio（vi, 15）, vn（vio，19）。则匕到各点的最短路线按照标号进行逆向追

25、索（结果见图中粗线）。例如，k-乙最短路为，匕一匕一匕匕一匕匕）一> 乙，权值和为19。10.12 jw：求解匕到各点的最短路。（1）从匕出发，匕标号为（匕，0）,令丫=匕,其余各点集合为（2） vfv的有向弧有（乂,匕），（匕,匕）,最小累计权值/尸而口口九,1n+九 = min0+l0 + 2 = l = lu +工2，给匕标号为（匕，1）,令vu匕=>v,即匕=匕，匕（3）v 一比的有向弧有（匕,匕），（匕,匕），（匕,匕）11p =111111£12 + 力3，/12 + 以,/1 +九 = minl + 3+ 4,0+2 = 2 = z12 +九，给匕 标号匕（

26、匕，2）,匕nv。（4） v fv的有向弧有（匕,匕），（匕,匕）,l1p = nnn£12 + f2i,ll4 + f45 = nmil + 3,2 + 3 = 4 = & + /7 = q ,给匕标号匕（匕， 4）, 丫3匕 0 丫。（5） vfd的有向弧有（匕,匕），（匕,匕）,= nmiz13 + 54 + /45 = nmi4 +1,2 + 3） = 5 ,给匕标号匕（匕，4 ）, 丫3匕 0 丫。（6） vfv不存在有向弧，而匕还未标号，表明匕不能到达匕，匕到匕，匕，匕，匕 的最短路按标号逆向追索可得。10.13 解：（1）从匕出发，匕标号为（匕，0）,令旷=匕,

27、其余各点集合为方。（u） vfv的有向弧有（匕，匕），（匕, ）,（匕,匕）zlp = minz11 + /；2,lll + /；5,z114-/；7 = min0+4,04-l,0 + 3） = l = lll + /；5=z15，给匕 标号匕（匕，1）,令匕nv。（ill） vf （的有向弧有（匕,匕），（km）,（匕m）= miikl + £?,l + 67，+ 人6 = nnn0 + 4,0 + 3,1 + 6 = 3 = l,给匕标号匕（匕，3）,令匕=丫。（iv）依据上述规则，依次标号匕（匕，4）, v6 （v., 7）,匕（匕，10）。此时， 丫 = 匕匕mmm

28、77; =化,匕。（v）vfv不存在有向弧，标号终止，采用逆向标号追索，得到匕到各点的最短路 为：k 一吻：匕-l ；v1f v5 ：匕一% ；乂- v7：匕一岭；v1f v6 ：匕一%一匕:v1f山：匕一匕一匕一匕。（2）依据（1）中的标号结果，标号终止时，匕，匕依然没有标号，表明匕出发，不能 到达匕,匕。10.14解：寻求铺油管线最短问题，可转化为含有8个点的赋权完全图的最小树求解问 题。可采用破圈法和避圈法求解。以下采用避圈法求解。（1）从匕出发，令旷=匕,其余各点集合为，从表中划去第一列。（2）寻求vfv的最短边，从表中第一行寻找最小值，&5 =。7最小，令v=knv,从表中划

29、去第5歹ij。（3）寻找vfv的最短边，从表中第一行，第五行寻找最小值，最小值为4«=0.7,令vu匕nv,划去表中第4列，v = 乂，匕,匕。vi ;1 11v：5；11v111v3 ：11 1日 i v- i1 1 1vs； i iv1x：1 11.32.i io.p1 10.7； iu8j.62.0： i i1.31 1v2l3；x0© 1；81.2；2.*v32.1 o.i10.9i x i i12f.6 ii.5 ia.61.4 /1ibv41.82；6x 0.7 i0l9 iv50分 11.2d.7 1p.71i x ；0.91/11q.8 vfi“82.61.

30、5 ia 610；9 1：x 1q.61i-o 1v71 j.o112.3i.91 f；l5 iil:.l 116.8! 0.611反i.5b.5vs1.511.1；l0 ! 0.9'1.0:x（4）寻找v fv的最短边，在表中v中元素各行中寻找最小值得到（即从第1, 4, 5行寻找），d5z = 0.8 ,令匕 =>v,划去表中第8行。（5）按照（4）依次进行操作,直到v=0为止，得到结果如下图:铺设输油管线全线长为:61s=doi+dis+dsi+dse+dss+dsi+ds+dsz = 5+0. 9+0. 7+0. 9+0. 8+0. 5+1. 0+0. 9=10. 7 （

31、哩）10.15 解：，050。=6 4025j050 s 400 15 2015 0 1020 10 0oo 20 1025 s 2525 10）s 2520 oo _10 25 0 5555 0,（喀）构造 qu)= (%,其中 4" = mmd? + d；?j 7=1,6j，035453525jo 03501520302545150102035352010010252530201003510)253525350,曙+蹈嗯+娉4?+吧喈。曙娉+40幡娉+4700娉十%0同理构造。=（4），4y = min4* + 4】） r=l.6得到。=。“），则。卬矩阵为从q到4城市的最便宜原

32、价为4"，其路线为:。4c5。61-5-41-51-62-42-4-52-63-43-53-4-64-54-65-4-610.16 解：（1）所有的截集（割集）（匕，匕），（匕,匕） ：（匕,匕）,（匕，匕） ：（匕，匕），（匕，匕），（%，%）；（匕，匕）,（匕，匕）;（匕,匕）,（匕，匕）匕(21)（2）对应（1）中所有截集的容量为：6, 7, 7, 5, 8,所以最小截集为（匕，匕）,（匕,匕）， （v = 匕,匕,u2, p = 匕,匕）其容量为5。（3）图中指出流的流量为非作歹，由定理最大流等于最小割容量可知当前流是最大流。 也可用标号法证明不存在增广链，而说明当前流是最大

33、流。（1）给匕标号匕（0,+8）（11）检查匕相邻的弧，弧（匕，匕）已达容量，f3=c“ = 2,不满足标号条件中，弧 （匕，匕），/c=3<4 = j，给匕标号，匕（5,/（匕），/（%） = min/（匕）,（-<?）, =min +s, 43 = 1 即匕标号匕:（s,l）（m）检查匕，弧（叱,匕）不满足标号条件中，弧（彩，匕）,/“<&，给匕标号 匕（2,/（匕）,/（匕）=min /（v2）,（c21-/21）= mn 1,3 -1 = 1 即匕标号匕（2,1）。（，）检杳匕，弧（匕，匕），（匕，匕）均不满足标号条件中，标号终止，因为y = 匕，匕,匕, v

34、 = v3,vj, v, ev,所以不存在匕一匕的增广链，当前流为最大流。10.17 解：（1）给匕标号匕（s,+oo）。（2）检查叱，在弧（匕，匕）上，fsl <csl,给匕标号（s,/（匕）,/（匕）=min/（匕）,csl-fsl =min+oo,4-3 = 1,即匕标号（另1）,弧（匕,匕）,九 <%， /l（匕）= min/（匕）,九=1皿+8,3 2=1,给匕标号匕（“）。弧”,匕），fs2 < %, 4（%）= nmi 0（匕），7 几 = l给匕标号匕（邑1）":(3)检查匕，弧(匕,匕)，/14 = c14 ;不符合标号条件。检查匕，弧(匕,匕)，

35、八4<。34，/(v4) = n±il,4-3=l,给.标号匕(3,1)；弧 (v3,vj, /35 < c35, /(v5) = imil,5-3)=l,给 标号为gj)。检查匕，弧(口匕)，ar < c4t » /(v;) = nm 1,7 - 6= 1,给匕标号匕(4,1)。得到增 广链匕-匕匕匕，修改调整原流量力°),正向弧流量增加1,反向弧减少1,得到4(1)承:对流力1)进行标号检至 寻找增广链。给匕标号匕(s,+00);检查l，标记匕(5,1),标记% (另1);检查匕，标记片(u)；检查匕，标记匕(2,1)；检查匕，无满足条件弧。

36、检查%，标记匕(5,1)，匕(5,1)；得到增广链,匕- v5 .匕，调整流量e=i得 到流量於)。承卜对力进行标号，寻找增广链，得增广链匕-匕-叱-匕-匕，调整流量得力3）。裁:对力检查，已不存在增广链，该网络的最大流415。10.18 解：（a）（1）给匕标号匕（s,8）检查匕，弧（匕，匕），（匕，匕）均己满 容量,不符合标记条件，弧（匕,匕）， %=° < 1 =，s3， /（匕）=皿1/（匕）,0-九= mm+s,l _0 = 1,%标记匕（s，l）。(al)（3 ）检查匕，弧（匕，匕），/“<c“，匕标记匕（3,1）,弧（,匕）为逆向弧，人3=。不符合标记条件。

37、（4）检查匕，弧（匕,匕）,f4t <c4i, 给匕标号匕（3,1）。（5）匕己得到标号，反向追索得增 广链，f v3 -匕匕，修正调整流 量，正向弧流量增加1,反向弧减少1。 得新流4（1）对匕标记匕（s,+8）,检查匕点，己 无符合标记条件的弧，表明不存在增广(32)链，当前流为最大流，匕f匕的最大流为5,最小割为（v,v） = （匕,匕）,（匕，匕，（匕，匕）(b)（1）给匕标号匕（另8）（2）检查匕，弧（匕，匕），（匕小），（匕,匕）均已满容量，不符合标记条件，弧（匕,匕），fs2 < cs2 ,标记匕（5,1）。（3）检查叱，弧（匕,叱），/12 > o ,标记匕（

38、2,1）；弧（匕,匕），（匕43）已达容量，不标 记。检查匕，弧“3,匕），不标记，己达容量；弧（匕，匕），八4<。34，给匕标号匕（3,1）。检查匕，弧（办,匕），不满足标记条件；弧（匕，匕），zl5 c45 »给匕标号匕gj）。检查叱，弧（为，匕），了”。"，给匕标号匕（5,1）。（4）匕己得到标号,反向追索得增广链,匕一匕f v4 - v5 f vt，增广链正向弧流 量+1，反向弧-1，调整得到新流，九重新开始标号。标记匕（x）,检查匕，标记匕（“），其它匕相连弧均不符合条件。检查匕，弧（匕,匕），几0,标记匕（2,1） °检杳匕，所有弧均不符合标记条

39、件，标记结束。%未标记，现流量不存在增广链，现流量为最大流，/ = 14 ,最小割为 （匕,匕）,（匕,匕），（匕,匕），（匕，匕），（匕，也），（匕，为）。（c）首先标记匕（5,8）。检查匕，弧（匕，匕），（匕,匕）均已满容量，不符合标记条件，弧（匕,叱），fs2 < cs2 , v2标记 v2（5,2） o检查匕，弧（匕,匕），f25 < c25,标记匕（2,1）。检查,反向弧（匕,匕），/35 > 0»标号匕（5,1）。检查匕，反向弧（匕,匕），/13 > 0,标号匕（3,1）。检查匕，弧（匕，匕），fl4 <cl4,标记匕（1,1）。检查v4,弧

40、（匕,匕），f4l < c4l,标记匕（4,1） ov,已得到标号，反向追索得增广链，匕一叭u5 f匕匕匕匕，流量调整量为1。得新流力九重新开始标号。标记匕3”），检查叱，标记叱（5,1）,检查匕，没有满足标记条件的弧，标记结束。%未标记，现流量不存在增广链，现流量为最大流，/ = 13 ,最小割为（匕，匕）,（匕,匕），（匕，匕）。（d）首先标记匕（s,8）。检查匕，弧（匕叫）,几<%,标记匕（另2）。弧（匕，匕），-2 <c$2，匕标记匕（s,l） 0检查匕，弧（匕，匕），/14 <c14 ,标记匕（1,1）。弧（匕,匕），/13 < c13 ,标记匕（1,1

41、）。检查匕，弧（匕j6）, f26 < c26,标记忆（2,1）。检查匕，反向弧（匕，l）, /54 > 0 ,标记1彳（4,1）。检查1，6，弧（乙，匕），£<%，标号匕（6,1）。匕（s,”）匕己得到标号，反向追索得增广链,匕一匕一> v6 匕，流量调整量为1。得新流o匕（s,+oo）重新开始标号。标记匕（s,+8）,检查匕，弧（匕，匕），九<%,标记匕（5,2）。检查匕，弧（匕,/）,标记匕（u），弧（匕,匕），九 </，标记匕（l1）。检查%,反向弧（,%），/54 > 0 »标记匕（4,1）检查匕，反向弧（方,匕），标记匕

42、（3,1）检查匕，无可标记点，标记终止，匕未标记，当前流最大流/ = 16,最小割为（匕，匕），（%，%），（匕 #6）10.19解：将5种语言和5个人各作为一点，它们的匹配关系见图，增加一个起点s,和一个终点t,就构成一个网络图招聘人员问题就变为求上述网络图的最大流。图中所有弧的容量为1,设定的初始流量u01标记 5(0,4-00)o检查s点，弧(s,4),九 cs4,标记4(0,1)。检查4点，标记9 (4, do标记10 (4, do检查9点，标记3 (9, do检查10点;，标记5 (10, 1),检查3点，5点，无满足标记条件中的弧，标记终止, 当前流为最大流，只招聘4人，戊一法语，

43、乙一 德语，甲一 英语，丁一语10. 20 解：（a）（1）从流量/。=0开始（图al）,构适费用加权网络图必/。）°按照标号法求解s-t的最短路为，s 吟一匕一匕-f,根据各弧容量调整到£ =3,见图设。（2）构造费用加权网络卬（£）,（见图a4）,求解其最短路线为：s f%一匕-f,调整增广链上流量。得到流量力=4,（见图a5）（3）重复上述过程，必力）最短路线s f也一匕fig-f,得流量八=5,九=8,(al)： fq=q(a3)： 6=3(a4)： w(fi)(a5)： l=4(a6)： w出)(a7)： f3=5(a9)： 6=8(all)： 

44、3;=9构造八=9的费用加权图w"）,无法找到sff的最短路，即sff不存在增广链， 所以流人=9是网络最小费用最大流。（b）从流量/。= 0开始（图bl）,构造费用加权网络图叭人）o按照标号法求解w（fq）的 最短路为，s -匕-%匕-根据最短路上的最小容量调整流量得£ = 5, 见图b3o（2）构造费用加权网络卬（£）,（见图b4）,求解其最短路线为：s -匕均一乙 调 整增广链上流量。得到流量力=7 ,（见图b5）(bl)： fb=o匕(s,2)7 匕(2,6)匕(1，5)45(3,8)(b2)： w(fo)10.21解：a, b为发点,有货物为50和40单

45、位,d,e为收点，需要货物30和60单位，c为转运点，现假设一个总的发点s,向a, b分别送货50, 40单位，费用为0,再假 设一个总收点t,分别收到c, d的货为30, 60单位，运输费用为0,那么，转动问题就转 化为求sff点网络图的最小费用最大流问题。(1)从流量/。=0开始，构造费用网络图(a)卬(/0),用标号法求得最短路线为stbtctett,调整流量得新流量/1=40 °(b) ： w(fb)(s,0)(d) ： w(fi)(s,0)(e,70)：w(f2)(h) ： w(f3)（2）构成费用加权图卬（4）（图d）,其最短路线为：s .4.c 一七.八 调整流 量得到

46、力（见图e）.（3）重复:上述过程，寻找图卬（八）最短路s fa cf cf。一九 调整流量得 /3 = 80 ,图卬（八）的最短路线为：s fa 。-f,调整流量为人= 90。（4）流量人=90,从s点出发的所有弧达到容量，力为最小费用最大流。a, b, c, d, e之间的调运方案（见图j）.10.22 证明：已知g = （v,七），5（g） = min4»）, g 为简单图。rev（1）因为g是简单图，所以g中无环，无多重边。假设g中无圈，则g至少有一个悬 挂点，不妨设为小，d（y0） = l,这与5（g）之2矛盾，所以g必定存在圈。（2）因5（gr2,设乐5（r）22,取v中

47、任一点匕，因d（匕）之2,必存在边 / =（匕,匕），匕为/另一端点，显然匕工匕；又因d（匕）之团之2，与匕有至少m条边 相邻。一定可以找到边与，其端点不是匕，设为匕，令匕=机，叱,匕。因"（匕）之用，匕有至少m个，不同的点有边与匕相连，一定可以找到边。3,其端点 为匕，匕，且匕色匕，形成链匕/匕与匕63 v4，令匕=6。0%。重复上述过程，可以找到链心匕 且匕=匕匕匕，因d（vm+l）mf有m条边与匕阳相连,设其端点为匕e，如果匕+?匕，则 /me匕1%匕£”匕+闾，构成一个m+1的圈，如果乙+2任匕,则继续上述过程， 因为v中有限个点，且d（匕）之团之2,所以一定会找到

48、一个边其端点为匕，与上述搜索链 构成图，其边数大于m+1。10.23 证明：g是一个连通图，不含奇点。反证法假设g中存在割边，g= （v, e）,不妨设割边为e0其端点为九,匕，即 /=（%，匕），%£匕,匕£匕。因为匕为偶点，必可以找边6与之相连，设其另一端点为叭，同理上边为偶点，必 可找到相连边3,其另一端点为匕。以此重复操作，因为匕中点和边均有限，且g为连通图，一定可以结束搜索，得到 链匕6kd4匕.，匕=匕，则d（匕）为奇数,与g中不存在奇点相矛盾。所以g中不含割边。10.24 解：求解最大支撑树步骤如下：(1)令1=1,纥=。(。为空集)(2)选一条边"

49、£上,使巧是使(匕ei u e)不含圈的所有边e(e £石 eq中权最大的边。令鸟=与_3上，如果不存在这样的边，则7 =(乙及最大支撑树。(3)把i换成i+1,转入(2)。另一解法(1)从图中任选一点匕，令v = 匕,其余点为7(2)从v与m的边线中找出最大边，这条边一定包含在最大支撑树内，不妨设最大边 为匕，匕，将匕,匕加粗以标记是最大支撑树内的边。(3)令匕刃卜二已(4)重亚(2) (3),直到v包含所有的点，即比10.25 解：“可行流f的流量为0,即v(f)=0,当且仅当f是零流。”这种说法是不正 确的，f是零流仅是v (f) =0的充分条件。考研题选编及点评10

50、-1 （20分）有网络图如下（弧旁数字为容量c）（1）求网络中由发点集（v共和vr）到收点集（vr和vn）的最大流与最小截集。（2）若弧（vx, v3）的容量改变量为试讨论对最大流量的影响。（2007年华中科技大学运筹学（管理科学与工程）考研试题）10-2 （本题满分14分）某地输油管网络如图1所示，其中a为油田产地，c为原油出i i码头，图上所标括号外 数字为每段输油管的口输油能力，括号内数字为目前采用输油方案。（1）问现行方案是否最优？为什么？ （4分）（2）如现行方案不是最优，以现行方案为基础构成新方案。用最大流的标号算法求出最 优方案。（10分）图1（来源：2006年天津工业大学运筹学

51、考研试题）记其最小权支撑树为t。10-3 （15分）有网络图如下（边旁数字为边权，入为参数）,（1）求人二0时网络的最小权支撑树t。：（2）分析0w4 w2时最小权支撑树的变化。（来源：2006年华中科技大学运筹学考研试题）10.4填空题（1）判别网络最大流的条件是：（2）已知赋权网络图为：则其最小支撑树的权和为：（来源：2005年天津工业大学运筹学考研试题）10-5 （本题满分16分）下图为一运输网络，网络中边上第一个数是能力，第二个数字是给定的初始流。（1）用找增广链的方法求出最大流；（2）写出最大流-最小截定理并加以验证。v1（来源：2005年天津工业大学运筹学考研试题）10-6 （本题

52、满分为14分）某人每天从住处vl开车至工作地v7上班，图中各弧旁的数字为该人开车上班时经过该 弧受阻的可能性，试问该人应该选择哪条路线，使从家出发至工作地，路上受阻的可能性最 小？最小值是多少（不允许凭直观观察，要求用运筹学的方法计算）？（来源：2005年天津工业大学运筹学考研试题）【点评】图与网络分析是运筹学的核心内容之一，其内容范围说不上宽广，都是实用性非常强的 知识领域，是运筹学学习者必须掌握的内容，也是考研入学考试必然出现的内容。其核心内 容主要为：最小支撑树，最短路线，最大网络流和最小费用最大流四部分内容。（1）最小支撑部分的核心是破圈法和避圈法求解；（2）最短路线部分的核心内容是最短路线标号求解法：（3）最大网络流部分的核心内容是利用标号法求解增广值，进而进行流量调整，求解最小割集和最大流量：(4)最小费用最大流量部