| 推点与二部竞赛图的强连通性 |
| |
| 引用本文： | 王培.推点与二部竞赛图的强连通性[J].系统科学与数学,2006,26(1):005-010. |
| |
| 作者姓名： | 王培 |
| |
| 作者单位： | 中国科学院数学与系统科学研究院系统所,北京,100080;中国科学院研究生院,北京,100049 |
| |
| 摘 要： | 设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是最好可能的．
|
| 关 键 词： | 二部竞赛图 推点 强连通 |
| 收稿时间： | 2004-11-15 |
| 修稿时间： | 2004年11月15 |
Pushing Vertices and the Strong Connectivity of Bipartite Tournaments |
| |
| Wang Pei.Pushing Vertices and the Strong Connectivity of Bipartite Tournaments[J].Journal of Systems Science and Mathematical Sciences,2006,26(1):005-010. |
| |
| Authors: | Wang Pei |
| |
| Institution: | Institute of Systems Science, Academy ofMathematicsand Systems Science, Chinese Academy of Sciences, Beijing 100080; Graduate University of Chinese Academy of Sciences, Beijing 100049 |
| |
| Abstract: | 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 givendigraph $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. |
| |
| Keywords: | Bipartite tournament pushing vertices strongly connected |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
