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

PUSHING VERTICES AND THE STRONG CONNECTIVITY OF BIPARTITE TOURNAMENTS

设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.