1基本概念及定理[1]

定义1:设V是顶点集,E是边集,如果对每个e∈E,有V中一个顶点对(u,v)和它对应,则称V及E组成的集为一个线图,记为G=(V,E)。顶点u及v称为边e的端点,并称u及v相邻。若线图G中任两个顶点之间都有通路,则称G是连通的。定义2:设G1=(V1,E1)和G=(V,E)为两个线图,如果V1V且E1E,则称G1为G的子图。定义3:设线图G连通且有n个顶点,若T是G的一个有n个顶点和n-1条边的连通子图,则称T为G的一棵树。设线图G连通,若对它的每一边eij=(vi,vj)赋以实数wij=w(eij),则称G为赋权图,实数wij表示边eij上的权。在实际问题中,wij可以代表距离、运费、造价等。定义4:设I是G的一个顶点子集,如果G中每一条边至少有一个端点在I中,则称I为G的一个点覆盖。顶点数最少的点覆盖为最小点覆盖。若对点覆盖I中任一顶点x,I\(x)都不是点覆盖,则说I为极小点覆盖。显然,最小点覆盖一定是极小点覆盖。定义5:设K是G的一个顶点子集,如果K中任何两个顶点在G中都不邻接,则称K为G的独立集。顶点数最多的独立集为最大独立集。设K为G的独立集,若对G中任何异于K的独立集K′,均有|K′|≤|K|,则说K是极大独立集。定理1:设KV,则K是G的极大独立集V\K是G的极小点覆盖。

2最小造价问题

在一个地区或一个国家的地图上,都画有连接各城镇之间的一个铁路网或公路网。已知城市vi和vj间的直通线路的造价为wij=w(eij),要求给出一个总造价为最小的设计方案。又如一个城镇中,对若干新建居民点供应自来水和煤气,已知连接各点间的直通管道的造价,要求给出一个造价最小的铺设方案。寻求这样的设计方案在农业科学建设中有着重要的经济价值,而解决这些实际问题可以归结为图论中连通赋权图的最优树问题。文献[2]中给出了克鲁斯克尔算法,该算法由3步组成:(1)在G的边集E中选取边e1,使w(e1)最小。(2)设已选好了边e1,e2,…,ek,则从E-{e1,e2,…,ek}中选取ek+1,使(1)导出子图G[{e1,e2,…,ek+1}]无回路;(2)w(ek+1)是满足(1)的尽可能小的权。(3)当第(2)步不能继续进行时,则停止。可以证明,由克鲁斯克尔算法构造出的树是连通赋权图G的一棵最优树。例如所示赋权图表示某7个城市v1,v2,…,v7及预先测算出的它们之间的一些直接通信线路的造价。试给出一个既使各城市之间能够通信又使总造价为最小的设计方案。显然,所求即为连通赋权图的具有最小权的一棵树—最优树。利用克鲁斯克尔算法,第一步,选e1=(v1,v7),w(e1)=1;第二步,选e2=(v3,v4),w(e2)=3;第三步,选e3=(v2,v7),w(e3)=4;第四步,选e4=(v3,v7),w(e4)=9;第五步,本该选权为15的边(v2,v3)作为e5,但它与已选的e3,e4构成回路,故舍去;当改选权为16的边(v4,v7)时,同样因它与已选的e2,e4构成回路,再次舍去,从而选取e5=(v4,v5),w(e5)=17;依次选下去,最后选e6=(v1,v6),w(e6)=23。此时7个城市均已相通且无回路,算法终止。于是由e1、e2、e3、e4、e5和e6所构成的树()即给出所需要的总造价最小的设计方案,其总造价为57。

3收银台的设置问题

许多大型商场为加强经营管理,对商品的零售收入实行统一收款制度。为了使顾客在任何一个货架前都能看到收银台,则收银台应设置在什么位置并且至少要设置多少个收银台。构作线图G=(V,E)。该商场两排货架之间的通道为G的边,通道交叉处为G的顶点。为使顾客在任何一个货架前都能看到收银台,从尽可能减少设置收银台的数目来说,收银台应设置在通道的交叉处。于是收银台的设置问题就归结为在G中找出一个最小点覆盖。由于最小点覆盖必是极小点覆盖,所以,只需确定G的所有极小点覆盖。文献[3]中介绍了枚举法,由定理1,V的子集K是G的极小点覆盖V\K是G的极大独立集对每个x∈V,要么选择x∈K,要么选择NG(x)K(但两者不能同时成立)。这里NG(x)表示在G中与顶点x相邻的点的集合。这个事实提供了一个求极小点覆盖的方法:对每个x∈V,要么选择x,要么选择NG(x)。为了有效地执行该程序,引入下列逻辑运算:设x、y、z是3条指令,定义x+y为“要么执行x,要么执行y”;xy为“同时执行x和y”。容易验证这2个逻辑运算满足交换律、结合律、分配律、吸收律(x+x=x,xx=x,x+xy=x)。根据上述定义的逻辑运算和求极小点覆盖的程序,顶点集为{v1,v2,…,vn}的线图G的所有极小点覆盖可表示为C(v1,v2,…,vn)=∏ni=1(xi+∏y∈N(xi)y)。最后比较所有求出的极小点覆盖,找出G中一个最小点覆盖即可。