图与网络分析

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,110.2 已知9个人中，和两个人握过手， 各和四个人握过手，各和五个人握过手，各和六个人握过手，证明这九个人中一定可以找出三个人互相握过手。10.3 有八种化学药品A、B、C、D、P、R、S、T要放进储藏室保管。出于安全原因，下列各组药品不能储存在同一室内：A-R、A-C、A-T、R-P、P-S、S-T、T-B、T-D、B-D、D-C、R-S、R-B、P-D、S-C、S-D问储存这八种药品至少需要多少间储藏室。图10-110

2、.4 已知有十六个城市及他们之间的道路联系（见图10-1）。某旅行者从城市A出发，沿途依次经过J、N、H、K、G、B、M、I、E、P、F、C、L、D、O、C、G、N、H、K、O、D、L、P、E、I、F、B、J、A，最后到达城市M。由于疏忽，该旅行者忘了在图上标明各城市的位置，请应用图的基本概念及理论，在图101中标明各城市AP的位置。10.5 十名研究生参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表101给出了每个研究生应参加考试的课程（打号的）。规定考试应在三天内结束，每天上下午各安排一门。研究生们提出希望每人每天最多考一门，又课程A必须安排在每一天上午考，课程F安排在最后一门

3、，课程B只能安排在中午考，试列出一张满足各方面要求的考试日程表。表10-1考试课程研究生ABCDEF1234567891010.6 用破圈法和避圈法找出图10-2的一个支撑树。 e1v1v2v3v4v5v6v7v8v9v10e2e3e7e4e5e6e8e9e10e11e12e13e14e15图10-210.7 用破圈法和避圈法求图103中各图的最小树。(a)728232443613654174312223425(b)223221533522422536474536321(c)(d)图10-310.8 已知世界6大城市：（Pe）、（N）、（Pa）、（L）、（T）、（M）。试在由表101所示交通网

4、络的数据中确定最小树。表10-2城市PeTPaMNLPe×1351776850T13×60706759Pa5160×57362M777057×2055N68673620×34L505925534×10.9 有九个城市,其公路网如图104所示。弧旁数字是该段公路的长度，有一批货物从运到，问走那条路最短？343323122.5542V1V2V3V4V5V6V7V8V93图10-410.10 用标号法求图105中V1到各点的最短路。2261304202047105101515751030420V1(a)(b)图10-5V1985218374

5、310710.11 用Dijksrea方法求图106中V1到各点的最短距离。V12847615129143216317924V2V3V4V5V6V7V8V9V10V11图10-610.12 求图10-7中从V1到各点的最短路。12445331222V1V2V4V323V5V6图10-710.13 在图108中(1) 用Dijkstra 方法求从V1到各点的最短路；(2) 指出对V1来说那些顶点是不可到达的。V4413341624367V1V2V7V5V6V8V3图10-810.14 已知八口海上油井，相互间距离如表10-2所示。已知1号井离海岸最近，位5浬。问从海岸经1号井铺设油管将各油井连接

6、起来，应如何铺设使输油管线长度为最短（为便于计算和检修，油管只准在各井位处分叉）。表10-2 各油井间距离 单位：km从 到234567811.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 设某公司在六个城市c1, , c6 有分公司，从ci 到cj 的直达航线票价记在下面矩阵的（i，j）位置上（表明无直达航线，需经其他城市中转）。请帮助该公司设计一张任意两城市的票价最便宜的路线表。10.16 在如图10-9 所示的网格中，每弧旁的数字是（cij，fij

