第二讲 图论模型 1. 问题引入与分析 2. 图论的基本概念 3. 最短路问题及算法 4. 最小生成树及算法 5. 旅行售货员问题

Presentation on theme: "第二讲 图论模型 1. 问题引入与分析 2. 图论的基本概念 3. 最短路问题及算法 4. 最小生成树及算法 5. 旅行售货员问题"— Presentation transcript:

1 第二讲 图论模型 1. 问题引入与分析 2. 图论的基本概念 3. 最短路问题及算法 4. 最小生成树及算法 5. 旅行售货员问题
第二讲 图论模型 1. 问题引入与分析 2. 图论的基本概念 3. 最短路问题及算法 4. 最小生成树及算法 5. 旅行售货员问题 6. 模型建立与求解

2 1. 问题引入与分析 1) 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的：
今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视. 巡视路线指从县政府 所在地出发，走遍各乡（镇）、村，又回到县政 府所在地的路线.

3 1）若分三组（路）巡视，试设计总路程最 短且各组尽可能均衡的巡视路线. 2）假定巡视人员在各乡（镇）停留时间T=2 小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分 几组；给出这种分组下最佳的巡视路线.

4 公路边的数字为该路段的公里数.

5 2) 问题分析： 本题给出了某县的公路网络图，要求的是在不 同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡 镇、村之间的公路看作此图对应顶点间的边，各条 公路的长度（或行驶时间）看作对应边上的权，所 给公路网就转化为加权网络图，问题就转化图论中 一类称之为旅行售货员问题，即在给定的加权网络 图中寻找从给定点O出发，行遍所有顶点至少一次 再回到点O，使得总权（路程或时间）最小.

6 本题是旅行售货员问题的延伸 －多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是m条 经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链（闭迹）. 　 如第一问是三个旅行售货员问题，第二问是四 个旅行售货员问题. 　　众所周知，旅行售货员问题属于NP完全问题， 即求解没有多项式时间算法. 　　显然本问题更应属于NP完全问题. 有鉴于此， 一定要针对问题的实际特点寻找简便方法，想找到 解决此类问题的一般方法是不现实的，对于规模较大 的问题可使用近似算法来求得近似最优解.

7 2.图论的基本概念 1) 图的概念 2) 赋权图与子图 3) 图的矩阵表示 4) 图的顶点度 5) 路和连通

8 1) 图的概念 定义 一个图G是指一个二元组(V(G),E(G))，其中: 是非空有限集，称为顶点集， 1) 其中元素称为图G的顶点.
2) E(G)是顶点集V(G)中的无序或有序的元素偶对 组成的集合，即称为边集,其中元素称为边. 定义 图G的阶是指图的顶点数|V(G)|, 用 来表示； 图的边的数目|E(G)|用 来表示. 表示图，简记 用 也用 来表示边

9 定义 若一个图的顶点集和边集都是有限集，则称
其为有限图. 只有一个顶点的图称为平凡图，其他的 所有图都称为非平凡图.

10 若图G中的边均为无序偶对 ，称G为无向图.称
图. 称边 为有向边或弧,称 是从 连接 ，称 为e的尾，称 为e的头. 若图G中的边均为无序偶对 ，称G为无向图.称 边 为无向边，称e连接 和 ，顶点 和 称 为e的端点. 既有无向边又有有向边的图称为混合图.

11 常用术语 1) 边和它的两端点称为互相关联. 2)与同一条边关联的两个端点称 为相邻的顶点，与同一个顶点 点关联的两条边称为相邻的边. 3) 端点重合为一点的边称为环， 端点不相同的边称为连杆. 4) 若一对顶点之间有两条以上的边联结，则这些边 称为重边． 5) 既没有环也没有重边的图，称为简单图．

12 6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv.
常用术语 6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv. 7) 若 ， ，且X 中任意两顶点不 相邻，Y 中任意两顶点不相邻，则称为二部图或 偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为 完全二部图或完全偶图,记为 (m=|X|,n=|Y|)． ， 8) 图 叫做星. 二部图

13 2) 赋权图与子图 定义 若图 的每一条边e 都赋以 一个实数w(e)，称w(e)为边e的权，G 连同边上的权 称为赋权图. 定义 设 和 是两个图. 1) 若 ,称 是 的一个子图,记 2) 若 ， ，则称 是 的生成子图. 3) 若 ，且 ，以 为顶点集，以两端点 均在 中的边的全体为边集的图 的子图，称 为 的由 导出的子图，记为 4) 若 ，且 ，以 为边集，以 的端点 集为顶点集的图 的子图，称为 的由 导出的 边导出的子图，记为

