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

消防设施与监狱看守 若干条街道构成居民小区如图所示 e1 e2 e7表示街道 v1 v2 v5表示交叉路口 现计划在某些路口安置消防设施 只有与路口直接相连的街道才能使用它们 为使所有街道必要时都有消防设施可用 在哪些路口安置设施才最节省呢 问题 一座监狱的几间牢室有道路相连 亦为上图所示 v1 v2 v5表示牢室 e1 e2 e7表示道路 监狱看守要设在通过道路能直接监视所有牢室的地方 如果看守不得走动 那么他们应呆在某些牢室 即路口 所在地 问至少需要几名看守才能完成监视任务呢 图的几个基本概念 以上图为例叙述 图是由顶点集V v1 v2 v5 边集E 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 1 A aij n n 其中 邻接矩阵法 即仅当vi与vj之间有边相连时aij 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 都是右图的覆盖 一个图可以有很多覆盖 图的覆盖问题 含顶点个数最少的复盖称为最小覆盖 最小覆盖不唯一 如上面的 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 在上面得出矩阵中取恰有两个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 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的控制集 监狱看守问题 顶点集 v1 v3 v5 v1 v5 v2 v3 等都是图的控制集 含顶点