推点与二部竞赛图的强连通性  

PUSHING VERTICES AND THE STRONG CONNECTIVITY OF BIPARTITE TOURNAMENTS

作　　者：王培[1] 

机构地区：[1]中国科学院数学与系统科学研究院系统所

出　　处：《系统科学与数学》2006年第1期5-10,共6页Journal of Systems Science and Mathematical Sciences

摘　　要：设D是一个有向图,S是V(D)的子集．在D中推S,是指颠倒D中所有的只有一个端点在S中的弧的方向． Klostermeyer提出了对于任给的一个有向图D,能否通过推点使之成为强连通的有向图的问题．他证明了上述判定问题是NP-完备的．而我们论证了对于任意的二部竞赛图D,如果V(D)的二划分是(X,Y),并满足3≤|X|≤|Y|≤2|X|-1-1, 则可以通过推点使D成为强连通的有向图,而且,|Y|的上界2|X|-1-1是最好可能的．Let D be a digraph and S a subset of V（D）. Pushing S in D means reversing the orientation of all arcs with exactly one end in S. Klostermeyer proved that it is NP-complete to decide if a given digraph D can be made strongly connected by pushing vertices. In this paper, we show that, for any bipartite tournament D with the bipartition （X, Y） of V（D）, if 3 ≤｜X｜≤｜Y｜≤2^｜X｜- 1, then D can be made strongly connected by pushing vertices, and this result is best possible.

关 键 词：二部竞赛图 推点 强连通 

分 类 号：O157.5[理学—数学] O141.1[理学—基础数学]