§1、消防设施与监狱看守.ppt

《§1、消防设施与监狱看守.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、消防设施与监狱看守若干条街道构成居民小区如图所示，e1,e2,…,e7表示街道，v1,v2,…,v5表示交叉路口。现计划在某些路口安置消防设施，只有与路口直接相连的街道才能使用它们。为使所有街道必要时都有消防设施可用，在哪些路口安置设施才最节省呢？。问题一座监狱的几间牢室有道路相连，亦为上图所示，v1,v2,…,v5表示牢室，e1,e2,…,e7表示道路。监狱看守要设在通过道路能直接监视所有牢室的地方，如果看守不得走动，那么他们应呆在某些牢室（即路口）所在地．问至少需要几名看守才能完成监视任务呢？图的几个基本概念以上图为例叙述图是由顶点集V=(v1,v2,…,v5),边集E=

2、(e1,e2,…,e7)以及各个顶点和各边之间确定的关联关系Ψ组成的一种结构，记作图G=(V,E,Ψ)。其中Ψ(e1)=v1v2，Ψ(e2)=v2v3,…,Ψ(e7)=v4v5，v1，v2是e1的端点，e1是v1，v2的邻边．为简便常将Ψ省略，记为G=(V，E),e1=v1v2，…这里的图不是几何意义下的图形，只要保持V，E，Ψ不变，顶点的位置、边的长短曲直都可以任意选择。图的代数表示关联矩阵法R=(rij)nm(n为顶点数，m为边数），其中问题所示图的关联矩阵为仅当以vi为顶点的邻边是ej时rij＝1A=(aij)nn，其中邻接矩阵法即仅当vi与vj之间有边相连时aij

3、=1问题图的邻接矩阵为消防设施的安置在每个路口都安置可达目的.去掉v5，在v1、v2、v3、v4各安置一个也可达到目的。再去掉v1，在v2、v3、v4各安置一个仍然可以。在v1、v3、v5或v2、v4、v5各安置一个也可以。只在2个路口安置消防设施是不行的需要研究图的顶点与边的关系，图的覆盖问题正是讨论这种关系的。若图G的每条边都至少有一个端点在顶点集V的一个子集K之中，则K称为G的覆盖{v1,v2,v3,v4}，{v1,v3,v4,v5}，{v3,v4,v5}，(v1,v3,v5)，{v2,v4,v5}都是右图的覆盖一个图可以有很多覆盖图的覆盖问题含顶点个数最少的复盖称为最

4、小覆盖最小覆盖不唯一，如上面的{v2,v4,v5}，{v1,v3,v5}等最小覆盖中顶点个数称覆盖数，记作α最小覆盖数为唯一的消防设施的安置问题归结为求图的最小覆盖注：与极小覆盖的区别关联矩阵表示顶点与边之间的关系，使用关联矩阵求最小覆盖。消防设施的安置方法一个显然成立的结论顶点集V的子集K是图G的一个覆盖，当且仅当G的关联矩阵R中K的各顶点所对应的行内，每列至少存在一个元素1。由此结论可以找出一个最小复盖，以问题为例，步骤如下：1）在矩阵中取恰有两个1的那一列中1所在的行，如v3行。令v3K，划去v3行及v3行中元素1所在的e2、e3、e6列，得2）在上面得出矩阵中取恰有

5、两个1的那一列中1所在的行，如v5行。令v5K，重复上面的步骤。v1>v2，v1>v4若对所有的j，rkj=1rij=1，记vi>vk划去v2、v4行，v1K最小覆盖K={v1,v3,v5}用0~1规划求解xi=1~vi点设置消防设施设xi只能取0，1两个值要求S=x1+x2+x3+x4+x5达到最小xi=0~vi点不设置消防设施其又受到每条边ei必须被覆盖到的约束,即：x1+x2≥1；x2+x3≥1；x3+x4≥1；x1+x4≥1；x2+x5≥1；x3+x5≥1；x4+x5≥1；因而问题化为如下0~1规划问题：MinS=x1+x2+x3+x4+x5S.t.x1+x2

6、≥1；x2+x3≥1；x3+x4≥1；x1+x4≥1；x2+x5≥1；x3+x5≥1；x4+x5≥1；xi=0,1，i=1,2,3,4,5。监狱看守问题每间牢室设一看守是多余的在v1,v3,v5各设一看守即可,同时监视v2,v4。还可以把v3处的看守去掉，只留v1、v5。在v2、v3或v4、v5处设看守也可不能更少了！所以至少需要2名看守图的方法与上问题的区别用若干顶点控制所有邻边用若干顶点通过邻边控制所有顶点覆盖问题控制问题消防看守看守问题为图论中控制集问题若图G的每个顶点或者直接属于顶点集V的某个子集C，或者它的邻边的另一端点属于C，则C称为G的控制集。监狱看守问题顶点集

7、{v1,v3,v5}，{v1,v5}，{v2,v3}等都是图的控制集含顶点个数最少的控制集称为最小控制集如{v1,v5}，{v2,v3}最小控制集中顶点个数称为控制数，记作δ邻接矩阵表示顶点之间的联系由邻接矩阵确定最小控制集的算法与覆盖集类似。留给同学们研究