锦标赛

一个完全有向图 (Skiena 1990, p. 175)，即，一个图中每对节点都通过一个唯一的有向边连接。上面显示的第一个和第二个 3 节点锦标赛分别称为传递三元组和循环三元组 (Harary 1994, p. 204)。

锦标赛（也称为锦标赛图）之所以如此命名，是因为一个 节点锦标赛图对应于一个锦标赛，其中一组 名队员与其他所有 名队员比赛，并且每场比赛都以一名队员获胜，另一名队员失败告终。所谓的得分序列可以与每个锦标赛相关联，给出锦标赛中队员获得的得分集合，其中每次获胜计为一分，每次失败不计分。（另一种评分系统用于计算锦标赛所谓的锦标赛矩阵，获胜得 1 分，失败得 分。）给定锦标赛的得分序列是从按非递减顺序排序的出度集合获得的。

在 , 3, 4, ... 节点上的非同构锦标赛的数量 是 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) 使用波利亚计数定理获得了这些数字作为 函数的公式。对于对称群，定义

(1)

其中

(2)

其中 是 在 的共轭类中群元素的数量， 是类中任何成员的不相交循环表示中长度为 的循环数。定义

(3)

其中 是 和 的最大公约数。然后

(4)

(Davis 1954)。

每个锦标赛都包含奇数个哈密顿路径 (Rédei 1934; Szele 1943; Skiena 1990, p. 175)。然而，一个锦标赛具有有向哈密顿环 当且仅当它是强连通的 (Foulkes 1960; Harary and Moser 1966; Skiena 1990, p. 175)。

术语“锦标赛”也指一种安排，通过这种安排，团队或队员相互比赛以确定谁是最好的。在一个 支队伍的“杯赛”锦标赛中，队伍在一系列 决赛、...、1/8 决赛、四分之一决赛、半决赛和决赛中进行两两比赛，每轮的获胜者在下一轮与另一组获胜者比赛，而失败者在每轮被淘汰。第二名奖通常颁发给决赛中失利的队伍。然而，这种做法是不公平的，因为第二名队伍没有被要求与被第一名（以及可能是最好的）队伍淘汰的队伍比赛，因此实际上可能比被最好的队伍更早淘汰的队伍之一更差 (Steinhaus 1999)。

一般来说，为了公平地从 名参赛者中确定最好的两名队员，需要 轮比赛 (Steinhaus 1999, p. 55)。