划分图上的正影响数

• 作者: 赵伟良 赵衍才
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 全控制 符号全控制 正影响数 社会网络
• 年，卷（期）: 2012,（1）
• 页码范围: 41-48
• 分类号: O223
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2012.01.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵伟良		8	16	1.0	4.0
2	赵衍才	蚌埠学院数学与物理系	6	2	1.0	1.0