14 3) 若 ，且 ，以 为顶点集，以两端点 均在 中的边的全体为边集的图 的子图，称 为 的由 导出的子图，记为 4) 若 ，且 ，以 为边集，以 的端点 集为顶点集的图 的子图，称为 的由 导出的 边导出的子图，记为

15 3) 图的矩阵表示 邻接矩阵: (以下均假设图为简单图). 1) 对无向图 ，其邻接矩阵 ，其中：

16 2) 对有向图 ,其邻接矩阵 ,其中：

17 3) 对有向赋权图 , 其邻接矩阵 , 其中： 对于无向赋权图的邻接矩阵可类似定义.

18 关联矩阵 1) 对无向图 ，其关联矩阵 , 其中：

19 2) 对有向图 ，其关联矩阵 , 其中：

20 4) 图的顶点度 定义 1) 在无向图G中，与顶点v关联的边的数目(环 算两次),称为顶点v的度或次数，记为d(v)或 dG(v). 称度为奇数的顶点为奇点，度为偶数的顶点为偶点. 2) 在有向图中，从顶点v引出的边的数目称为顶点 v的出度，记为d+(v)，从顶点v引入的边的数目称为 v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数． 定理 推论 任何图中奇点 的个数为偶数．

21 5) 路和连通 定义1) 无向图G的一条途径（或通道或链）是指 一个有限非空序列 ，它的项交替 地为顶点和边，使得对 ， 的端点是 和 , 称W是从 到 的一条途径，或一条 途径. 整 数k称为W的长. 顶点 和 分别称为的起点和终点 , 而 称为W的内部顶点. 2) 若途径W的边互不相同但顶点可重复，则称W 为迹或简单链. 3) 若途径W的顶点和边均互不相同，则称W为路 或路径. 一条起点为 ,终点为 的路称为 　 　路 记为

22 定义 1) 途径 中由相继项构成子序列 称为途径W的节. 2) 起点与终点重合的途径称为闭途径. 3) 起点与终点重合的的路称为圈(或回路)，长 为k的圈称为k阶圈，记为Ck. 4) 若在图G中存在(u,v)路，则称顶点u和v在图G 中连通. 5) 若在图G中顶点u和v是连通的，则顶点u和v之 之间的距离d(u,v)是指图G中最短(u,v)路的长；若没 没有路连接u和v，则定义为无穷大.

23 6) 图G中任意两点皆连通的图称为连通图． 7) 对于有向图G，若 ，且 有 头 和尾 ，则称W为有向途径. 类似地，可定义有向迹，有向路和有向圈. 例 在右图中： 途径或链： 迹或简单链： 路或路径： 圈或回路：

24 3．最短路问题及算法 最短路问题是图论应用的基本问题，很多实际 问题，如线路的布设、运输安排、运输网络最小费
用流等问题,都可通过建立最短路问题模型来求解. 最短路的定义 最短路问题的两种方法：Dijkstra和Floyd算法 . 1) 求赋权图中从给定点到其余顶点的最短路. 2) 求赋权图中任意两点间的最短路.

25 定义 1) 若H是赋权图G的一个子图，则称H的各
若P(u,v)是赋权图G中从u到v的路,称 称为路P的权． 2) 在赋权图G中，从顶点u到顶点v的具有最小权 的路P*(u,v)，称为u到v的最短路． 3) 把赋权图G中一条路的权称为它的长，把(u,v) 路的最小权称为u和v之间的距离，并记作 d(u,v).

26 1) 赋权图中从给定点到其余顶点的最短路 最短路是一条路，且最短路的任一节也是最短路． 求下面赋权图中顶点u0到其余顶点的最短路．
假设G为赋权有向图或无向图，G边上的权均非 负．若 ，则规定

27 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

28 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

29 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

30 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

31 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

32 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

33 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

34 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

35 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

36 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

37 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

38 Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
1) 置 ，对 ， ， 且 2) 对每个 ，用 代替 ，计算 ，并把达到这个最小值的 一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代 替i，并转2).

39

40 定义 根据顶点v的标号l(v)的取值途径，使 到v
的最短路中与v相邻的前一个顶点w，称为v的先驱 点，记为z(v), 即z(v)=w. 先驱点可用于追踪最短路径. 例5的标号过程也 可按如下方式进行： 首先写出左图带权邻接矩阵 因G是无向图，故W是对称阵．

41

42

