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

Panconnected Vertices-Pairs in Tournaments

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

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.