论文部分内容阅读
本文的研究内容涉及有向图的两个方面:多部竞赛图的传递性和半完全多部有向图的3-王中王.
n-部竞赛图是完全n-部有向图的一个定向.当n=2时,称其为2-部竞赛图,竞赛图是恰好有n个点的n-部竞赛图.称有向图D是可传递的,如果对D中每一对弧xy和yz,x≠z,有xz∈A(D).
在文献[1]中,JorgenBang-Jensen,GregoryGutin证明了若有向图D的强连通分支无圈序为D1,D2,…,Dp,且D是可传递的,则每一个Di是完全的,且通过收缩每个Di成一点,然后删除重弧得到的有向图H是一个传递定向图,换句话即D=H[D1,D2,…Dp].本文的第二章在此基础上给出了多部竞赛图具有传递性的充分必要条件.
有关有向图的王的研究是从1953年开始的,在竞赛图,多部竞赛图的王方面已有相当丰硕的研究成果.在1980年,Maurer提出了竞赛图王中王的概念.即:
设H1是一个竞赛图,令K2(H1)表示H1的2-王的集合,对i≥1,设Hi+1=Hi[K2(Hi)],注意到K2(H1)()K2(H2)()K2(H3)()…,因为K2(H1)是一个有限集,则必存在一个整数p,使得对所有i<p,有K2(Hi+1)()K2(Hi),且对i≥p,有K2(Hi+1)=K2(Hi),Maurer称任意点u∈K2(Hp)为H1的一个王中王.
B.P.Tan将王中王的概念推广到了无发点的半完全n-部有向图T,且提出了r-王中王的概念,并证明了:
当r=1时,T的1-王中王概念无意义.当r=2,4时,T的r-王中王集合非空,指出当r=3时,T的3-王中王集合不一定非空,并提出了问题:哪些无发点的半完全多部有向图的3-王中王集合是非空的?他指出,要解决该问题只需考虑满足k3(T)≥1(k3(T)=|K3(T)|)的无发点的半完全多部有向图.本文则在第二章中解决了如下的问题:
(1)给出了正则半完全多部有向图T中使k3(T)≥1的一些充分条件.
(2)给出满足3-王中王集合非空的一类图.