主题
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.net.cn/Tournament.html

主题分类