7、）。(1) 确定所有的数集；(2) 求最小截集的容量；(3) 证明指出的流是最大流。(2,2)(4,3)(3,3)(1,0)(2,2)(5,2)(3,1)图 10-910.17求如图10-10 所示的网络的最大流（每弧旁的数字是（cij，fij）。VsVt（1,1）（4,3）（7,6）（4,3）（3,2）（3,2）（3,2）（4,3）（4,2）（5,3）（8,3）（2,2）图10-1010.18用Ford-Fulkerson的标号算法求图10-11中所示各容量网络中从Vs到Vt的最大流，并标出个网络的最小割集。图中各弧旁数字为容量cij，括弧中为流量fij。5(5)4(3)3(2)2(2)1(

8、1)5(4)5(5)5(2)1(1)2(2)3(3)4(4)5(3)1(1)2(1)2(2)1(2)2(1)2(1)2(2)2(0)1(0)2(2)2(0)1(1)(a)(b)3(2)5(5)3(3)3(3)2(0)6(4)4(4)2(2)5(4)2(0)8(6)6(6)(c)12(10)6(5)3(3)5(4)4(3)3(3)5(4)4(4)2(2)5(4)2(2)9(9)9(6)(d)图10-1110.19 某单位招收懂俄、英、日、德、法文的翻译各一人。有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文。问最多有几人能得到招聘，有分别被聘任从事那一文种

9、的翻译。10.20求图10-12中从st的最小费用最大流，各弧旁数字为（cij，bij）。（4,1）（7,6）（5,2）（2,3）（3,2）（8,4）（6,1）st（a）（b）（7,7）（5,3）（5,1）（7,2）（10,9）（5,3）（8,4）（10,10）（7,2）st图10-1210.21 图10-13中，A、B为出发点，分别有50 和40 单位物资往外发运，D、E为收点，分别需要物资30 和60 单位，C为中转点，各弧旁数字为（cij，bij）。求满足上述收发量要求最小费用流。ABCDE(20,90)(80,10)(10,30)(30,20)(40,30)(50,40)(10,20)

10、图10-1310.22 设G=（V,E）是一个简单图，令（G）=vVmind(v)(称（G）为G的最小次)。证明：（1）若（G） 2，则G必有图；（2）若（G） 2，则G必有包含至少（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个奇数，所以不可能是某个图的次的

11、序列，更不是某个简单图的次的序列。【或者】假设7，6，5，4，3，2为某个简单图的次的序列，则图中有6个点，作为简单图点的最大次数为n-1，即最大次数为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个点，不妨设为，其中 ，次为6，表明，与除自身外的剩余6个点均相连。即，的次不少于2，与的次

12、为1矛盾。所以，6，6，5，4，3，2，1不是某个简单图的次的序列。（3）假设6，5，4，3，2，1为某个简单图的次的序列，则图中存在7个点，不妨设为，因为=6, =1,所以与其他6个点相连，而仅与相连，又因为，则，与除和自身之外的所有点相连，则必须与，相连，所以与，相连，与矛盾，所以6，6，5，4，3，2，1不是某个简单图的次的序列。10.2 解：设9个人，为9个点，两人握手设为两点之间存在相连边，握手问题转化为一个简单图，其中，次的序列为2，4，4，5，5，5，5，6，6。这9个人中一定可以找到3个互相握过手，转化为在图中一定存在3个点彼此相连。因为，之间一定存在两点相连。假如，互相均不相

13、连，因为次均为5，所以，均与剩余的4个点，相连，这与 =2矛盾。不妨设，中存在，之间相连。必可以找到第三点均与，相连。假设不存在第3点均与，相连，分别与定义不同的4个点相连，即存在8个不同的点分别与或相连，加上，共计10个点，这与图中9个点矛盾。所以在图中，必存在3个点彼此相连。（a）BATCRPSD10.3 解：将8种化学药品A，B，C，D，P，R，S，T设定为8个点，两种药品不能贮存同一室内状态，设定为两点之间存在一边相连，画出药品关系图如下：（图10-3（a）（B）BATCRPSD图10-3 在图（a）中，两点之间相连的药品均不能存贮在一起。对于由点A，B，C，D，P，R，S，T的完全图

14、，求图（a）的补图，得图（b）,在（b）图中，彼此相连的药品均可以为存贮庄点，因为，从S，D开始搜索，（S，A，B）彼此相连，（D，R）相连，（T，C，P）彼此相连。所以至少需要3间贮存室，存效组合为（S，A，B），（T，C，P），（D，R）。10.4 解：依据旅行者的路线统计城市间的相互关系。点（城市）相邻城市（相邻点）次点相邻点次AJ，M2IM，E，F3BG，M，F，J4JA，N，B3CF，I，O，G4KH，G，O3DL，O2LC，D，P3EL，P2MB，I，A3FP，C，I，B4NJ，H，G3GK，M，C，N4OD，C，K3HM，K2PE，F，L3A M I E J B F PN G C