43 备用-将求最短路与最短路径结合起来: Dijkstra算法：求G中从顶点u0到其余顶点的最短路
设G为赋权有向图或无向图，G边上的权均均非负. 对每个顶点，定义两个标记（l(v)，z(v)），其中: l(v) ：表从顶点u0到v的一条路的权． z(v) ：v的先驱点，用以确定最短路的路线. 算法的过程就是在每一步改进这两个标记，使最终 l(v)为从顶点u0到v的最短路的权． S：具有永久标号的顶点集. 输入: G的带权邻接矩阵 w(u,v)

44 l(v) u0 v l(u) u w(u,v) 算法步骤：

45 例 求下图从顶点u0到其余顶点的最短路． 首先写出带权邻接矩阵 因G是无向图，故W是对称阵．

46

47 见Matlab程序-Dijkstra.doc

48 2) 求赋权图中任意两顶点间的最短路 算法的基本思想 （I）求距离矩阵的方法. （II）求路径矩阵的方法. （III）查找最短路路径的方法.
Floyd算法：求任意两顶点间的最短路. 举例说明

49 算法的基本思想

50 （I）求距离矩阵的方法.

51 （II）求路径矩阵的方法. 在建立距离矩阵的同时可建立路径矩阵R．

52 （III）查找最短路路径的方法. 然后用同样的方法再分头查找．若：

53 （IV）Floyd算法：求任意两顶点间的最短路.

54 例 求下图中加权图的任意两点间的距离与路径.

55 插入点 v1，得： 矩阵中带“=”的项为经迭代比较以后有变化的元素.

56 插入点 v2，得： 矩阵中带“=”的项为经迭代比较以后有变化的元素.

57 插入点 v3，得：

58 插入点 v4，得： 插入点 v5，得：

59 插入点 v6，得：

60 故从v5到v2的最短路为8 由v6向v5追溯: 由v6向v2追溯: 所以从到的最短路径为： 见Matlab程序-Floyd.doc

61 4．最小生成树及算法 1) 树的定义与树的特征 定义 连通且不含圈的无向图称为树．常用T表示.
树中的边称为树枝. 树中度为1的顶点称为树叶. 孤立顶点称为平凡树. 平凡树

62 定理2 设G是具有n个顶点的图，则下述命题等价：
1) G是树（ G无圈且连通）； 2) G无圈，且有n-1条边； 3) G连通，且有n-1条边； 4) G无圈，但添加任一条新边恰好产生一个圈; 5) G连通，且删去一条边就不连通了（即G为最 最小连通图）； 6) G中任意两顶点间有唯一一条路.

63 2）图的生成树 定义 若T是包含图G的全部顶点的子图,它又是树, 则称T是G的生成树. 图G中不在生成树的边叫做弦. 定理3 图G=(V,E)有生成树的充要条件是图G是连 通的. 证明 必要性是显然的.

64

65 （II）找图中生成树的方法 可分为两种：避圈法和破圈法 A 避圈法 : 深探法和广探法 B 破圈法

66 A 避圈法 定理3的充分性的证明提供了一种构造图的生 成树的方法. 这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法” 在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.

67 若这样的边的另一端均已有标号，就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.
a) 深探法 例用深探法求出下图10的一棵生成树 步骤如下： 图10 i) 在点集V中任取一点u, 给以标号0. ii) 若某点v已得标号，检 查一端点为v的各边，另一 1 2 8 7 端是否均已标号. 10 11 若有边vw之w未标号,则给 3 13 12 9 w以标号i+1，记下边vw.令 6 5 4 w代v，重复ii). 若这样的边的另一端均已有标号，就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.

68 若这样的边的另一端均已有标号，就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.
a) 深探法 例用深探法求出下图10的一棵生成树 步骤如下： 图10 i) 在点集V中任取一点u, 给u以标号0. ii) 若某点v已得标号，检 查一端点为v的各边，另一 1 2 8 7 端是否均已标号. 若有边vw之w未标号,则给 10 11 3 13 12 9 w以标号i+1，记下边vw.令 6 5 4 w代v，重复ii). 若这样的边的另一端均已有标号，就退到标号为 i-1的r点,以r代v,重复ii),直到全部点得到标号为止.

69 b)广探法 例用广探法求出下图10的一棵生成树 步骤如下： i) 在点集V中任取一点u, 给u以标号0. ii) 令所有标号i的点集为
Vi,检查[Vi,V\Vi]中的边端点 1 1 2 图10 是否均已标号. 对所有未标 3 1 2 2 号之点均标以i+1,记下这些 3 4 2 边. 3 1 2 iii) 对标号i+1的点重复步 步骤ii)，直到全部点得到 标号为止.

