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

研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图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中必存在泛连通性点对。

Panconnected Vertices-Pairs in Tournaments

The existence of the panconnected vertex-pairs in the extended touraments was studied. Firstly, it is proved that if D is a transitive extended tourament without tournament, then there exists no a panconnected vertexpairs in D. Next, the sufficient conditions for the existence of panconnected vertex-pairs in the extended tourna- ments were studied, which proved that （a） Let D1 , D2, ..., Dt be the acyclic ordering of the strongly connected components of D. If every Di （ i = 1,2,..., t） contains a 1-path-cycle factor, then there must be a panconnected ver- tex-pairs in D, and the algorithm to find the panconnected vertex-pairs can be performed in time O （ n^2.5 ） ; （b） If D is a digraph obtained by balanced extending the strong components Ti （ I V（ Ti ） I I〉 3 ） of the tournament T （ Ti remains unchanged,if IV（ Ti） I = 1 ） ,then there must be a panconnected vertex-pairs in D.