1
4
1-3
5
1-4-7
1-4-5-8 575 150
10
175
最短路线为650
175
200 350
425
8
225
27
3
7
图论
【例1】用Dijkstra算法求下图从v1到v6的最短路。
1-2 v2 3 v1-2-4 4 5 4 1 2 2 2 v3 1-2-3 4 4 v5 1-2-5 5 v6 1-2-5-6 7
例如
性质1：任何树至少有一个悬挂节点 性质2：具有n个顶点的树的边恰好为(n-1)条 性质3：任何具有n个顶点、(n-1)条边的连通图是树图。 树图的任意两个点之间有一条且仅有一条唯一的通路，是最脆弱 的连通图
14
图论
v4 v1
【例】树的形成
v5
v2 已知在五个城市间架设电话线，要求任何两个城市都 v3 可以通话（允许通过其它城市），并且电话线的条数最少。 方案一 v4 方案二 v4 方案三 v4 v5
v4
此为最小树杈，最小线路长度为15
24
练习：求最小树杈
5 2 2 3 3 3 2 2 3 3 4 2 2
1 2
5
25
图论
§6.3
最短线路问题
一、起点到终点的最短距离
当通过网络的各边所需时间、距离或费用为已知时，找出从入 口到出口所需的最少时间、最短距离或最少费用的路径问题，称做 网络的路线问题。 （一）狄克斯彻(Dijkstra)算法（适用于wij≥0） （二）逐次逼近算法思想（适用于有wij≤0）
5
7
8
4
12 4-6-5-7
7 6-5-7
32
答案：1-2-3-5-7或1-2-3-6-5-7路长16
图论
【例3】求5年内，哪些年初购置新设备，使5年内的总 费用最小。
第i年度 购置费 设备役龄 维修费用 1 11 0-1 5 2 11 1-2 6 3 12 2-3 8 4 12 3-4 11 5 13 4-5 18
6
5-8-10 400
200
9
400 250 8-10 150
100
1
4
275
175
5
7-8-10
10
150
3-5-8-10
600 200
最短路线为650
375
8
225
3
350
7
29
图论
【例2】
2-5-7 2-4-6-7
10
5-7
3 7
2 1-3-6-7
12 5 2
5
6 3
4-6-7
8 4
2
1 3-6-7
100 600
500
200 5
600
400
1100 1100 2 900 7
此为最小树杈，最小线路长度为2400
20
图论
避圈法(普赖姆法)
4
300 1000 100 600 200 700
6
1.供水管 道的阀门
3
500
600
5
400 1100
7
2
900
此为最小树杈，最小线路长度为2400
21
图论
2
3
1 v1 0 5
28
图论
2、从后向前推：给出了从vs到任意一个点vj的最短路。 求起点到终点的最短路线问题，可采用从终点开始逐步逆向推
算
2-6-9-10 600 300 275 200 6-9-10 300 9-10 100
2
1-4-6-9-10 650 100 150 175 4-6-9-10 500
e3
v3 e4 v4 v8 链：是一个点、边交错序列, 如（v1 ,e1 ,v2 ,e2 ,v4 ) 路：如果链中每个项点都不相同, 则称为路，如（v1 ,e1 ,v2 ,e2 ,v4 )
圈：若起始点和终点是同一个点的链称为圈。例如(v1 ,e1 ,v2 ,
e2 ,v4 ,e3 ,v3 ,e4 ,v1 ) 。
22
v1 16 v2 16 v3
30
17
41
v4
23 17 31
v5 18 v6
22
30 41
23
W23 =11+5=16
W24 =11+5+6=22
W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 35
8 2
v3
v3
破圈法
避圈法
16
图论
破圈法(克鲁斯喀尔法)
破圈法：任选一个圈，从圈中去掉杈最大的一条边。在余下的 图中重复这个步骤，直到得到一连通的不含圈的图为止。 例：已知连接五个城市的公交线路图，在要在五个城市间架设 电话线，为了便于维修要求电话线必须沿公路架设，并且电话 线总长度最小。 v 1
v1
v2 v3
v5 v1
v5
v2 v3
v1
v2 树
v3
不连通
有圈
问题：如何构建才能是最短路径的树—最小枝权树问题
15
图论
二、求最小树杈问题
最小树杈问题是关于在一个网络中，从一个起点出发 到所有点，找出一条或几条路线，以使在这样一些路线中 所采用的全部支线的总长度是最小的，或铺设费用最少。 求图的最小树杈问题的方法有“破圈法”和“避圈 法”。 v2 e6 v2 e1 e6 e4 e1 v4 e v1 e4 e3 7 v 1 v5 v4 e5 v5 e2 e e
环：如果边的两个端点相重，称该边为环，如e10；如果两个端点之 间的边多于一条, 称为具有多重边，如[v2, v4] ,无环，无多重边的图为 简单图。
6
图论
v1
e4 v3
e1
v5 e5 e3 e6
v2
e8 e9 e2
v1
v 6 e 1 e5
e2 v5 e7 e6
v2
e9
v7
e10 v6 e8
e7
v4 e10
30
v4
v3 此为最小树杈，最小线路长度为54
18
图论
【又例】
在住宅小区安装供水管道。求最小线路。
700
4 300 1.供水 管道的 阀门 100 600
6
1000 3
500 400 1100 2 900
19
200
5
600
7
图论
破圈法(克鲁斯喀尔法)
300
4 1000 3
700
6
1.供水管 道的阀门
得到第一次就座方案是（1，2，3，4，5，6，7，1），继 续寻求第二次就座方案时就不允许这些顶点之间继续相邻， 因此需要从图中删去这些边。 1 7 2 方案二：
1-3-5-7-2-4-6 3
6
5
4
11
图论
得出第二次就座方案是（1，3，5，7，2，4，6，1），那 么第三次就座方案就不允许这些顶点之间继续相邻，只能从 图中删去这些边。 1 7 2 方案三：
解：（1）分析：可行的购置方案（更新计划）是很多的， 如：1） 每年购置一台新的，则对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2）第一年购置新的，一直用到第五年年底，则总费用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。 33
图论 （2）方法：将该问题化为最短路问题，用点vi表示第i年初购买 一台新设备，并虚设点v6表示第五年年底。然后求这个赋权有 向图的最短路。 求解步骤： 1）画赋权有向图： 设 Vi 表示第i年初，（Vi ,Vj ）表示第i年初购买新设备用到 第j年初（j-1年底），而Wij 表示相应费用，则5年的一个更新计 划相当于从V1 到V6的一条路。 2）求解 （标号法）
10 25 9 15 20 30
v5
12
此为最小树杈 最小线路长度为：
v2
20+15+10+9=54
v4
17
v3
图论
避圈法(普赖姆法)
避圈法：从任意一个节点开始，选一条杈较小的边连接，以后 每一步中，总从未被选取的边中选一条杈尽可能小，且与已选
边不构成圈的边。
v1
10 25
v2
20
9
15
v5
12
2 1 2 1 C 1 E 1 3
A
2
B
D 1 F
B D
C F
E D
A
4
图论
§6.1 图的基本概念与模型
图是反映研究对象之间相互关系的一种工具。是在纸上 用点和线画出的各种各样的示意图。
张家口
承德 戊 丁
密云
怀柔 北京 通县 原平 灵丘 保定 太原 石家庄 塘沽 乙 甲
秦皇岛
丙
天津
图的最基本的要素是点以及点与点之间的一些连线，点表示我们要 研究的对象，线表示对象之间的某种特定关系。 如图中点和线赋与具体的含义和权重，称为网络图。
1-4-7-3-6-2-5 3
6
5
4
12
图论
得到第三次就座方案是（1，4，7，3，6，2，5，1），那 么第四次就座方案就不允许这些顶点之间继续相邻，只能从 图中删去这些边，只留下7点孤立点，所以该问题只有三个 1 就座方案。 7 2
6
3
5
4
13
图论
§6.2 树图和图的最小部分树
一、树的性质
树：一个无圈的连通图称为树。