扩张竞赛图中的泛连通性点对

摘要

研究了扩张竞赛图中的泛连通性点对的存在性问题.证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对.研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,Dt是连通但非强连通的扩张竞赛图D的一个强分支无圈序.若Di(i=1,2,…,t)有1-路-圈因子,则D中必存在泛连通性点对.并且找到泛连通性点对的时间复杂度为D(n2.5).(b)设D是由连通但非强连通竞赛图T的强分支Ti(| V(Ti)|≥3)平衡扩张而成的,(当| V(Ti)|=1时,Ti不变),则D中必存在泛连通性点对.