请输入您要查询的百科知识:

 

词条 支配集
释义

形式上,支配集可描述如下:给定无向图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条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/20 12:06:05