下载文档原格式
第六章图论(Graph Theory)◎知识目标：掌握图的方法与原理；图的基本概念；最小树、最短路、最大流的概念、计算与应用；了解中国邮路问题与解法。
◎能力目标：通过学习，使学生掌握图的方法与原理，提高分析问题和解决问题的能力。
◎本章重点：最小树、最短路、最大流的计算与应用◎本章难点：最短路的应用、最大流的计算引例：哥尼斯堡七桥问题18世纪著名古典数学问题之一。
在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。
问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。
有关图论研究的热点问题。
18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。
当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。
这就是哥尼斯堡七桥问题。
L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。
他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。
当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。
Konigsberg城中有一条名叫Pre gel的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。
Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。
后来推论出此种走法是不可能的。
他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。
所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。
第六章图论(Graph Theory)◎知识目标：掌握图的方法与原理；图的基本概念；最小树、最短路、最大流的概念、计算与应用；了解中国邮路问题与解法。
◎能力目标：通过学习，使学生掌握图的方法与原理，提高分析问题和解决问题的能力。
◎本章重点：最小树、最短路、最大流的计算与应用◎本章难点：最短路的应用、最大流的计算引例：哥尼斯堡七桥问题18世纪著名古典数学问题之一。
在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。
问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。
有关图论研究的热点问题。
18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。
当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。
这就是哥尼斯堡七桥问题。
L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。
他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。
当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。
Konigsberg城中有一条名叫Preg el的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。
Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。
后来推论出此种走法是不可能的。
他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。
所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。
第八章图论方法§1 图论中图的概念在人们从事的各种活动中，为了反映事物之间的关系，常在纸上用点和线画出各种各样的示意图。
例如，为了反映某地区的铁路交通、公路网分布情况，画出铁路、公路交通图。
在这些图中以点表示城镇，用点与点之间的连线表示城镇之间的铁路或公路的沟通情况。
诸如此类的图还有电缆线分布图、供水道及下水道分布图、航空线图等等。
再如，在一场有5支球队参加的球类比赛中，比赛情况也可以用图表示出来，如图6-1，我们用点代表各个球队，某两个队比赛过一次，就在两个点之间画一条箭线。
从图中可以看出A队与其他各队都比赛过，只有一场败给C 队。
而B队和E队各比赛过两场，成绩都是一胜一负，等等。
图6-1从上述例子中可以看出，图的最基本要素是：点、以及点与点之间的一些连线。
通常用点表示我们所要研究的对象（如城市、运动队、状态等等），用线表示研究对象间的某种特定关系（如两个城市之间有铁路，两个运动队之间已经比赛过等）。
因此可以说，图是反映对象之间关系的一种工具。
如果两个对象之间有某种特定关系，那么就用一条线连接这两个点。
必须指出：上述图中点的相对位置如何，点与点之间连线的长短曲直，对于反映研究对象之间的关系并不很重要，因此，图论中的图与几何图、工程图本质上是不同的。
另外在许多情况下，我们要研究的“关系”只用一条线反映还是不够完全。
比如说比赛，我们关心的如果不只是两个队是否比赛过，还要了解比赛的胜负情况，我们可以用一条箭线（有向线）来表示，如果A队胜了B队，就表示为A→B。
如图6-1所示，从图中可以看出A队三胜一负，D队三场全负等。
类似的情况在生产和生活中也是常见的，例如交通运输中的“单行线”、部门之间的领导与被领导关系、一项生产活动中各工序之间的先后次序关系等等。
图论中把不带箭头的连线叫做边，把带箭头的连线叫做弧。
如果一个图是由点和边所构成的，则称之为无向图，记作G=（V，E），其中V表示图G中的所有点组成的点集合，E表示图G中所有边组成的边集合。
如，交通图。
如果一个图是由点和弧所构成的，则称之为有向图，记作G=（V，A），其中V表示图G中的点集合，A表示图G中所有弧组成的弧集合（如上图）。
其次，为了反映两个城市之间铁路线的公里数（或运行时间等），就要在这两个城市之间的连线旁边写上里程数（或运行时间等）。
这就是说，根据问题的需要，还可以在图的点旁或连线旁标上数，统称为权数。
权数在不同的场合可以有不同的含义，如距离（长度），时间、费用、容量等等。
如果给图中每一条连线赋予一个数，则称这样的图G为赋权图，所谓网络就是指定了起点（发点）和终点（收点）的赋权图。
对要研究的问题确定具体对象及各对象间的关系，并用图的形式表示出来，这样的图就是对研究问题建立的图模型。
用建立图模型的方法往往能帮助我们解决一些用其他方法难以解决的问题。
例1、有甲、乙、丙、丁、戊、已六名运动员报名参加A、B、C、D、E、F六个项目的比赛。
表中打√的是各运动员报名参加的比赛项目。
问六个项目的比赛顺序应如何安排，才能保证每名运动员都不连续地参加两项比赛。
解：把比赛项目作为研究对象，用点表示。
如果两个项目有同一名运动员参加，就在代表这两个项目的点之间连成一条线，可得一图。
在该图中只要找出一个点的序列，使依次排列的两个点间没有连线，就能保证每名运动员不会连续参加两项比赛。
例如，从图上可看出，按照A、C、B、F、E、D顺序安排比赛，即可满足要求。
书P136练习6.3有十名研究生要参加六门课程的考试。
由于选修的课程不同，考试门数也不一样。
表6-4给出了每个研究生应参加考试的课程（打△号的）。
规定考试应在三天内结束，每天上下午各安排一门。
研究要求每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门考，课程B只能安排在下午考试，试列出一个满足各方面要求的考试日程表。
表6-4解：把考试课程作为研究对象，用点表示。
如果两门课程有同一名研究生参加考试，就在代表这两门课程的点之间连成一条线，可得一图如下。
这个图就是练习6.3问题的图模型。
在该图中第一天上午写入A，第三天下午写入F，因B课程与课程A和F有联系，故只能排入第二天下午，剩下的课程C、D、E要找出两个点间没有连线，例如，从图上可看出，按照A点与E 点间无连线，故E课程可排第一天下午，同理C、D课程安排第二天与第三天上午，即可满足要求。
§2 树和图的最小生成树在各式各样的图中，有一类简单而且十分有用的图，即所谓树图（简称树，记作T（V，E））。
树图就是无圈（即回路）的连通图。
这类图与大自然中树的特征相似，因而得名为树图。
铁路专用线、管理组织机构、学科分类往往都可以用树图的形式表示。
例如，下面图（1）就是树图，而图（2）因为图中有圈（回路），所以它不是树；图（3）因为不连通，所以也不是树图。
可见，树必须是连通的而且是不含圈的图。
任一树图中的连线数一定比其点数少一。
V1 V1 V1 V8V2 V3 V2 V3 V2 V9V6V5 V4 V4 V5 V3 V4V8V7 V6V8 V9 V7 V5 V7图（1）图（2）图（3）从一个给定的无向图G=（V，E）中，去掉图G中一些连线，保留图G中的所有点，所得的树图被称为图G的生成树。
由一个图G可以生成若干树图，但不同生成树的连线总长度也是不同的，其中连线总长度最小的生成树就称为最小生成树。
§3 最小生成树的算法求图的最小生成树问题就是在一个网络中，从一个起点出发到所有结点，找出一条或几条路线，构成线路总长度最小的一个树问题。
为了解决这个问题，我们用一个在住宅小区安装供水管道的例子来用说明求图的最小生成树的普赖姆算法。
图6-2是各座住宅楼之间可以安装供水管道的距离图，图中圆圈代表住宅楼，连线上的数字代表距离（以米为单位）。
图6-2 各座住宅楼之间可以安装供水管道的距离图最小生成树的普赖姆算法就是把最近的未连接点连接到那些已经连接的结点上去，连接的方法如下：1.从始点出发，我们来查找与始点1最近的结点，发现结点3与1的距离最近，为100米，于是把1——3连接好，见图6-3。
2.从已连接点1、3出发，查找与结点1、3最近的结点，发现结点4与1的距离最近，为300米，于是把1——4连接好，见图6-3。
3.从已连接点1、3、4出发，查找与始点1、3、4最近的结点，发现结点7与1的距离最近，为400米，于是把1——7连接好，见图6-3。
4. 从已连接点1、3、4、7出发，查找与始点1、3、4、7最近的结点，发现结点5与3的距离最近，为500米，于是把3——5连接好，见图6-3。
5.用同样的方法查到5与6的距离最近，为200米，7与2的距离最近，为900米，于是把5——6、7——2连接好，见图6-3。
必须指出：在查找与连接过程中，要避免出现回路，即圈（否则就不是要求的树图），直到所有结点都被连接到起点为止。
图6-3 各座住宅楼之间供水管道的最小生成树图6-3就是各座住宅楼之间供水管道的最小生成树。
为了给各座住宅楼供水，总共需要2400米水管。
关于最小生成树问题，我们再举例一个例子如下：已知连接5个城市的公路交通图6-4，图中连线旁边数字是距离（单位：公里）。
现在要在这5个城市之间架设有线电视电缆，为了便于维修，要求电缆必须沿公路架设，而且电缆线的总长度要最少。
我们用普赖姆法（也称选线避圈法）计算如下：1.开始时，从图选出最小的连线1——4，并将加粗，表示1、4点被连接;2.再从图选出次最小的连线1——5，并将加粗，表示1、5点被连接;3.再从图选出第三最小的连线1——3，并将加粗，表示1、3点被连接，注意这里选择了连线1——3，而未选择连线4——5，是因为连线4——5与连线1——4、连线1——5构成了圈，有圈就不再是要求的树了，所以在选连线时，必须注意避免形成圈;4.再从图选出第四个最小的连线2——3，并将加粗，表示2、3点被连接,至此最小生成树图已求得，如图6-5。
其连线数一定比结点数少1。
由所求最小生成树图可知架设的电缆线总长度为54公里。
图6-4 图6-5 网络图的最小生成树算法的应用范围十分广泛，凡是各地区之间架设输电线、电缆线、输油管道、修建上下水管道等等，都可应用这个算法，从而能规划出长度最小的网络。
又如书P137习题6.6：某公司有八口海上油井，相互间距离如表所示，单位：海里。
1号井离海岸最近为4.8海里。
问：从海岸经1号井铺设油管，把各油井连接起来，应如何铺设可使管道总长度最少（为便于计量和检修，油管只准在各井位处分叉连接）？各油井间的距离（单位：海里）Array解：依题意可得最小生成树如下：§4最短路线问题下面我们用例子来介绍最短路线问题。
例1 赵某是A市一家运输公司的卡车调度员。
他的公司已经签订了一份运输合同，要把A市的一批货物运送到B市。
赵某看了这个城市之间可以选择的行车路线，并绘制了下面的公路网络。
图6-6中，圆圈也称结点，代表起点、目的地和途中要经过的其他城市。
箭线代表各城市之间的公路，每条公路上标着里程。
赵某的任务是找出从A市到B市的最短路线。
图6-6一、最短路线的手工计算方法为：1．从起点开始逐步向前推算：若经过结点2，因结点1到2只有一条路线，没有选择的余地，所以边1——2就是结点1到2的最短路线，其里程是100，将其写在结点2上方括号中。
同理，在结点3、4上方标上175和150。
2．再看结点6，因到达结点6有两条路线可以选择，若选择边2——6到达结点6，其里程是100+300=400，若选择边4——6到达结点6，其里程是150+200=350，所以从起点1到达结点6的最短路线的里程是350，将其写在结点6上方括号中。
同理，在结点5、7上方标上325和425。
3．再看结点9，因到达结点9有两条路线可以选择，若选择边6——9到达结点6，其里程是350+200=550，若选择边5——9到达结点9，其里程是325+400=725，所以从起点1到达结点9的最短路线的里程是550，将其写在结点9上方括号中。
同理，在结点8上方标上550。
4．再看结点10，因到达结点6也有两条路线可以选择，若选择边9——10到达结点10，其里程是550+100=650，若选择边9——10到达结点10，其里程是550+150=700，所以从起点1到达结点10的最短路线的里程是650，将其写在结点10上方括号中。
最后我们可以根据结点1到10的最短路线里程反向找出最短路线，见图6-7中加粗的箭线组成的路线1——4——6——9——10。
图6-7求网络图的最短路线方法可以应用于公路运输、铁路运输、电缆架设、管道铺设以及企业设备更新等方面。
二、最短路问题的应用（见书P138习题6.10）例2某人购买一台摩托车，准备在今后四年内使用。
