划分图上的正影响数(英文)

作者：赵伟良; 赵衍才

来源：运筹学学报, 2012, (01): 41-48.

DOI：10.15960/j.cnki.issn.1007-6093.2012.01.008

• 全控制
• 符号全控制
• 正影响数
• 社会网络 total domination
• signed total domination
• positive influencing number
• social networks

一个社会网络中通常包括具有正面影响和负面影响的两类人员,为了研究这个社会网络中人们之间相互影响的某些规律,引入了一个新的概念.用划分图G=(V,E),V=V+∪V~-表示这样的一个社会网络,其中V~+和V~-分别表示正面人员的集合和负面人员的集合.图G的一个点子集D(?)V~-被称为G的一个正影响集,若G的每个点的至少一半的邻点在D∪V~+中.G的所有正影响集的最小基数称为G的正影响数.给出G的正影响数的几个下界并证明了这些界是紧的.此外,还证明了求正影响数问题在二部图和弦图上都是NP-完全的.

• 单位
  蚌埠学院; 浙江工业职业技术学院