划分图上的正影响数

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

Positive Influencing Number of Partitioned Graphs

In this paper, a concept is introduced in order to model a class of problems in social networks. A social network consisting of positive and negative influential individuals is represented as a partitioned graph G=(V,E) with vertex set partition V=V⁺\cup V^-. A subset D\subseteq V^- is called a positive influencing set if every vertex of G has in D\cup V⁺ at least half of its neighbors. The positive influencing number of G is the minimum cardinality of a positive influencing set. In the present paper, we show some sharp lower bounds for this parameter, and prove that this problem is NP-complete for partitioned bipartite graphs and partitioned chordal graphs, respectively.