王培
设$D$是一个有向图,$S$是$V(D)$的子集.
在$D$中{推$S$},是指颠倒$D$中所有的只有一个端点在$S$中的弧的方向.
Klostermeyer提出了对于任给的一个有向图$D$,能否通过推点使之成为强连通的有向图的问题.
他证明了上述判定问题是$NP-$完备的.而我们论
证了对于任意的二部竞赛图$D$,如果$V(D)$的二划分是$(X,Y)$,并满足
$3\leq |X|\leq |Y|\leq 2^{|X|-1}-1$,则可以通过推点使$D$成为强连通的有向图,
而且,$|Y|$的上界$2^{|X|-1}-1$是最好可能的.