图的支配集、覆盖集与独立集

Published on 2016 - 06 - 25

点支配集

支配、点支配集、支配数

支配与支配集:设无向图为G(V,E),顶点集合V*⊆V,若对于∀v∈(V-V*),∃u∈V*,使得(u,v)∈E,则称u支配v,并称V*为G的一个点支配集(Vertex Dominating Set,支配集)。

在图1(a)中,取V*={v1,v5},则V*就是一个支配集。因为V-V*={v2,v3,v4,v6,v7}中的每个顶点都是V*中某个顶点的邻接顶点。

通俗地讲,所谓点支配集,就是V*中的顶点能“支配”V-V*中的每个顶点,即V-V*中的每个顶点都是V*中某个顶点的邻接顶点,或者说V中的顶点要么是V*集合中的元素,要么与V*中的一个顶点相邻。

注意:在无向图中存在用尽可能少的顶点去支配其他顶点的问题,所以支配集有极小和最小的概念。最大支配集的概念是没有意义的,因为对任何一个无向图G(V,E),取V*=V,总是满足支配集的定义。

极小支配集:若支配集V*的任何真子集都不是支配集,则称V*是极小支配集。

最小支配集:顶点数最少的支配集称为最小支配集。

点支配数(Vertex Dominating Number):最小支配集中的顶点数称为点支配数,记作γ0(G)或简记为γ0。

在图1(a)中,{v1,v5}、{v3,v5}和{v2,v4,v7}都是极小支配集,{v1,v5}、{v4,v5}和{v3,v6}都是最小支配集,因此γ0=2。

在图1(b)中,{v1}和{v2,v3,v4,v5,v6,v7}都是极小支配集,{v1}是最小支配集,因此γ0=1。

在图1(c)中,{v1}、{v2,v4}、{v2,v5}等都是极小支配集,显然γ0=1。

点支配集的性质

  • 性质1 若G中无孤立顶点,则存在一个支配集V*,使得G中除V*外的所有顶点也组成一个支配集(即V-V*也是一个支配集)。(证明略。)
  • 性质2 若G中无孤立顶点,V*为极小支配集,则G中除V*外的所有顶点也组成一个支配集(即V-V*也是一个支配集)。(证明略。)

例1 应用点支配集设置通信基站

假设需要在8个城镇A~H之间选择若干个城镇建通信基站,使得通信信号覆盖这8个城镇。如果在A建设一个基站,能同时覆盖到B、C、D和E;如果在B建设一个基站,能同时覆盖A、C和G等。问至少需要建几个基站?

用顶点表示每个城镇,如果在城镇X建设一个基站,能同时覆盖到Y城镇,那么在顶点X和Y之间连一条边。这样构造的图如图2所示。现在将问题转换成求最小支配集问题。在图2中,最小支配集是{A,H},γ0=2。因此至少需要建设两个通信基站。

点覆盖集

点覆盖边、点覆盖集、点覆盖数

点覆盖集(Vertex Covering Set):设无向图为G(V,E),顶点集合V*⊆V,若对于∀e∈E,∃v∈V*,使得v与e相关联,则称v覆盖e,并称V*为G的一个点覆盖集或简称点覆盖。

在图3(a)中,取V*={v1,v3,v5,v7},则V*就是一个点覆盖集。因为G中的每条边都被V*中某个顶点“覆盖”住了。

通俗地讲,所谓点覆盖集V*,就是G中所有的边至少有一个顶点属于V*

注意:

  1. 点覆盖集里的“覆盖”,含义是顶点“覆盖”边;
  2. 在无向图中存在用尽可能少的顶点去“覆盖”住所有边的问题,所以点覆盖集有极小和最小的概念。最大点覆盖集的概念是没有意义的,因为对任何一个无向图G(V,E),取V*=V,总是满足点覆盖集的定义。

极小点覆盖:若点覆盖V*的任何真子集都不是点覆盖,则称V*是极小点覆盖。

最小点覆盖:顶点个数最少的点覆盖称为最小点覆盖。

点覆盖数(Vertex Covering Number):最小点覆盖的顶点数称为点覆盖数,记作α0(G),简记为α0。

在图3(a)中,{v2,v3,v4,v6,v7}、{v1,v3,v5,v7}等都是极小点覆盖,{v1,v3,v5,v7}等是最小点覆盖,因此α0=4。

在图3(b)中,{v1}和{v2,v3,v4,v5,v6,v7}是极小点覆盖,{v1}是最小点覆盖,因此α0=1。

在图3(c)中,{v1,v2,v4,v5}、{v1,v2,v4,v6}是极小点覆盖,也都是最小点覆盖,因此α0=4。

例2 应用点覆盖集配置小区消防设施

某小区计划在某些路口安装消防设施,约定只有与路口直接相连的道路才能使用该路口的消防设施(发生火灾时消防车开进小区道路上并使用路口的消防设施),为了使所有道路在必要时都能使用消防设施,问至少要配置多少套消防设施。

