防疫站问题

首先证明没有建防疫站的城镇只和一个建防疫站的城镇相连，假设存在一个城镇Ai有至少两条路连到两个城镇,若两个城镇都无防疫站，则与题目条件矛盾，因而至少有一个城镇建有防疫站。因此只需保留Ai到建有防疫站的那个城镇的路而删去其他路，这样建一条路的花费显然小于两条及两条以上路的花费。由此证明上述命题。 再证明建了防疫站的城镇之间没有路相连，假设原来两个都建了防疫站的城镇之间有路相连，而若删去这些路，依然满足题目条件，且此公路花费明显小于原来两者建有公路的方案。因此证明建有防疫站的城镇之间没有路相连。 既然已建防疫站之间的城镇之间不能有道路连接，我们可以假想一个新节点X，让所有城镇到该点X的边的权为建防疫站的费用。有了X，所有建防疫站的地方都相通，且其他所有未建防疫站的地方与建防疫站的地方相通，因此最后所求图为连通图。而且没有X前，每个未建防疫站的地方有且只有一条路相通，而建防疫站的城镇之间无路相连，设建了y个防疫站，那么边的个数为（N-y）。多了节点X后，边的个数增加了y个，因而边数q=N。而顶点数为（N+1）个，符合q=p-1的关系。根据定理3.1.2，可证我们所求的图为树。而我们要的是总费用的最小值，即所有边权的最小值，那么这道题的目标也就是说要求解包含X的最小生成树，且X的度不应超过P。 可以用有条件限制的Prim算法来求解该题的最小生成树，步骤如下：设图G=（V, E），其生成数的顶点为U。首先，以节点X为初始点，放入U。第二步，在所有u属于X或与X有直接边相连的点，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。第三步，把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。同时，在找最小权值得过程中，要注意不能使X的度超过P，并且由于要求城镇要直接连到建有防疫站的城镇，所以只能以X或与X直接相接的点出发连线，并在其中寻找权最小的点。易得，该算法的复杂性为O（v2），为有效算法。而求得的最小生成数图中与X直接相连即为应当建防疫站的地方，最小生成树的权即为最少的花费。 以图为例,假设存在5个城镇，XAi的权代该城镇的建防疫站的花费，AiAj的权代表两个城镇间建公路的花费，假设最多有3个城镇建防疫站。 1.首先以X为初始点，可见X到A2的边地的权最小，得 2.可见，可以以X或A2为起始点，取A1A2为端点权为2的边，因为它在所有以X和A2为端点的边中权最小。 3.以X或A2为起始点，可取XA3或A2A3，假设取XA3。 4.继续上过程，在这一过程中要始终以X或与X有边相连的点出发连线。 从最后得到的最小生成树可知，与X直接相连的A2、A3应当建防疫站，A1、A4应与A2建道路，A5应与A3建道路，X的度数不超过3，符合条件，因而最小花费为13。 X A2 A2 X A1 A1 X A2 A3 2 2 2 2 2 3 3 2 2 A3 A5 X A2 2 4 2 3 2 2 A3 A1 X A2 A1 A5 A4