15、 LC K O D图10-4由点的次可知，A，D，E，H为2，则为4个顶点；B，C，F，G的次为4，则为4个顶点；某系为边点，城市布局图为图10-4。 DAEBF图10-5 （b）10.5 解：将课程A，B，C，D，E，F设定为6个点，同时学生选某课程认为存在相邻边。依据学生1-10的选课划分课程关系图10-5（a），要求学生一天最多考1门，即图（a）中相连的课程不能排在同一天。对于点ABCDEF的关系图，求图（a）的补图（b）。CABDEF图10-5 （a） 那么，图（b）中相邻的课程可以安排在同一天，可保证学生一天最多考一门，所以（A，E），（F，D），（C，B）分别各为一天，安排如下：天

16、上午下午123ACDEBF10.6 解：（破圈法）寻找图中的圈，去掉圈中的一边。（1）圈（）去掉；圈（）去掉；圈（）去掉。（2）圈（）去掉；圈（）去掉，得到支撑树(c)。e1v1v2v3v4v5v6v7v8v9v10e2e3e7e4e5e6e8e9e10e11e12e13e14e15(a) v1v2v3v4v5v6v7v8v9v10e2e3e7e5e6e8e9e10e11e12e14e15(b) v1v2v3v4v5v6v7v8v9v10e2e3e7e8e10e11e12e14e15(b) (避圈法)(1) 从点出发，边相邻边增加边和点，保证不构成回路。出发，增加。(2) 相邻边，增加，相邻边

17、，增加点 ，。(3) 相邻边，增加，相邻边，增加点，。将点均包含在图中，且不存在回路，构成一个支撑树（f）。(e)e1v1v2v3v4v5v10e12e2e7e6v6v8e1v1v2v3v5e2e7(d)v1v2v3v4v5v6v7v8v9v10e2e3e7e8e10e11e12e14e15(f)10.7 解：a）（破圈法）在图中寻找圈，去除圈中权值最大的边（V1 ，V2 ，V3）去除（V1 ,V3 ）边；（V1 ，V4 ，V7）去除（V4 ,V7 ）边；（V2 ，V5 ，V8）去除（V2 ,V8 ）边；（V6 ，V8 ，V9）去除（V7 ,V8 ）边，得到图（a2）（V2 ，V5 ，V3）去

18、除（V2 ,V5 ）边；（V3 ，V6 ，V4）去除（V3 ,V6）边；（V5 ，V6 ，V8）去除（V5 ,V6 ）边，得到图（a3）（V1 ，V2，V3 ,V4）去除（V1 ,V2）边，( V3 ，V4，V6 ,V8，V5) 去除（V4 ，V6）边, 得到图（a4）。( V1 ，V4，V3 ,V5，V8，V7)去掉（V3 ,V4）边，得到图（a5）,图中不再有回路，则为最小树，其权值和为(a2)v1v2v5v4v7v8v3v6722124431357(a1)v1v2v5v4v7v8v3v672823244361365417 (a3)v1v2v5v4v7v8v3v6721244313(a4)

19、v8v1v2v5v4v7v3v62124313(a5)v1v8v2v5v4v7v3v62124313图10-7 （1） (避圈法)从V1 出发，即V =V1其余点为，与间有边（V1 ，V2），（V1 ，V3），（V1 ，V7），（V1 ，V4），权值分别为7，8，3，2，权值最短边为（V1 ，V4）。则加粗边（V1 ，V4），令。与间最短边为（V1 ，V7），加粗边（V1 ，V7），令。依次按照上述规则操作，直到。则得到最小树为图（a3）, 其权值和为16。 (a1)v1v2v5v4v7v8v3v672823244361365417(a2)v1v2v5v4v7v8v3v672823244361

