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

• 作者: 王培
• 来源期刊: 系统科学与数学
• 学科: 数学
• 关键词: 二部竞赛图 推点 强连通
• 年，卷（期）: 2006,（1）
• 页码范围: 5-10
• 页数: 6页
• 分类号: O1
• 字数: 5322字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-0577.2006.01.002

摘要

设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是最好可能的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王培	中国科学院数学与系统科学研究院系统所	15	55	4.0	7.0