競賽圖的傳遞性和半完全多部有向圖的3-王中王.pdf

1、本文的研究內(nèi)容涉及有向圖的兩個方面：多部競賽圖的傳遞性和半完全多部有向圖的3-王中王. n-部競賽圖是完全n-部有向圖的一個定向.當(dāng)n=2時，稱其為2-部競賽圖，競賽圖是恰好有n個點(diǎn)的n-部競賽圖.稱有向圖D是可傳遞的，如果對D中每一對弧xy和yz，x≠z，有xz∈A(D). 在文獻(xiàn)[1]中，JorgenBang-Jensen,GregoryGutin證明了若有向圖D的強(qiáng)連通分支無圈序?yàn)镈1，D2，…，Dp，且D是可傳遞

2、的，則每一個Di是完全的，且通過收縮每個Di成一點(diǎn)，然后刪除重弧得到的有向圖H是一個傳遞定向圖，換句話即D=H[D1，D2，…Dp].本文的第二章在此基礎(chǔ)上給出了多部競賽圖具有傳遞性的充分必要條件. 有關(guān)有向圖的王的研究是從1953年開始的，在競賽圖，多部競賽圖的王方面已有相當(dāng)豐碩的研究成果.在1980年，Maurer提出了競賽圖王中王的概念.即： 設(shè)H1是一個競賽圖，令K2(H1)表示H1的2-王的集合，對i≥1，設(shè)H

3、i+1=Hi[K2(Hi)]，注意到K2(H1)()K2(H2)()K2(H3)()…，因?yàn)镵2(H1)是一個有限集，則必存在一個整數(shù)p，使得對所有i＜p，有K2(Hi+1)()K2(Hi)，且對i≥p，有K2(Hi+1)=K2(Hi)，Maurer稱任意點(diǎn)u∈K2(Hp)為H1的一個王中王. B.P.Tan將王中王的概念推廣到了無發(fā)點(diǎn)的半完全n-部有向圖T，且提出了r-王中王的概念，并證明了： 當(dāng)r=1時，T的1-王中