70 b)广探法 例用广探法求出下图10的一棵生成树 步骤如下： i) 在点集V中任取一点u, 给u以标号0. ii) 令所有标号i的点集为
Vi,检查[Vi,V\Vi]中的边端点 1 1 2 是否均已标号. 对所有未标 3 1 2 2 号之点均标以i+1,记下这些 3 4 2 边. 3 1 2 iii) 对标号i+1的点重复步 显然图10的生成树 不唯一. 步骤ii)，直到全部点得到 标号为止.

71 B 破圈法 相对于避圈法，还有一种求生成树的方法叫做“破圈法”. 这种方法就是在图G中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止. 例 用破圈法求出 下图的一棵生成树.

72 B 破圈法 例 用破圈法求出下图的另一棵生成树. 不难发现，图的生成树不是唯一的 .

73 3) 最小生成树与算法 介绍最小树的两种算法： Kruskal算法（或避圈法）和破圈法.

74 A Kruskal算法（或避圈法） 步骤如下： 1) 选择边e1，使得w(e1)尽可能小； 2) 若已选定边 ，则从 中选取 ，使得: i) 为无圈图， ii) 是满足i)的尽可能小的权， 3) 当第2)步不能继续执行时，则停止. 定理4 由Kruskal算法构作的任何生成树 都是最小树.

75 例10用Kruskal算法求下图的最小树. 在左图中 权值 最小的边有 任取一条 在 中选取权值 最小的边 中权值最小边有 , 从中选 任取一条边 中选取在中选取 中选取 但 与 都 会与已选边构成圈,故停止,得

76 B破圈法 例11用破圈法求下图的最小树. 算法2 步骤如下： 1) 从图G中任选一棵树T1. 2) 加上一条弦e1，T1+e1中 立即生成一个圈. 去掉此 圈中最大权边，得到新 树T2,以T2代T1,重复2)再 检查剩余的弦，直到全 部弦检查完毕为止. 再加上弦e7，得到圈 v4v5v2v4, 先求出上图的一棵生成树. 加以弦 e2,得到的圈v1v3v2v1, 去掉最大的权边e6，得到一棵 去掉最大的权边e2,得到一棵新 新树；如此重复进行，直到全 树仍是原来的树； 全部的弦均已试过,得最小树.

77 5. 旅行售货员问题 定义设G=(V,E)是连通无向图，包含图G的每个 顶点的路称为G的哈密尔顿路(Hamilton路或H路).
含Hamilton圈的图称为哈密尔顿图(或Hamilton 图或H图).

78 旅行售货员问题或货郎担问题. 一个旅行售货员想去访问若干城镇，然后回 到出发地.给定各城镇之间的距离后，应怎样计划 他的旅行路线，使他能对每个城镇恰好经过一次 而总距离最小？ 它可归结为这样的图论问题：在一个赋权完 全图中,找出一个最小权的H圈,称这种圈为最优圈. 但这个问题是NP-hard问题，即不存在多项式 时间算法.也就是说,对于大型网络(赋权图),目前还 没有一个求解旅行售货员问题的有效算法，因此 只能找一种求出相当好（不一定最优）的解.

79 一个可行的办法 : 是先求一个H圈,然后适当 修改,以得到具有较小权的另 一个H圈.

80 定义 若对于某一对i和j，有 则圈Cij将是圈C的一个改进. 二边逐次修正法: 在接连进行一系列修改之后,最后得一个圈,不能 再用此方法改进了，这个最后的圈可能不是最优的, 但是它是比较好的，为了得到更高的精度，这个 程序可以重复几次，每次都以不同的圈开始. 这种 方法叫做二边逐次修正法.

81 例对下图16的K6,用二边逐次修正法求较优H圈. 较优H圈: 其权为W(C3)=192

82 分析: 找出的这个解的好坏可用最优H圈的权
的下界与其比较而得出.即利用最小生成树可得最 优H圈的一个下界，方法如下： 设C是G的一个最优H圈，则对G的任一顶点v, C-v是G-v的路，也G-v是的生成树.如果T是G-v的 最小生成树,且e1是e2与v关联的边中权最小的两条 边,则w(T)+w(e1)+w(e2)将是w(C)的一个下界. 取v=v3,得G-v3的一 最小生成树(实线),其 权w(T)=122,与v3关联 的权最小的两条边为 v1v3和v2v3,故w(C) w(T)+w(v1v3)+w(v2v3) =178.故最优H圈的权 应满足178 w(C)