20、365417 (a5)v1v8v2v5v4v7v3v62124313图10-7 （2）（b）依图（a）中的步骤，得到图b）的最小树图为10-4 （b），其权值和为222132222图10-7 （c）122232图10-7 （b） 3421334图10-7 （d）（c）依图（a）中的步骤，得到图c）的最小树图为10-7 （c），其权值和为 （d）依图（a）中的步骤，得到图d）的最小树图为10-7 （d），其权值和为 10.8解：6城市（Pe），（N），（Pa），（L），（T），（M）对应6个点，依表中数据得到交通网络图为：TLPaNMPe13517768506070596734573655202

21、按照避圈法，V=Pe，=T，L，Pa，M，N，与的最短边为（Pe，T），加粗（Pe，T）边，即V=Pe，T，=L，Pa，M，N，依次推导。逐次加入边（Pe，L），（L，Pa），（L，N），（N，M），得到最小树图：PeTLPaN9解：利用双标号法，求的最短路线。（1）从出发，标号为（，0），=，其余点为。（2）中点相邻的未标号的点有，则对进行标号（，3），令，。（3）中点，与未标号的，=，给标号（，），令343323122.5542V1(V1,0)(V1,3)V2(V2,6)V3V4(V1,4)V5(V2,5)(V2,6)V6V7(V4,7)V8(V6,8.5)V93

22、(4) 依（3）中的原理，与相邻边累计最小为（，），（5）按照上述原则，依次标号顺序为：给标号（，6），=；给标号（，6），=，；给标号（，7），=，；给标号（，8.5），=，；已标号，因此，的最短路线为，最短路长为8.5。10.10解：（a） 2261304202047105101515751030420V1(V1,0)V2(V1,30)V3(V2,31)(V5,29)V4V5(V6,27)V6(V1,20)V7(V6,24)V8(V7,28)(V8,33)V9(V9,34)V10V11(V8,34)V12(V11,44) （1）从出发，令=，其余点为，给标号为（，0）。（2）与相邻边有（）

23、,()，给标号（，20），令（3）与相邻边有（）,( )，（），（）=，给标号（），令。（4）依次标号：（，27），（，28），；（，29），（，30），；（，31），（，33），； (，34)，（，34），（，44），至此，全部点都已标注。V11V12261304202047105101515751030420V2V3V4V5V6V7V8V9V10V126到各点的最短路只需从该点出发，逆向搜索标号就可得到，且该标号中第2组数字就是到该点的最短距离。 V2 : V2 ， V3 : ， V4: ， V5: ， V6: ， V7: ， V8: ， V9: ， V10: ， V11: ， V12:

24、， V1(V1,0)V2(V1,9)V3(V1,8)V4(V2,10)V5(V2,1)V6V7(V4,13)9852183743107(b) (1) 从出发，令=，其余点为，给标号为（，0）（2）与相邻边有（）,( )，累计距离，给标号（，8），令（3）按照以上规则，依次标号，直至所有的点均标号为止， 到某点的最短距离为沿该点标号逆向追溯。标号顺序为：V3 (V1，8)，V2 (V1，9)，V4 (V2，10)，V1 (V4，13)，V5 (V2，11)，V6 (V5，14)。到各点的最短路见图中粗线。 10.11 解：2847615129143216317924V1(V1,0)V2(V1,2

25、)V3(V4,15)V4(V1,8)V5(V2,3)V6(V9,10)V7(V6,14)V8(V9,11)V9(V5,4)V10(V7,15)V11(V10,19) (1) 从出发，令=，其余各点集合为。给标号为（，0）,的所有边为（），（），累计距离最小为，给标号为（，2），令 （2）的所有边为（），（），（），累计距离最小为，令，（3）按照标号规则，依次给未标号点标号，直到所有点均已标号，或者不存在有向边为止。标号顺序为：V5 (V2，8)，V9 (V5，9)，V4 (V1，8)，V4 (V1，8)，V6 (V9，10)，V8 (V9，11)，V7 (V6，14)，V3 (V4，15)，V

