词条 | 支配集 |
释义 | 形式上,支配集可描述如下:给定无向图G =〈V , E〉,其中V 是大小为n 的点集, E 是边集, 那么V 的一个子集S称为支配集当且仅当对于V - S 中任何一个点v ,都有S 中的某个定点u , 使得( u , v) ∈E。 支配集问题的两个变形。 定义1 在图G=〈V , E〉中,V 的一个子集S 称为C 强支配集( C 是某个固定的常正整数) 当且仅当对任何一个大小不 小于| S| - C 的S 的一个子集S′,对于V - S 中任何一个顶点v ,都有S′中的某个定点u ,使得( u , v) ∈E。 定义2 在图G=〈V , E〉中,V 的一个子集S 称为完全支配集当且仅当对于V 中任何一个点v ,都有S - { v} 的某个点 u ,使得( u , v) ∈E。 1 支配集D是图G=<V,E>的一个顶点子集,对于G的任一顶点v,要么v属于D,要么与D中的一个顶点相邻,则D称为图G的一个支配集。若在D集中去掉任何元素后D不再是支配集,则称D是极小支配集。称图G的所有支配集中顶点个数最少的支配集为最小支配集,最小支配集中的顶点个数称为图G的支配数。 如何求G的所有极小支配集合? 对符号X,Y,Z,定义两种运算X+Y(加法运算,或运算)和XY(乘法运算,与运算),满足以下运算定律: 交换律:X+Y = Y+X; XY = YX 结合律:(X+Y)+Z = X+(Y+Z); (XY)Z = X(YZ) 分配律:X(Y+Z) = XY+XZ 吸收律:X+X = X; XX = X; X+XY = X 求所有极小支配集的公式: 一个顶点与它相邻的所有顶点进行加法运算组成一个因子项,n个因子项再相乘。连乘过程中根据上述运算规律展开成积之和的形式。每一积项给出一个最小支配集。 (1 + 2 + 3 + 4)(2 + 1 + 4)(3 + 1 + 4)(4 + 1 + 2 + 3 + 5 + 6)(5 + 4 + 6)(6 + 4 + 5) =15 + 16 + 4 + 235 + 236 故极小支配集为 {V1, V5}, {V1, V6}, {V4}, {V2, V3, V5}, {V2, V3, V6} |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。