论文部分内容阅读
研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图，那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件：证明了（a）设D1，D2，…，D1是连通但非强连通的扩张竞赛图D的一个强分支无圈序。若Di（i=1，2，…，f）有1一路一圈因子，则D中必存在泛连通性点对。午且找到泛连通性点对的时间复杂度为0（n^0.5）．（b）设D是由连通但非强连通竞赛图r的强分支t（1y（t）1≥3）平衡扩张而成的，（当Iy（t）I=1时，Ti不变），则D中必存在泛连通性点对