第9页 中华学生百科全书

  分钟。这样，便会有 5 种安排：

  第 1 种，可以在一项工作完成以后，再进行第二项工作，最后进行第三

  项，这样总计要花 65 分钟时间；

  第 2 种是在挖坑的同时派人去运树苗，在完成挖坑工作以后再组织人力

  挑水，这样需要 50 分钟；

  第 3 种是在挖坑的同时就派人去挑水，在挑完水后再去运树苗，这样需

  要 45 分钟；

  第 4 种是在挖坑的同时就派人去挑水，在挖完坑后又派人去运树苗，这

  样只需花 35 分钟；

  第 5 种安排是 3 项工作同时开始，那么，总共只需要 30 分钟就可以完成

  任务了。

  很显然，在人力、工具等条件都允许的情况下，第 5 种安排最省时间，

  其他安排费时间多，会出现“窝工”现象。

  同样，对于一个生产汽车的工厂，厂长一定会安排不同的车间（分厂），

  分别生产汽车的发动机、轮胎、底盘、外壳、仪表、座椅、车灯、电器等零

  部件，最后进行总体装配，一辆辆崭新、漂亮、别致的汽车就会从流水作业

  线上徐徐开出来。任何一位厂长都不会安排先生产一种零部件，完成后再生

  产第二种，一直到最后一种零部件制造出来后，再去一一组装。这样，无疑

  要浪费许多时间，没有生产效率。

  建筑队要盖一幢楼房，一定要打地基，运砖瓦石、水泥、钢材等建筑材

  料，砌砖，安门窗，装水管和下水道，粉刷墙面等，如果安排不当，就会出

  现窝工现象。

  生活中也有许多例子，需要人们开动脑筋巧妙安排。你可能听过这样一

  个故事，讲的是一个人挑着一担菜，牵着一只羊，带着一条狗过河，河边只

  有一小小的船，因船太小，当人不在场时，不能把狗和羊留在一起，因为狗

  要咬羊，也不能把羊和菜留在一起，因为羊会把菜吃掉怎知办？这个人运用

  他的聪明才智，巧妙安排，把三者安全顺利地带过了河。你知道他是怎样干

  的吗？

  如果在家里做饭烧菜，你一定会先煮米饭（或蒸馒头），并利用煮饭的

  时间去洗菜、切菜，等饭（或馒头）做好了，你的准备工作也做得差不多了，

  然后再烧菜，这样可节约不少时间。

  当你仔细观察一下周围发生的事情，或者回想一下你的经历，你就会了

  解到，生活当中有着许多精明的“管家”——他们能管理好班级，管理好企

  业，管理好农业生产。这里介绍的内容，就是用图和网络的方法，解决前面

  提到的各种问题，帮助人们统筹安排时间，精打细算，提高工作效率。

  著名的哥尼斯堡七桥问题

  欧洲有一座城市，叫哥尼斯堡。有一条河流经城区，河中有两个小岛，

  共有七座桥将河的两岸和两个小岛联接起来。图中 A、B 表示两岸，C、D 表

  示两个小岛，数字 1 至 7 表示七座桥。

  有人提出一个问题，能不能从某一地点出发（例如 D 点），通过七座桥

  各一次（即不能重复过桥），然后回到出发地（也就是 D 点）？这就是有名

  的哥尼斯堡七桥问题。

  1736 年，数学家欧拉发表了一篇论文，将上面的问题用下图表示出来。

  同样地，图上 A、B 表示两岸，C、D 表示两个小岛，数字 1 至 7 表示七座桥。

  图中的点叫顶点，用来表示具体的事物。图中的线叫做边，用来表示事

  物之间的某种关系。这种图不是按比例画出的，边长不代表真正距离或其他

  数量关系，顶点和边的位置也不与实际位置一一对应。这样，就可以将复杂

  的工程系统、运输系统、管理系统等等简化成图，来解决工程任务花费时间

  最少、运输距离最短、管理费用最省等最优化问题。

  欧拉将哥尼斯堡七桥问题抽象成一个图，将上述过桥问题抽象成一笔画

  问题后，他证明，上图中的顶点都只与奇数条边相连接，因此不能将图一笔

  画成而不重复任一条边。假设第 4 条桥不是连接 C、D 小岛，而是连接 A、B

  两岸，则可用下图表示。可以明显地看出各点均与偶数条边相连接，此图就

  可以不重复地一笔画成。

  我们再看一下架设电话线的例子。在下图中，要在各单位之间架设电话

  线。电话线必须将它们连接，但为了节省线路，两单位之间也可以通过其他

  单位接通电话，例如乙村可以通过甲村、汽车站同学校接通电话，因此不必

  在乙村与学校间再架设一条电话线。这种简单形式的图就是“树”。

  由于每两单位之间架线的长度不同，因此，实际上要求找到所架电线最

  短的“树”，按这“树”的样子架线，所花时间最少、也最省钱。

  架设电话线的“树”

  供应问题

  请看供水系统管路图，某村供水站要向新开垦的土地送水浇地，供水管

  路要经过东南西北 4 片地区，每段管线最大供水能力分别表示在线中边上，

  如供水站向南片土地每分钟最多能供应 5 立方米水，再由南片向东片最多每

  分钟供应 2 立方米水等等。而这种有发点（如供水站）和收点（如新开垦地）

  的有方向的图（从发点开始到收点为止）就组成了一个网络。研究供水站通

  过这个网络每分钟最多能供给新开地多少立方米的水，这就是网络最大流问

  题。

  古代战争中就非常重视供应问题，“兵马未到，粮草先行”，说的就是

  这个问题。现代化的战争供应问题更加复杂。因为现代战争，是对多兵种、

  高技术、快速反应的全面考验，在一次战役之前，准备工作显得十分重要、

  紧迫。因此，战前往往要研究从后方向前线调运各种武器弹药，集结各地作

  战兵员和医疗、后勤保障、军事技术等各类人员，储备燃料、食品、饮用水、

  药品等等问题。

  还有许多系统都需要研究最大质量问题。如春节期间，铁路部门要研究

  铁路网络最大客运能力，以便安排列车将旅客送回家过年。发电厂（还有水

  电站）要研究电网最大送电能力，以满足工厂、农村和人民生活用电的需要。

  油田和炼油厂要研究输油管网络的最大输油能力。电话局要研究电话网的最

  大通话容量，等等。

  邮路捷径

  当你收到邮递员送来的报纸、信件的时候，你一定很高兴能从报纸上了

  解到国内外大事，从信中知晓亲戚朋友的消息。但不知道你是否注意到，邮

  递员每次送信都是沿着相同的街道、相同的方向送信。你会说，这些绿衣天

  使熟悉这些街道，甚至熟悉许多家庭，他们习惯于沿同样的路线送信，不管

  酷暑寒冬、刮风下雨，日复一日，年复一年。如何为他们选一条路程最短的

  “邮路”，使他们能相对轻松地完成他们的工作呢？这个问题是 1962 年由我

  国数学家管梅谷教授提出的，国际上因此而称为中国邮递员问题。

  我们看一看下图所表示的一个简单的街区路线图，数字表示街道的长度

  （米）。那么，假设邮递员从邮局出发，沿什么路线送完信件返回邮局，所

  走的路最少呢？