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

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

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

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