覆盖

(1)格中两个元素间的一种关系。设<I>a</I>，<I>b</I>∈<I>S</I>，并且<I>a</I>＜<I>b</I>，若格<I>S</I>中不存在元素<I>x</I>，使<I>a</I>＜<I>x</I>＜<I>b</I>，则称<I>b</I>覆盖<I>a</I>。(2)点覆盖(vertex covering)。图<I>G</I>顶点集合V的一个子集<I>K</I>，如果<I>G</I>中每一条边都至少有一个端点在<I>K</I>中，则称<I>K</I>为<I>G</I>的一个(点)覆盖。如果<I>K</I>是<I>G</I>的一个覆盖，去掉<I>K</I>中任意一顶点后就不再是<I>G</I>的覆盖，则<I>K</I>称为<I>G</I>的一个极小覆盖(minimal covering)。如果<I>G</I>中不包含顶点个数比<I>K</I>中顶点个数更少的覆盖，则<I>K</I>称为最小覆盖(minimum covering)。

外被