1701009520
1701009521
从图8-2中可以看出，从O点出发到其他点共有6条干枝，他们的名称分别为①、②、③、④、⑤和⑥。
1701009522
1701009523
根据实际工作的经验及上述分析，在分组时应遵从以下准则。
1701009524
1701009525
准则一：尽量使同一干枝及其分枝上的点分在同一组；
1701009526
1701009527
准则二：应将相邻的干枝上的点分在同一组；
1701009528
1701009529
准则三：尽量将长的干枝与短的干枝分在同一组。
1701009530
1701009531
由上述分组准则，我们找到两种分组形式如下。
1701009532
1701009533
分组一：（⑥，①），（②，③），（⑤，④）；
1701009534
1701009535
分组二：（①，②），（③，④），（⑤，⑥）。
1701009536
1701009537
显然⑥，①相对于②，③，分配是极不均匀的，故考虑分组二。
1701009538
1701009539
对分组二中每组顶点的生成子图，用加权图G（V，E）的最佳巡视路线的近似算法求出近似最优解及相应的巡视路线。使用加权图G（V，E）的最佳巡视路线的近似算法时，在每个子图所构造的完备图中，取一个尽量包含图8-2中树上的边的H圈作为其Step 2步输入的初始圈。
1701009540
1701009541
分组二的近似解如表8-1所示。
1701009542
1701009543
表8-1 分组二的近似解（单位：km）
1701009544
1701009545
1701009546
小组名称 路线 路线长度 路线的总长度 I O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O 191.1 558.5 II O-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C-O 241.9 III O-R-29-Q-30-32-31-33-35-34-A-B-1-O 125.5 由表8-1可知，该分组的均衡度，所以此分法的均衡性很差。
1701009547
1701009548
为改善均衡性，将第Ⅱ组中的顶点C，2，3，D，4分给第Ⅲ组（顶点2为这两组的公共点），重新分组后的近似最优解如表8-2所示。
1701009549
1701009550
表8-2 重新分组后的近似最优解（单位：km）
1701009551
1701009552
1701009553
编号 路线 路线长度 路线总长度 I O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O 191.1 599.8 II O-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-O 216.4 III O-R-29-Q-30-32-31-33-35-34-A-1-B-C-3-D-4-D-3-2-O 192.3 由表8-2可知，因该分组的均衡度，所以这种分法的均衡性较好。
1701009554
1701009555
【问题】当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一定，要在24h内完成巡视，至少要分几组及最佳的巡视路线。
1701009556
1701009557
【分析】
1701009558
1701009559
由于T=2h，t=1h，V=35km/h，需访问的乡镇共有17个，村共有35个。
1701009560
1701009561
1701009562
计算出在乡（镇）及村的总停留时间为17×2+35=69h，要在24h内完成巡回，若不考虑行走时间，有（i为分的组数），得i最小为4，故至少要分4组。
1701009563
1701009564
1701009565
1701009566
1701009567
由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为，则每组分配在路途上的时间大约为24-17.25=6.75h。而前面讨论过，分3组时有个总路程599.8km的巡视路线，分4组时的总路程不会比599.8km大太多，不妨以599.8km来计算。路上时间约为，若平均分配给4个组，每个组约需，故分成4组是可能办到的。
1701009568
1701009569
现在尝试将顶点分为4组。