小区平面图如图4(a)所示,以路口为顶点、街道为边,构造如图4(b)所示的无向图。本题要求用最少的顶点“控制”所有的边,即“覆盖”住所有的边。因此,本题要求的是最小顶点覆盖集。图4(b)给出了一个解,实心圆圈顶点表示安装消防设施的路口。因此最少需要8套消防设施。

点独立集

点独立集、点独立数

点独立集(Vertex Independent Set):设无向图为G(V,E),顶点集合V*⊆V,若V*中任何两个顶点均不相邻,则称V*为G的点独立集,或简称独立集。

在图5(a)中,取V*={v1,v5},则V*就是一个独立集。因为v1和v5是不相邻的。

注意:在无向图中存在将尽可能多的、相互独立的顶点包含到顶点集合的子集V*中的问题,所以独立集有极大和最大的概念。最小独立集的概念是没有意义的,因为对任何一个无向图G(V,E),取V*=(空集),总是满足独立集的定义。

极大点独立集:若在V*中加入任何顶点都不再是独立集,则称V*为极大点独立集。

最大点独立集:顶点数最多的点独立集称为最大点独立集。

点独立数(Vertex Independent Number):最大点独立集的顶点数称为点独立数,记作β0(G),简记为β0。

在图5(a)中,{v1,v5}、{v3,v6}、{v2,v4,v7}都是极大点独立集,{v2,v4,v7}是最大点独立集,因此β0=3。

在图5(b)中,{v1}和{v2,v3,v4,v5,v6,v7}都是极大点独立集,{v2,v3,v4,v5,v6,v7}是最大点独立集,因此β0=6。

在图5(c)中,{v2,v4}、{v2,v5}都是极大点独立集,也都是最大点独立集,显然β0=2。

例3 应用点独立集存放化学药品

某仓库要存放n种化学药品,其中有些药品彼此不能存放在一起,因为相互之间可能引起化学或药物反应导致危险,所以必须把仓库分成若干区,各区之间相互隔离。至少把仓库分成多少隔离区,才能确保安全?

考虑7种药品的情况。用v1,v2,…,v7分别表示这7种药品,已知不能存放在一起的药品为:(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v2,v7),(v3,v4),(v3,v6),(v4,v5),(v4,v7),(v5,v6),(v5,v7),(v6,v7)。在本题中,把各种药品作为顶点,即顶点集为:V(G)={v1,v2,v3,v4,v5,v6,v7}。然后把不能存放在一起的药品用边相连,就构成一个图,如图6所示。

由点独立集的定义可知,能存放到同一个仓库中的药品应属于同一个点独立集,为了使得仓库数尽可能少,在不导致危险的前提下应该在同一个仓库中存放尽可能多的药品,这个点独立集还应该尽量是极大点独立集。另外,存放在不同仓库中的药品集合分别对应不同的点独立集,而且这些点独立集没有公共元素。

设想把仓库划分为若干个隔离区,分别用Ⅰ、Ⅱ、Ⅲ、…来代表,每个隔离区相当于一个顶点子集。根据题意,图中各边的两个顶点不能存入在同一个隔离区。现在按照如下的方法将各个顶点划分到不同的隔离区中:任取一顶点,如v1,存放在Ⅰ区;因v2与v1有边相连,所以把v2存放在Ⅱ区;v3与v2有边相连,但与v1无边相连,故可存放在Ⅰ区;……。以此类推,最后一个顶点v7,既与v5相连,也与v2、v4、v6相连,所以既不能存放在Ⅰ区,也不能存放在Ⅱ区,只好存放在Ⅲ区。从而这7种药品可用3个隔离区存放。每个隔离区存放的药品分别为,Ⅰ区:v1,v3,v5;Ⅱ区:v2,v4,v6;Ⅲ区:v7。图6标明了各顶点(代表对应的药品)所属的隔离区。

点支配集、点覆盖集、点独立集之间的联系

点支配集、点覆盖集、点独立集都是顶点的集合,这些集合之间存在以下联系。

  • 定理7.1 设无向图G(V,E)中无孤立顶点,则G的极大点独立集都是G的极小支配集。逆命题不成立(即极小支配集未必是极大独立集)。
  • 定理7.2 一个独立集是极大独立集,当且仅当它是一个支配集。
  • 定理7.3 设无向图G(V,E)中无孤立顶点,顶点集合V*⊆V,则V*是G的点覆盖,当且仅当V-V*是G的点独立集。
  • 推论:设G是n阶无孤立点的图,则V*是G的极小(最小)点覆盖集,当且仅当V-V*是G的极大(最大)点独立集,从而有:α0+β0=n(n为顶点个数)。

参考文档

图论算法理论、实现及应用 第七章 支配集、覆盖集、独立集与匹配