图论7课件.pptVIP

第七节 系统监控模型 * Good good study, day day up ! 任兴龙教案 6.7 系统监控模型 实际问题： 1.在城市街道中需在街道口设立岗亭，以便监 控和指挥交通，为监控所有街道，问要设多少 岗亭？ 2.一个指挥系统，被指挥的单位之间有着若干 通讯线路，欲在某些单位建立指挥站，以便可 以通过指挥站给各单位下达命令，问如何建立 指挥站？ 基本概念 定义1 设图G = (V, E ), K?V,如果图G的每条边都 至少有一个顶点在K中, 则称K是G的一个点覆盖. 若G的一个点覆盖中任意去掉一个点后不再是点 覆盖, 则称此点覆盖是G的一个极小点覆盖. 顶点 数最少的点覆盖, 称为G的最小点覆盖. 图中, { v0, v2, v3, v5, v6} 是极小点覆盖, { v0, v2, v4, v6} 是最小点覆盖. 点边关系 定义2 设图G = (V, E ), I ?V,如果I中任意两个顶 点在G中都不相邻, 则称I是G的一个独立点集. 若G的一个独立点集中任意添加一个点后不再 是独立点集, 则称此独立点集是G的一个极大 独立点集. 顶点数最多的独立点集, 称为G的最 大独立点集. 图中, { v1, v4}是极大独立点集, { v1, v3, v5}是最大独立点集. 点点关系 定义3 设图G = (V, E ), D ?V, 如果对任一v∈V, 或者v∈D, 或者v与D的某个点相邻, 则称D是G的 一个控制集. 若G的一个控制集中任意去掉一个点 后不再是控制集, 则称此控制集是G的一个极小 控制集. 顶点数最少的控制集, 称为G的最小控制 集. 图中, { v1, v3, v5}是极小控制集, { v0}是最小控制集. 点点关系 定理1 设无向图G = (V, E )中无孤立点(不与 任何边关联的点), 若D是G中极大独立点集, 则D是G中极小控制集. 定理2 设无向图G = (V, E )中无孤立点, K ?V, 则K是G的点覆盖当且仅当Kc = V \K是G的独 立点集. 推论 设无向图G = (V, E ) 中无孤立点, K ?V, 则K是G的最小 (极小) 点覆盖当且仅当Kc = V \K是G的最大 (极大) 独立点集. ① 若E =?, 停. 否则取u∈V, 使d ( u ) = max { d ( v ) | v∈V } 系统监控问题之一 例26：假设v1, v2, … , v7是7个哨所, 监视着11条 路段(如图所示), 为节省人力, 问至少需要在几个 哨所派人站岗, 就可以监视全部路段? 启发式算法 ： ② 令K = K∪{ u }, G = G \{ u }, 转向① 第七节 系统监控模型 * Good good study, day day up ! 任兴龙教案