4-7-西 7
1
4
4
2 东-1-4-7-西
12
2-5-7-西 15
7 5-7-西 10 7
东
3
5
2
7 3-6-8-西
14 4
3
3
5
6
6-8-西 11 4 6
Page 13
7-西 3
7 3
8-西
西
7 77
8
【解析】从终点逆向标到起点即可 说明：方框中的数字代表改点到终点最短距离；方框上的标 示从改点到终点最短路线的走法。
1000辆/小时计算），求从A到F的最大车流量及安排。
Page 21
解：A-B-D-F连线上最小流量为4，A-C-E-F连线上最小流量为2;A-C-D-E-F 连线上最小流量为1,A-B-C-D-E-F连线上最小流量为1，总流量是4+2+1+1=8 ，即8000辆/小时。最大流量问题，就是在一定条件下，要求流过网络的流 量为最大的问题，路线的选择顺序不唯一，单不管哪种选择最终的总流量是 相等的。
【答案】第一条路：1—2—4—6 流量为5吨 第二条路：1—3—4—6 流量为2吨 第三条路：1—3—5—6 流量为6吨
所以最大流量为5+2+6=13吨。 【解析】路线的选择顺序不唯一，但不管哪种选择最终的总 流量是相等的。
如下图所示为4座城市及其公路连接情况，线上数字是相邻城市 每个小时最多可以通行的车辆数，以1000辆为1个计量单位P，age试19 求出从第一个城市到第四个城市的最大流量及安排
Page 1
第八章 图论方法
复习建议
Page 2
本章在历年考试中，处于相当重要的地位，建议学员全面掌 握,重点复习。从题型来讲包括单项选择题、填空题、名词 解释和计算题题型都要加以练习。
重要考点：树、最小枝杈树、最短路线、最大流量等。
8.1图的基本概念
有向图
VPage 3
1、图的基本要素：结点、边。
2.（10年4月）某工程埋设电缆，将中央控制室W与6个控制点相连通，各控制 点位置及距离（公里）如图。如何埋设可使电缆总长最短？求出最短P距age离1。0
8.4 最短路线问题
Page 11
最短路线问题为当通过网络的各边所需要的时间、距 离或费用已知时，寻求两点间的距离最短或费用最少的路性 问题。 采用的方法为逆向推算法。
Page 6
4、克鲁斯喀尔法（又称避圈法） （1）每次选择剩余边中长度最小的 （2）后选的边与已经选好的边不能构成回路，若构成则舍弃 （3）重复（1）（2），直到把所有边选完。
Page 7
【例题·计算题】某自来水公司欲在某地区各高层住宅楼间 敷设自来水管道并与主管道相连。其位置如下图，节点代表 各住宅楼和主管道位置，线上数字代表两节点间距离（单位： 百米）。如何敷设才能使所用管道最少？
V4
2、有向图：所有边都带方向。
1
V
V
3、无向图：所有边都没有方向。
3
2
4、连通图：所有结点都连接起来，没有孤
立点的图。
5、不连通图：有孤立点的图。
6、权：赋给结点或边的信息。
7、回路（圈）：从一点出发，还能回到原 点的一条路。
8.2 树和树的逐步生成法
Page 4
1、树：连通且不含圈（回路）的图称为树。 2、树的边数=结点数-1。
9
2
3

7
3.5
4
6
10
1
6
4
3
8
2
5
【答案】
2 5
4
6
1
3
5
3 3.5 4
2
Page 8
【解析】按照克鲁斯喀尔的算法很轻松得出答案。
1.（11年7月）已知连接5个城镇的公路交通图如图。为了沿公路架设5个城镇的
光缆线，并要求光缆线架设的总长度为最小，试以最小枝杈树方法求出Pa最ge优9 方 案并计算光缆线的总长度。
解：从1到4总共有3条可行方案，分别是1-2-4，1-3-4,1-2-3-4， 每条路线的流量分别为6000辆/小时、 12 000辆/小时、 2 000辆/ 小时，因此1到4总安排为6000+12000+2000=20 000辆/小时。
Page 20
下图是六个城市之间的公路连接情况，线旁的数字表示公路的车流量（以
路的交通状况相同，请为该公司寻求一条最佳路线。
8.5 最大流量问题
Page 17
最大流量问题，就是在一定条件下，要求流过网络的流
量为最大的问题。
【例题·计算题】某网络如图，线上标注的数字是单位时间
通过两节点的流量。试求单位时间由网络始点到网络终点的
最大流量（单位：吨）。
2
4
1
6
3
5
Page 18
3.（11年4月）电信公司准备在甲、乙两地之间沿公路架设光缆 ，图给出了两地间的公路交通图，其中，V1表示甲地，VP7a表ge 示14 乙地，点与点之间的连线（边）表示公路，边上的数值表示两 地间公路长度（km）。问如何选择架设线路可使光缆架设距离 为最短？最短距离是多少？
Page 15
4.（07年4月）城市A到城市B的交通道路如题图所示，线上标注的数字为两点 间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设Pa各ge 条16线
Page 12
【例题·计算题】某城市东到西的交通道路如下图所示，线 上标注的数字为两点间距离(单位：千米)。某公司现需从市 东紧急运送一批货物到市西。假设各条线路的交通状况相同， 请为该公司寻求一条最佳路线。
2 东3
4
3 1
7
2
5
7
3
3
4
4
7 5
6
4 6
7 3
7
西
8
【答案】
1-4-7-西 10 3
Page 22
5.（09年7月）某网络如图，线上标注的数字是单位时间通过两节点的流量。
Page 23
试求单位时间由网络始点到网络终点的最大流量（单位：吨）。
Page 24
Page 25
6.（08年7月）如题图所示，圆圈代表网络节点，节点间的连线表示它们间有网线
【选择题】以下叙述中，正确的是（ ） A．树的点数为线数加1 B．图的点数小于线数 C．图的点数大于线数 D．树可能含有圈 【答案】A 【解析】树的点数和边数差1，普通图的点数和边数谁多谁少不 确定。 【知识点】图和树的基本概念
8.3 最小枝杈树问题
Page 5
1、最小枝杈树问题是关于在一个网络中，从一个起点出 发到所有点，找出一条或几条路线，以使在这样一些线 路中所采用的全部支线的总长度是最小的。 2、常用方法：普莱姆法或克鲁斯喀尔法。 教材中介绍的是普莱姆法，在做题过程中不如克鲁斯喀 尔法简单，因此我们重点讲解克鲁斯喀尔法。 3、最小枝杈树问题主要应用于管道、电话线、电线、网 线等线路铺设中。