26、10 (V1，15)，V11 (V10，19)。则到各点的最短路线按照标号进行逆向追索（结果见图中粗线）。例如，最短路为，权值和为19。10.12解：求解到各点的最短路。（1）从出发，标号为（，0），令=，其余各点集合为。（2）的有向弧有（），（），最小累计权值，给标号为（，1），令，即=，12445331222V1(V1,0)V2(V1,1)V4(V1,2)V3(V2,4)223V5(V3,5)V6（3）的有向弧有（），（），（）,给标号（，2），。（4）的有向弧有（），（）,给标号（，4），。（5）的有向弧有（），（）,给标号（，4），。（6）不存在有向弧，而还未标号，表明不能到达，到，的

27、最短路按标号逆向追索可得。10.13 解：（1）(i) 从出发，标号为（，0），令=，其余各点集合为。(ii) 的有向弧有（），（），（）,给标号（，1），令。（iii）的有向弧有（），（），（）,给标号（，3），令。V4413341624367V1(V1,0)V2(V1,4)V7(V1,3)V5(V1,1)V6(V5,7)V8(V6,10)V3（iv）依据上述规则，依次标号（，4），（，7），（，10）。此时， 。（v）不存在有向弧，标号终止，采用逆向标号追索，得到到各点的最短路为： V2 ： V2 ； V5 ： V5 ； V7 ： V7 ； V6 ： V5 ； V8 ： 。（2）依据（1）

28、中的标号结果，标号终止时，依然没有标号，表明出发，不能到达。10.14 解：寻求铺油管线最短问题，可转化为含有8个点的赋权完全图的最小树求解问题。可采用破圈法和避圈法求解。以下采用避圈法求解。（1）从出发，令=，其余各点集合为，从表中划去第一列。（2）寻求的最短边，从表中第一行寻找最小值，最小，令，从表中划去第5列。（3）寻找的最短边，从表中第一行，第五行寻找最小值，最小值为，令，划去表中第4列，。V1V2V3V4V5V6V7V8V1V2V3V4X1.32.10.91.3X0.91.82.10.9X2.60.91.82.6X0.71.21.70.71.82.62.51.62.02.31.91.

29、51.51.11.00.9V5V6V7V8 0.71.82.01.51.22.62.31.11.72.51.91.00.71.61.50.9X0.91.10.80.9X0.61.01.10.6X0.50.81.00.5X(4) 寻找的最短边，在表中V中元素各行中寻找最小值得到（即从第1，4，5行寻找），令，划去表中第8行。（5）按照（4）依次进行操作，直到为止，得到结果如下图：0.90.70.90.80.51.00.9V1V4V5V6V7V8V3V2铺设输油管线全线长为：S=d01+d15+d54+d56+d58+d87+d83+d32 = 5+0.9+0.7+0.9+0.8+0.5+1.0+

30、0.9=10.7(哩)10.15 解：= （）构造= ，其中 同理构造=（），=得到=，则矩阵为从到城市的最便宜原价为，其路线为：10.16解：（1）所有的截集（割集） ； ； ； ； （3，3）（5，2）（1，0）（4，3）（3，1）（3，2）（2，2）（2）对应（1）中所有截集的容量为：6，7，7，5，8，所以最小截集为，其容量为5。（3）图中指出流的流量为非作歹，由定理最大流等于最小割容量可知当前流是最大流。也可用标号法证明不存在增广链，而说明当前流是最大流。（i）给标号（ii）检查相邻的弧，弧已达容量，不满足标号条件中，弧，给标号，即标号（iii）检查，弧不满足标号条件中，弧，给标号，

31、即标号。（iv）检查 ，弧，均不满足标号条件中，标号终止，因为，所以不存在的增广链，当前流为最大流。10.17解： （1）给标号。（2）检查，在弧上，给标号，即标号，弧，给标号。弧，给标号（1，1）（3，2）（4,3）（5,3）（3,2）（7,6）（8,3）（4,2）（4,3）（3,2）（4,3）（3,2）（4，1）：（3）检查，弧，；不符合标号条件。检查，弧，给标号；弧，给标号。检查，弧，给标号。得到增广链，修改调整原流量，正向弧流量增加1，反向弧减少1，得到（1，1）（3，2）（4,4）（5,3）（3,2）（7,7）（8,3）（4,2）（4,3）（3,3）（4,3）（3,2）（5，1）：对