83 6. 最佳灾情巡视路线的模型的建立与求解 问题转化为在 给定的加权网 络图中寻找从 给定点O出发, 行遍所有顶点 至少一次再回
总权(路程或时 时间)最小,即 最佳旅行售货 员问题.

84 因二边逐次修正法的结果与初始圈有关,故本算法
最佳旅行售货员问题是NP—完全问题,采用一种 第2)，3)，4)步分别用三种方法产生初始圈，以保 近似算法求其一个近似最优解，来代替最优解. 证能得到较优的计算结果. 算法一 求加权图的最佳旅行售货员回路近似算法: 1) 用图论软件包求出G中任意两个顶点间的最短路, 构造出完全图 2) 输入图 的一个初始H圈； 3) 用对角线完全算法（见[3]）产生一个初始圈; 4) 随机搜索出 中若干个H圈，例如2000个； 5) 对第2)，3)，4)步所得的每个H圈，用二边逐次 修正法进行优化，得到近似最优H圈； 6) 在第5)步求出的所有H圈中，找出权最小的一个, 此即要找的最优H圈的近似解.

85 问题一 若分为三组巡视，设计总路程最短且各
组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题. 4)

86 此问题包含两方面：a)对顶点分组, b)在每组中
求(单个售货员)最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存 故多 也不 存在多项式时间内的精确算法.

87 而图中节点数较多，为53个，我们只能去寻求 一种较合理的划分准则，对图1进行粗步划分后,求 出各部分的近似最佳旅行售货员回路的权,再进一 进一步进行调整，使得各部分满足均衡性条件3). 从O点出发去其它点，要使路程较小应尽量走 O点到该点的最短路. 故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树. 将从O点出发的树枝称为干枝.

88 由上述分组准则，我们找到两种分组形式如下：
准则1 尽量使同一干枝上及其分枝上的点分在同一组. 在分组时应遵从准则： 从O点出发到其它点共有6条干枝，它们的名称 分组1:（⑥，①），（②，③），（⑤，④） 准则2 应将相邻的干枝上的点分在同一组； 分别为①，②，③，④，⑤，⑥. 分组2:（①，②），（③，④），（⑤，⑥） 准则3 尽量将长的干枝与短的干枝分在同一组. 分组1极不均衡,故考虑分组2.

89 分组2:(①,②),(③,④),(⑤,⑥) 对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线. 在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈.

90 分组2的近似解

91 分给第Ⅲ组（顶点2为这两组的公共点），重新分
因为该分组的均衡度 . 所以此分法的均衡性很差. 为改善均衡性，将第Ⅱ组中的顶点C,2,3,D,4 分给第Ⅲ组（顶点2为这两组的公共点），重新分 分组后的近似最优解见表2.

92

93 因该分组的均衡度 所以这种分法的均衡性较好. 问题二 当巡视人员在各乡（镇）、村的停留 停留时间一定,汽车的行驶速度一定,要在24小时内 完成巡视,至少要分几组及最佳旅行的巡视路线.

94 由于T=2小时,t=1小时,V=35公里/小时,需访问
的乡镇共有17个，村共有35个. 计算出在乡(镇)及 村的总停留时间为 =69小时，要在24小时 内完成巡回，若不考虑行走时间，有: 69/i<24(i为 分的组数). 得i最小为4，故至少要分4组. 由于该网络的乡(镇)、村分布较为均匀,故有可 能找出停留时间尽量均衡的分组,当分4组时各组停 停留时间大约为69/4=17.25小时，则每组分配在路 路途上的时间大约为 =6.75小时.而前面讨 论过,分三组时有个总路程599.8公里的巡视路线， 分4组时的总路程不会比599.8公里大太多,不妨以 599.8公里来计算.路上约用599.8/35=17小时,若平 均分配给4个组,每个组约需17/4=4.25小时<6.75小 小时,故分成4组是可能办到的.

95 现在尝试将顶点分为4组.分组的原则：除遵从 前面准则1、2、3外，还应遵从以下准则： 准则4 尽量使各组的停留时间相等. 用上述原则在下图上将图分为4组，同时计算 各组的停留时间,然后用算法一算出各组的近似最 最佳旅行售货员巡回，得出路线长度及行走时间, 从而得出完成巡视的近似最佳时间. 用算法一计 计算时，初始圈的输入与分三组时同样处理. 这4组的近似最优解见表3.

96

97 表3符号说明：加有底纹的表示前面经过并停留过,
此次只经过不停留;加框的表示此点只经过不停留. 该分组实际均衡度 % 可看出,表3分组的均衡度很好,且完全满足24 小时完成巡视的要求.

98 再见