[科普中國(guó)]-競(jìng)賽圖

簡(jiǎn)介

競(jìng)賽圖是通過(guò)在無(wú)向完整圖中為每個(gè)邊緣分配方向而獲得的有向圖（有向圖）。 也就是說(shuō)，它是一個(gè)完整圖形的方向，等價(jià)于一個(gè)有向圖，其中每對(duì)不同的頂點(diǎn)通過(guò)單個(gè)有向邊連接，即每對(duì)頂點(diǎn)之間都有一條邊相連的有向圖稱(chēng)為競(jìng)賽圖。1

蘭多（1953）首先調(diào)查了競(jìng)賽圖的許多重要屬性。競(jìng)賽圖的當(dāng)前應(yīng)用包括投票理論和社會(huì)選擇理論的研究等。 競(jìng)賽圖起源于這樣的圖形解釋?zhuān)貉h(huán)賽，其中每個(gè)玩家恰好一次遇到每個(gè)其他玩家。 在競(jìng)賽圖中，頂點(diǎn)對(duì)應(yīng)于球員。 每對(duì)玩家之間的邊緣從勝者到失敗者。 如果每個(gè)玩家都對(duì)陣同樣數(shù)量的其他玩家，那么這個(gè)競(jìng)賽圖就被稱(chēng)之為常規(guī)競(jìng)賽圖。2

路徑和循環(huán)任何有限數(shù)量n個(gè)頂點(diǎn)的競(jìng)賽圖都包含一個(gè)哈密爾頓路徑，即所有n個(gè)頂點(diǎn)上的直線(xiàn)路徑。假設(shè)該語(yǔ)句適用于n，并考慮n + 1個(gè)頂點(diǎn)上的任何競(jìng)賽圖T。 選擇T的頂點(diǎn)v0，并考慮的一個(gè)有向路徑?，F(xiàn)在讓是最大的，所以對(duì)于每個(gè)都有一個(gè)從到的有向邊。

是根據(jù)需要設(shè)置的有向路徑。 這個(gè)參數(shù)還給出了一種求解哈密爾頓算子的算法。 只需要檢查邊緣的。

這意味著緊密聯(lián)系的競(jìng)賽圖有一個(gè)哈密爾頓循環(huán)（Camion 1959）。 每個(gè)聯(lián)系的競(jìng)賽圖是頂點(diǎn)泛循環(huán)：對(duì)于每個(gè)頂點(diǎn)v，并且每個(gè)k在競(jìng)賽圖中的三個(gè)到頂點(diǎn)的數(shù)量的范圍內(nèi)，存在包含v的長(zhǎng)度為k的循環(huán)。此外，如果比賽是4連接的，則每對(duì)頂點(diǎn)可以與哈密爾頓路徑連接（Thomassen 1980）。

傳遞性在競(jìng)賽圖中，被叫做一個(gè)傳遞。換句話(huà)說(shuō)，在傳遞競(jìng)賽圖中，頂點(diǎn)（嚴(yán)格地）由邊緣關(guān)系完全排序。

等價(jià)條件以下語(yǔ)句與n個(gè)頂點(diǎn)上的競(jìng)賽圖T相當(dāng)：

（1）T具有傳遞性；

（2）T是一個(gè)嚴(yán)格的總排序；

（3）T是非循環(huán)的；

（4）T不包含長(zhǎng)度為3的循環(huán)；

（5）T的得分序列（外差集）為{0,1,2，...，n-1}；

（6）T只有一個(gè)哈密爾頓路徑。

拉姆齊理論傳遞競(jìng)賽圖在拉姆齊理論中起到類(lèi)似于無(wú)向圖中的作用。 特別是，n個(gè)頂點(diǎn)上的每個(gè)競(jìng)賽圖在頂點(diǎn)上包含一個(gè)傳遞子公式。證明很簡(jiǎn)單：選擇任何一個(gè)頂點(diǎn)v作為這個(gè)子公式的一部分，并在v的輸入鄰集或v的傳出鄰集之間遞歸地形成其余的子體，然后取較大者。

縮合任何比賽的本身就是一場(chǎng)傳遞性的比賽。 因此，即使是不可傳遞的比賽，競(jìng)賽圖的強(qiáng)力連接組件也可能被完全排序。

得分序列和分?jǐn)?shù)集比賽的得分序列是比賽頂點(diǎn)的不規(guī)則序列。 比賽的得分集是在該比賽中頂點(diǎn)的偏差的整數(shù)集合。

Landau的定理（1953）：整數(shù)序列當(dāng)且僅當(dāng)滿(mǎn)足下面條件的時(shí)候是一個(gè)得分序列：

讓s（n）是大小為n的不同得分序列的數(shù)量。 序列s（n）（OEIS中的序列A000571）開(kāi)始為：

溫斯頓和克萊特曼證明，對(duì)于足夠大的n：

其中c1= 0.049。

這些提供證據(jù)表明：

這里φ表示一個(gè)漸近緊的界限。

姚明表示，每一個(gè)非空的整數(shù)都是一些比賽的得分。3