32、流进行标号检查，寻找增广链。给标号；检查，标记，标记；检查，标记；检查，标记；检查，无满足条件弧。检查，标记，；得到增广链，调整流量=1得到流量。（1，1）（3，2）（4,4）（5,3）（3,2）（7,7）（8,4）（4,3）（4,4）（3,3）（4,3）（3,2）（5，1）：对进行标号，寻找增广链，得增广链，调整流量得。（1，1）（3，3）（4,4）（5,4）（3,2）（7,7）（8,5）（4,3）（4,4）（3,3）（4,4）（3,2）：对检查，已不存在增广链，该网络的最大流f=15。10.18解：（a）2(2)2(2)2(0)2(1)2(1)2(2)1(1)2(0)1(1)2(1)1(1

33、)1(0)(a1)（1）给标号检查,弧,均已满容量，不符合标记条件，弧，标记。（3）检查，弧，标记，弧为逆向弧，不符合标记条件。2(2)2(2)2(0)2(1)2(1)2(2)1(1)2(1)1(1)2(2)1(1)1(1)(a2)（4）检查，弧，给标号。（5）已得到标号，反向追索得增广链，修正调整流量，正向弧流量增加1，反向弧减少1。得新流对标记，检查点，已无符合标记条件的弧，表明不存在增广链，当前流为最大流，的最大流为5，最小割为（b）5(2)5(4)5(5)5(4)5(3)4(4)3(3)2(2)1(1)1(1)2(2)3(2)4(3)5(5)(1) 给标号(2) 检查,弧,，均已满容量

34、，不符合标记条件，弧，标记。 (3) 检查，弧，标记；弧，已达容量，不标记。检查，弧，不标记，已达容量；弧，给标号。检查，弧，不满足标记条件；弧，给标号。检查，弧，给标号。(4) 已得到标号，反向追索得增广链，增广链正向弧流量+1，反向弧-1，调整得到新流。5(3)5(5)5(5)5(4)5(4)4(4)3(3)2(2)1(1)1(1)2(2)3(3)4(3)5(5)重新开始标号。 标记，检查，标记，其它相连弧均不符合条件。 检查，弧，标记。 检查，所有弧均不符合标记条件，标记结束。未标记，现流量不存在增广链，现流量为最大流，最小割为。（c）3(2)3(3)4(4)2(2)2(0)8(6)6(

35、6)5(4)6(4)3(3)5(5)_）2(0)（4，1）首先标记。检查,弧,均已满容量，不符合标记条件，弧，标记。检查，弧，标记。检查，反向弧，标号。检查，反向弧，标号。检查，弧，标记。检查，弧，标记。已得到标号，反向追索得增广链，流量调整量为 1。得新流。3(3)3(2)4(4)2(1)2(0)8(7)6(6)5(5)6(5)3(3)5(5)_）2(0)重新开始标号。 标记，检查，标记，检查，没有满足标记条件的弧，标记结束。未标记，现流量不存在增广链，现流量为最大流，最小割为。（d）首先标记。检查,弧,标记。弧，标记。检查，弧，标记。弧，标记。检查，弧，标记。检查，反向弧，标记。检查，弧，

36、标号。12（10）6（5）3（3）5（4）5（4）4（4）3（3）4（3）5（4）2（2）2（2）9（9）9（6）已得到标号，反向追索得增广链，流量调整量为 1。得新流。12（10）6（6）3（3）5（4）5（5）4（4）3（3）4（3）5（4）2（2）2（2）9（9）9（7）重新开始标号。 标记，检查,弧,标记。 检查，弧，标记，弧，标记。检查，反向弧，标记检查，反向弧，标记 检查，无可标记点，标记终止，未标记，当前流最大流，最小割为10.19解：将5种语言和5个人各作为一点，它们的匹配关系见图，增加一个起点s，和一个终点t，就构成一个网络图戊德S丁丙甲乙日英俄法t招聘人员问题就变为求上述网

