竞赛图中的泛连通性点对  

Panpathical Vertex Pairs in Tournaments

作　　者：刘爱霞[1] 杨爱民[2] 

机构地区：[1]山西大学商务学院,太原030031 [2]山西大学数学科学学院,太原030031

出　　处：《太原科技大学学报》2008年第3期223-225,共3页Journal of Taiyuan University of Science and Technology

基　　金：国家自然科学基金(10471081);山西省自然科学基金(20031003)

摘　　要：证明了每个连通的但非强连通的竞赛图中至少存在一个泛连通性点对且该点对可在多项式时间内找到。另外,我们还得到连通的但非强连通的竞赛图中存在泛连通性点对的个数。特别地,证明了每个连通的但非强连通的竞赛图中不存在恰好两个泛连通性点对。We prove that there exists at least a panpathical vertex pair in every connected but not strongly connected tournament and the panpathical vertex pairs can be found in polynomial times. In addition,we also obtain the numher of panpathical vertex pairs in a connected but not strongly connected tournament. In particular, it is proved that there are not precise two panpathical vertex pairs in any connected but not strongly connected tournament.

关 键 词：Hamihion路 HAMILTON圈 竞赛图 泛连通性点对 

分 类 号：O157.5[理学—数学]