大师作文网离散数学中关于配集的定义,
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/11 05:21:16
离散数学中关于配集的定义,
离散数学中没有配集一说,叫支配集,定义如下：
给定无向图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.
给定无向图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.