主題
Search

錦標賽

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
Tournament

一個完全有向圖 (Skiena 1990, p. 175)，即，一個圖中每對節點都透過一個唯一的有向邊連線。上面顯示的第一個和第二個 3 節點錦標賽分別稱為傳遞三元組和迴圈三元組 (Harary 1994, p. 204)。

錦標賽（也稱為錦標賽圖）之所以如此命名，是因為一個 n 節點錦標賽圖對應於一個錦標賽，其中一組 n 名隊員與其他所有 n-1 名隊員比賽，並且每場比賽都以一名隊員獲勝，另一名隊員失敗告終。所謂的得分序列可以與每個錦標賽相關聯，給出錦標賽中隊員獲得的得分集合，其中每次獲勝計為一分，每次失敗不計分。（另一種評分系統用於計算錦標賽所謂的錦標賽矩陣，獲勝得 1 分，失敗得 -1 分。）給定錦標賽的得分序列是從按非遞減順序排序的出度集合獲得的。

在 n=2, 3, 4, ... 節點上的非同構錦標賽的數量 a(n) 是 1, 2, 4, 12, 56, 456, ... (OEIS A000568; Moon 1968; Goldberg and Moon 1970; Harary and Palmer 1973, pp. 126 and 245; Reid and Beineke 1978)。 Davis (1954) 和 Harary (1957) 使用波利亞計數定理獲得了這些數字作為 n 函式的公式。對於對稱群S_n，定義

s(pi)={0 if pi has any cycle of even length; n(pi) otherwise,
(1)

其中

n(pi)=(c(pi))/(n!)=1/(1^(p_1)p_1!2^(p_2)p_2!...n^(p_n)p_n!),
(2)

其中 c(pi) 是 pi 在 S_n 的共軛類中群元素的數量，p_k 是類中任何成員的不相交迴圈表示中長度為 k 的迴圈數。定義

d(pi)=1/2sum_(i=1)^np_i(ip_i-1)-sum_(i<j)p_jp_jGCD(i,j),
(3)

其中 GCD(i,j) 是 i 和 j 的最大公約數。然後

a(n)=sums(pi)2^(d(pi))
(4)

(Davis 1954)。

每個錦標賽都包含奇數個哈密頓路徑 (Rédei 1934; Szele 1943; Skiena 1990, p. 175)。然而，一個錦標賽具有有向哈密頓環 當且僅當它是強連通的 (Foulkes 1960; Harary and Moser 1966; Skiena 1990, p. 175)。

術語“錦標賽”也指一種安排，透過這種安排，團隊或隊員相互比賽以確定誰是最好的。在一個 n=2^k 支隊伍的“盃賽”錦標賽中，隊伍在一系列 1/2^(k-1) 決賽、...、1/8 決賽、四分之一決賽、半決賽和決賽中進行兩兩比賽，每輪的獲勝者在下一輪與另一組獲勝者比賽，而失敗者在每輪被淘汰。第二名獎通常頒發給決賽中失利的隊伍。然而，這種做法是不公平的，因為第二名隊伍沒有被要求與被第一名（以及可能是最好的）隊伍淘汰的隊伍比賽，因此實際上可能比被最好的隊伍更早淘汰的隊伍之一更差 (Steinhaus 1999)。

一般來說，為了公平地從 n 名參賽者中確定最好的兩名隊員，需要 n-1+log_2(n-1) 輪比賽 (Steinhaus 1999, p. 55)。

另請參閱

完全圖, 迴圈三元組, 有向圖, 哈密頓路徑, 得分序列, 錦標賽矩陣, 傳遞三元組

使用 探索

參考文獻

Boesch, F. and Tindell, R. "Robbins' Theorem for Mixed Graphs." Amer. Math. Monthly 87, 716-719, 1980.Chartrand, G. "Tournaments." §27.2 in Introductory Graph Theory. New York: Dover, pp. 155-161, 1985.Chvátal, V. and Thomassen, C. "Distances in Orientations of Graphs." J. Combin. Th. B 24, 61-75, 1978.Davis, R. L. "Structure of Dominance Relations." Bull. Math. Biophys. 16, 131-140, 1954.Foulkes, J. D. "Directed Graphs and Assembly Schedules." In Proc. Symp. Appl. Math. Providence, RI: Amer. Math. Soc., pp. 218-289, 1960.Goldberg, M. and Moon, J. W. "On the Composition of Two Tournaments." Duke Math. J. 37, 323-332, 1970.Harary, F. "The Number of Oriented Graphs." Mich. Math. J. 4, 221-224, 1957.Harary, F. "Tournaments." In Graph Theory. Reading, MA: Addison-Wesley, pp. 204-208, 1994.Harary, F. and Moser, L. "The Theory of Round Robin Tournaments." Amer. Math. Monthly 73, 231-246, 1966.Harary, F. and Palmer, E. M. "On the Problem of Reconstructing a Tournament from Subtournaments." Monatsh. für Math. 71, 14-23, 1967.Harary, F. and Palmer, E. M. "Tournaments." §5.2 in Graphical Enumeration. New York: Academic Press, pp. 124-127, 1973.Moon, J. W. Topics on Tournaments. New York: Holt, Rinehart, and Winston, p. 87, 1968.Ore, Ø. Graphs and Their Uses. New York: Random House, 1963.Rédei, L. "Ein Kombinatorischer Satz." Acta Litt. Szeged. 7, 39-43, 1934.Reid, K. B. and Beineke, L. W. "Tournaments." In Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson). New York: Academic Press, pp. 169-204, 1978.Roberts, F. S. Graph Theory and Its Applications to Problems of Society. Philadelphia, PA: SIAM, 1978.Ruskey, F. "Information on Score Sequences." http://www.theory.csc.uvic.ca/~cos/inf/nump/ScoreSequence.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A000568/M1262 in "The On-Line Encyclopedia of Integer Sequences."Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 54-55, 1999.Szele, T. "Kombinatorische Untersuchungen über den gerichteten vollständigen Graphen." Mat. Fiz. Lapok 50, 223-256, 1943.

在 上被引用

錦標賽

請引用為

韋斯坦因，埃裡克·W. "錦標賽。" 來自 Web 資源。 https://mathworld.tw/Tournament.html

主題分類