• 论文 • 上一篇    下一篇

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

王培   

  1. 中国科学院数学与系统科学研究院系统所, 北京 100080; 中国科学院研究生院, 北京 100049
  • 收稿日期:2004-11-15 修回日期:2005-03-21 出版日期:2006-02-25 发布日期:2006-02-25
  • 通讯作者: 王培

王培. 推点与二部竞赛图的强连通性[J]. 系统科学与数学, 2006, 26(1): 5-010.

Wang Pei . Pushing Vertices and the Strong Connectivity of Bipartite Tournaments[J]. Journal of Systems Science and Mathematical Sciences, 2006, 26(1): 5-010.

Pushing Vertices and the Strong Connectivity of Bipartite Tournaments

Wang Pei   

  1. Institute of Systems Science, Academy ofMathematicsand Systems Science, Chinese Academy of Sciences, Beijing 100080; Graduate University of Chinese Academy of Sciences, Beijing 100049
  • Received:2004-11-15 Revised:2005-03-21 Online:2006-02-25 Published:2006-02-25
  • Contact: Wang Pei
设$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$是最好可能的.
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\leq |X|\leq |Y|\leq 2^{|X|-1}-1$, then $D$ can be
made strongly connected by pushing vertices, and this result is best possible.

MR(2010)主题分类: 

()
No related articles found!
阅读次数
全文


摘要