37、络图的最大流。图中所有弧的容量为1，设定的初始流量1(1) 1(1) 1(1) 1(0) 1(1) 1(1) 161(1) 1(0) 1(1) 1(0) 1(0) 1(0) 1(1) 1(0) 1(1) 1(1) 1(0) 1(1) 1(0) 1(1) S543210987t(9,1)(s,1)(10,1)(4,1)(4,1)1(0) 标记。检查s点,弧,标记。检查4点，标记9（4，1）。标记10（4，1）。检查9点，标记3（9，1）。检查10点，标记5（10，1），检查3点，5点，无满足标记条件中的弧，标记终止，当前流为最大流，只招聘4人，10.20解：（a）（1）从流量开始（图a1），构适

38、费用加权网络图。按照标号法求解s-t的最短路为，根据各弧容量调整到，见图a2。（2）构造费用加权网络，（见图a4），求解其最短路线为：，调整增广链上流量。得到流量，（见图a5）(3)重复上述过程，最短路线，得流量，7(0)4(0)3(0)2(0)5(0)6(0)8(0)ts(a1)：f0=0t(3,6)6123214(2,3)(1,4)s(s,0)(s,1)(a2)：W(f0)7(0)4(3)3(3)2(0)5(3)6(3)8(0)ts(a3)：f1=3t(3,6)6-11-232 -21-14(s,4)(2,4)s(s,0)(s,1)(a4)：W(f1)7(0)4(4)3(3)2(1)5(4

39、)6(3)8(0)ts(a5)：f2=4t(3,7)6-1-23 -32 -21-14(s,4)(1,5)s(s,0)(1,2)(a6)：W(f2)7(0)4(4)3(3)2(1)5(5)6(4)8(1)ts(a7)：f3=5t(2,8)6-1-23 -3-2 1-14 -4(s,4)(2,5)s(s,0)(1,2)(a8)：W(f3)7(3)4(4)3(0)2(1)5(5)6(4)8(4)ts(a9)：f4=8t(2,8)-66-123 -3-2 1-14 -4(s,4)(1,5)s(s,0)(3,2)(a10)：W(f4)7(4)4(4)3(0)2(0)5(5)6(5)8(5)ts(a11

40、)：f5=9t-66-123 -2 1-14 -4(s,4)(1,5)s(s,0)(a12)：W(f5)构造的费用加权图，无法找到的最短路，即不存在增广链，所以流是网络最小费用最大流。（b）从流量开始（图b1），构造费用加权网络图。按照标号法求解的最短路为，根据最短路上的最小容量调整流量得，见图b3。（2）构造费用加权网络，（见图b4），求解其最短路线为：，调整增广链上流量。得到流量，（见图b5）7(0)5(0)5(0)8(0)7(0)5(0)10(0)7(0)10(0)st(b1)：f0=07314239210S(s,0)(1,5)(3,8)t(4,11)(b2)：W(f0)(s,2)(2,

41、6)7(0)5(5)5(5)8(0)7(5)5(5)10(0)7(5)10(0)st(b3)：f1=57-3-142 -2-39-2 210S(s,0)(3,8)(3,11)t(3,18)(b4)：W(f1)(s,2)(1,9)7(2)5(5)5(5)8(0)7(5)5(5)10(2)7(7)10(0)st(b5)：f2=7(2,7)(1,14)-77-3-142 -2-39 -9-2 10S(s,0)(s,10)(2,14)t(3,23)(b6)：W(f2)7(7)5(0)5(5)8(0)7(5)5(5)10(7)7(7)10(5)st(b7)：f2=1310.21解：A，B为发点，有货物为

42、50和40单位，D，E为收点，需要货物30和60单位，C为转运点，现假设一个总的发点S，向A，B分别送货50，40单位，费用为0，再假设一个总收点t，分别收到C，D的货为30，60单位，运输费用为0，那么，转动问题就转化为求点网络图的最小费用最大流问题。SABCDET(20,90)(80,10)(60,0)(10,30)(30,20)(30,0)(40,30)(50,40)(10,20)(40,0)(50,0)（1）从流量开始，构造费用网络图（a）,用标号法求得最短路线为，调整流量得新流量。SABCDET20(0)80(0)60(0)10(0)30(0)30(0)40(0)50(0)10(0)40(0)50(0)(a) ：f0=0SABCDET901003020030402000(b) ：W(f0)(s,0)(s,0)(s,0)(B,30)(C,40)(E,40)SAB